Homework 4
Table of Contents
Task 1 (40 pts)
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):
- 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 amin
function, sometimes like amax
function. Describe or copy the small chunk of code in the Pacmanminimax
function 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 someprint
statements to the code to see why it chooses theSTOP
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.
Task 2 (60 pts)
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.