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=2python pacman.py -p MinimaxAgent -l openClassic -f -a depth=2python pacman.py -p MinimaxAgent -l trickyClassic -f -a depth=1python pacman.py -p MinimaxAgent -l trickyClassic -f -a depth=2python pacman.py -p MinimaxAgent -l trickyClassic -f -a depth=3python 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):
- 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
minimaxfunction should act like aminfunction, sometimes like amaxfunction. Describe or copy the small chunk of code in the Pacmanminimaxfunction that I wrote that handles this min/max difference. - 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?
- Sometimes Pacman just sits there, without eating any dots
(especially on
openClassic). Why does this happen? You might want to add someprintstatements to the code to see why it chooses theSTOPaction 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=2python pacman.py -p AlphaBetaAgent -l openClassic -f -a depth=2python pacman.py -p AlphaBetaAgent -l trickyClassic -f -a depth=1python pacman.py -p AlphaBetaAgent -l trickyClassic -f -a depth=2python pacman.py -p AlphaBetaAgent -l trickyClassic -f -a depth=3python 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.