Homework 4

This task asks you to read and understand some code I wrote. My code solves a question in the original Pacman assignments from UC Berkeley. The question had to do with writing minimax for Pacman (so the guy can avoid the ghosts and eat the dots).

Go to the Carmen page for this class, and download the Pacman multi-agent ZIP file. In the file multiAgents.py is my solution for minimax search. Do not share this file outside of this class. The internet will hate me because they will never be able to use this question again! So keep it to yourself.

Read the code starting at line 115, the function called minimax in the class called MinimaxAgent. Also practice running Pacman with different mazes ("layouts") and depth limits:

• python pacman.py -p MinimaxAgent -l minimaxClassic -f -a depth=2
• python pacman.py -p MinimaxAgent -l openClassic -f -a depth=2
• python pacman.py -p MinimaxAgent -l trickyClassic -f -a depth=1
• python pacman.py -p MinimaxAgent -l trickyClassic -f -a depth=2
• python pacman.py -p MinimaxAgent -l trickyClassic -f -a depth=3
• python pacman.py -p MinimaxAgent -l originalClassic -f -a depth=2

And so on. Look at the various layouts in the layouts folder and try those for fun.

Now, anwser these questions (on paper or in a text file):

1. Recall that "minimax" means we want to find the best (max) move for the player (Pacman) but this depends on determining the worst (min) move for all the ghosts (best for the ghosts, worst for Pacman). Sometimes the minimax function should act like a min function, sometimes like a max function. Describe or copy the small chunk of code in the Pacman minimax function that I wrote that handles this min/max difference.
2. This code uses a depth limit. Does the depth increase in this code for each Pacman and ghost move, or only for each Pacman move, or only for each ghost move?
3. Sometimes Pacman just sits there, without eating any dots (especially on openClassic). Why does this happen? You might want to add some print statements to the code to see why it chooses the STOP action instead of something else. Also, how does the depth limit change this behavior? Try running the examples with different depth limits. Note, the impact of the depth limit is a bit counter-intuitive.

Look at the multiAgents.py file again, below the function you were looking at earlier. You will find the AlphaBetaAgent class and the exact same minimax function as before. Your task is to modify this minimax function to use alpha-beta pruning. Note, if you do it correctly, you will only need to modify the function header (where the arguments are listed) and add some code at the end of the for loop (but still inside the for loop).

Important note: In the lecture notes on this website, the code shows that you should return u if u <= alpha or if u >= beta. Instead of this, you should break from the for loop (not return u) and you should check u < alpha and u > beta (not <= or >=). Email me if you don't understand what I mean.

Test if you did it correctly with this command:

python autograder.py -q q3

It should report "Total: 4/4" tests passed. Ignore what it says about grades. You should also find that the demos work faster (since they will use the alpha-beta pruning), but otherwise make the same moves:

• python pacman.py -p AlphaBetaAgent -l minimaxClassic -f -a depth=2
• python pacman.py -p AlphaBetaAgent -l openClassic -f -a depth=2
• python pacman.py -p AlphaBetaAgent -l trickyClassic -f -a depth=1
• python pacman.py -p AlphaBetaAgent -l trickyClassic -f -a depth=2
• python pacman.py -p AlphaBetaAgent -l trickyClassic -f -a depth=3
• python pacman.py -p AlphaBetaAgent -l originalClassic -f -a depth=2

Submit just the multiAgents.py file (plus your answers to Task 1 if not on paper) to the Dropbox on Carmen.