Assignment 2 Pacman Project

CS 3346A / CS 3121A Assignment 2 
Total Weight: 15%

Part 1: Pacman Project (7%)
Search:
Question 7 (3 points): Eating All The Dots (a continued
question from the A1)
Now we'll solve a hard search problem: eating all the Pacman food in as few steps as
possible. For this, we'll need a new search problem definition which formalizes the
food-clearing problem: FoodSearchProblem in searchAgents.py (implemented for
you). A solution is defined to be a path that collects all of the food in the Pacman
world. For the present project, solutions do not take into account any ghosts or power
pellets; solutions only depend on the placement of walls, regular food and Pacman.
(Of course ghosts can ruin the execution of a solution! We'll get to that in the next
project.) If you have written your general search methods correctly, A* with a null
heuristic (equivalent to uniform-cost search) should quickly find an optimal solution
to testSearch with no code change on your part (total cost of 7).
python3 pacman.py -l testSearch -p AStarFoodSearchAgent
Note: AStarFoodSearchAgent is a shortcut for -p SearchAgent -a
fn=astar,prob=FoodSearchProblem,heuristic=foodHeuristic.
You should find that UCS starts to slow down even for the seemingly simple
tinySearch. As a reference, our implementation takes 2.5 seconds to find a path of
length 27 after expanding 5057 search nodes.
Note: Make sure to complete Question 4 before working on Question 7, because
Question 7 builds upon your answer for Question 4. 
Fill in foodHeuristic in searchAgents.py with a consistent heuristic for the
FoodSearchProblem. Try your agent on the trickySearch board:
python3 pacman.py -l trickySearch -p AStarFoodSearchAgent
Our UCS agent finds the optimal solution in about 13 seconds, exploring over 16,000
nodes.
Any non-trivial non-negative consistent heuristic will receive 1 point. Make sure that
your heuristic returns 0 at every goal state and never returns a negative value.
Depending on how few nodes your heuristic expands, you'll get additional points:
Number of nodes expanded Grade
more than 15000 1/4
at most 15000 2/4
at most 12000 3/4
at most 9000 4/4 (full credit; medium)
at most 7000 5/4 (optional extra credit;
hard)
Remember: If your heuristic is inconsistent, you will receive no credit, so be careful!
Can you solve mediumSearch in a short time? If so, we're either very, very impressed,
or your heuristic is inconsistent
Multi-Agent Pacman
After downloading the code ( A2-multiagent.zip ), unzipping it, and changing to the
directory, you should be able to play a game of Pacman by typing the following at the
command line:
First, play a game of classic Pacman:
python pacman.py
Now, run the provided ReflexAgent in multiAgents.py:
python pacman.py -p ReflexAgent 
Note that it plays quite poorly even on simple layouts:
python pacman.py -p ReflexAgent -l testClassic
Inspect its code (in multiAgents.py) and make sure you understand what it's doing.
Question 1 (2 points): Reflex Agent
Improve the ReflexAgent in multiAgents.py to play respectively. The provided reflex agent code
provides some helpful examples of methods that query the GameState for information. A
capable reflex agent will have to consider both food locations and ghost locations to perform
well. Your agent should easily and reliably clear the testClassic layout:
python pacman.py -p ReflexAgent -l testClassic
Try out your reflex agent on the default mediumClassic layout with one ghost or two (and
animation off to speed up the display):
python pacman.py --frameTime 0 -p ReflexAgent -k 1
python pacman.py --frameTime 0 -p ReflexAgent -k 2
How does your agent fare? It will likely often die with 2 ghosts on the default board, unless
your evaluation function is quite good.
Note: As features, try the reciprocal of important values (such as distance to food) rather than
just the values themselves.
Note: The evaluation function you're writing is evaluating state-action pairs; in later parts of the
project, you'll be evaluating states.
Options: Default ghosts are random; you can also play for fun with slightly smarter directional
ghosts using -g DirectionalGhost. If the randomness is preventing you from telling whether your
agent is improving, you can use -f to run with a fixed random seed (same random choices
every game). You can also play multiple games in a row with -n. Turn off graphics with -q to
run lots of games quickly.
Grading: we will run your agent on the openClassic layout 10 times. You will receive 0 points if
your agent times out, or never wins. You will receive 1 point if your agent wins at least 5 times,
or 2 points if your agent wins all 10 games. You will receive an addition 1 point if your agent's 
average score is greater than 500, or 2 points if it is greater than 1000. You can try your agent
out under these conditions with
python autograder.py -q q1
To run it without graphics, use:
python autograder.py -q q1 --no-graphics
Don't spend too much time on this question, though, as the meat of the project lies ahead.
Question 2 (2 points): Minimax
Now you will write an adversarial search agent in the provided MinimaxAgent class stub in
multiAgents.py. Your minimax agent should work with any number of ghosts, so you'll have to
write an algorithm that is slightly more general than what you've previously seen in lecture. In
particular, your minimax tree will have multiple min layers (one for each ghost) for every max
layer.
Your code should also expand the game tree to an arbitrary depth. Score the leaves of your
minimax tree with the supplied self.evaluationFunction, which defaults to
scoreEvaluationFunction. MinimaxAgent extends MultiAgentSearchAgent, which gives access to
self.depth and self.evaluationFunction. Make sure your minimax code makes reference to these
two variables where appropriate as these variables are populated in response to command line
options.
Important: A single search ply is considered to be one Pacman move and all the ghosts'
responses, so depth 2 search will involve Pacman and each ghost moving two times.
Grading : We will be checking your code to determine whether it explores the correct number of
game states. This is the only way reliable way to detect some very subtle bugs in
implementations of minimax. As a result, the autograder will be very picky about how many
times you call GameState.generateSuccessor. If you call it any more or less than necessary, the
autograder will complain. To test and debug your code, run
python autograder.py -q q2
This will show what your algorithm does on a number of small trees, as well as a pacman game.
To run it without graphics, use: 
python autograder.py -q q2 --no-graphics
Hints and Observations
● The correct implementation of minimax will lead to Pacman losing the game in some tests.
This is not a problem: as it is correct behaviour, it will pass the tests.
● The evaluation function for the pacman test in this part is already written
(self.evaluationFunction). You shouldn't change this function, but recognize that now we're
evaluating *states* rather than actions, as we were for the reflex agent. Look-ahead agents
evaluate future states whereas reflex agents evaluate actions from the current state.
● The minimax values of the initial state in the minimaxClassic layout are 9, 8, 7, -492 for
depths 1, 2, 3 and 4 respectively. Note that your minimax agent will often win (665/1000
games for us) despite the dire prediction of depth 4 minimax.
python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4
● Pacman is always agent 0, and the agents move in order of increasing agent index.
● All states in minimax should be GameStates, either passed in to getAction or generated via
GameState.generateSuccessor. In this project, you will not be abstracting to simplified states.
● On larger boards such as openClassic and mediumClassic (the default), you'll find Pacman to
be good at not dying, but quite bad at winning. He'll often thrash around without making
progress. He might even thrash around right next to a dot without eating it because he
doesn't know where he'd go after eating that dot. Don't worry if you see this behavior,
question 5 will clean up all of these issues.
● When Pacman believes that his death is unavoidable, he will try to end the game as soon as
possible because of the constant penalty for living. Sometimes, this is the wrong thing to do
with random ghosts, but minimax agents always assume the worst:
python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3
Make sure you understand why Pacman rushes the closest ghost in this case.
Submission
Please submit your final implementation python files:
search.py and searchAgents.py for Search:Q7
 multiAgents.py for Multi-Agent Q1 and Q2 through OWL.
Please do not change the other files in this distribution or submit any of our
original files other than the expected files. 
Part 2: (8%)
1. Games:
1. Consider the zero-sum game tree shown below. Triangles that point up, such as
at the top node (root), represent choices for the maximizing player; triangles that
point down represent choices for the minimizing player. Assuming both players act
optimally, fill in the minimax value of each node.
2. Which nodes can be pruned from the game tree above through alpha-beta
pruning? If no nodes can be pruned, explain why not. Assume the search goes
from left to right; when choosing which child to visit
first, choose the left-most unvisited child.
3. Again, consider the same zero-sum game tree, except that now, instead of a
minimizing player, we have a chance node that will select one of the three values
uniformly at random. Fill in the expectimax value of each node. Redraw the game
tree below to show your answer.
4. Which nodes can be pruned from the game tree above through alpha-beta
pruning? If no nodes can be pruned, explain why not.
2. CSPs: Trapped Pacman
Pacman is trapped! He is surrounded by mysterious corridors, each of which leads
to either a pit (P), a ghost (G), or an exit (E). In order to escape, he needs to figure
out which corridors, if any, lead to an exit
and freedom, rather than the certain doom of
a pit or a ghost. The one sign of what lies
behind the corridors is the wind: a pit
produces a strong breeze (S) and an exit
produces a weak breeze (W), while a ghost
doesn’t produce any breeze at all.
Unfortunately, Pacman cannot measure the
strength of the breeze at a specific corridor.
Instead, he can stand between two adjacent
corridors and feel the max of the two
breezes. For example, if he stands between a
pit and an exit he will sense a strong (S) breeze, while if he stands between an exit
and a ghost, he will sense a weak (W) breeze. The measurements for all
intersections are shown in the figure below. Also, while the total number of exits
might be zero, one, or more, Pacman knows that two neighboring squares will not
both be exits.
Pacman models this problem using variables Xi for each corridor i and domains P, G,
and E.
1. State the binary and/or unary for this CSP (either implicitly or explicitly).
2. Cross out the values from the domains of the variables that will be deleted in
enforcing arc consistency.
3. According to MRV, which variable or variables could the solver assign first?
4. Assume that Pacman knows that X6 = G. List all the solutions of this CSP or
write none if no solutions exist.
Submission
Please submit your final answers in a PDF file through the OWL. ( Please note you will
not receive grades if TA can not recognize your handwriting, please finalize your
solutions clearly and neatly and transform it to be a PDF version. )