[SOLVED] Assignment 5. multi-agent pac-man csed342

Introduction
Figure 1: Pac-Man, now with ghosts.
For those of you not familiar with Pac-Man, it’s a game where Pac-Man (the yellow circle
with a mouth in the above figure) moves around in a maze and tries to eat as many food
pellets (the small white dots) as possible, while avoiding the ghosts (the other two agents
with eyes in the above figure).If Pac-Man eats all the food in a maze, it wins. The big white
dots at the top-left and bottom-right corner are capsules, which give Pac-Man power to eat
ghosts in a limited time window (but you won’t be worrying about them for the required
part of the assignment). You can get familiar with the setting by playing a few games of
classic Pac-Man, which we come to just after this introduction.In this project, you will design agents for the classic version of Pac-Man, including ghosts.
Along the way, you will implement various search strategies.Files
• submission.py : Where all of your multi-agent search agents will reside and the only
file you need to concern yourself with for this assignment.• pacman.py : The main file that runs Pac-Man games. This file also describes a
Pac-Man GameState type, which you will use extensively in this project
• game.py : The logic behind how the Pac-Man world works. This file describes several
supporting types like AgentState, Agent, Direction, and Grid.• util.py : Useful data structures for implementing search algorithms.
• graphicsDisplay.py : Graphics for Pac-Man
• graphicsUtils.py : Support for Pac-Man graphics
• textDisplay.py : ASCII graphics for Pac-Man
• ghostAgents.py : Agents to control ghosts
• keyboardAgents.py : Keyboard interfaces to control Pac-Man
• layout.py : Code for reading layout files and storing their contentsWarmup
First, play a game of classic Pac-Man to get a feel for the assignment:
python pacman.py
You can always add –frameTime 1 to the command line to run in ”demo mode” where
the game pauses after every frame.Now, run the provided ReflexAgent in submission.py:
python pacman.py -p ReflexAgent
Note that it plays quite poorly even on simple layouts:
python pacman.py -p ReflexAgent -l testClassic
You can also try out the reflex agent on the default mediumClassic layout with one ghost
or two.
python pacman.py -p ReflexAgent -k 1
python pacman.py -p ReflexAgent -k 2Note: you can never have more ghosts than the layout permits.
Options: Default ghosts are random; you can also play for fun with slightly smarter
directional ghosts using -g DirectionalGhost. You can also play multiple games in a row
with -n. Turn off graphics with -q to run lots of games quickly.So, now that you are familiar enough with the interface, inspect the ReflexAgent code
carefully (in submission.py) and make sure you understand what it’s doing. The reflex agent
code provides some helpful examples of methods that query the GameState (a GameState
specifies the full game state, including the food, capsules, agent configurations and score
changes: see submission.py for further information and helper methods) for information,
which you will be using in the actual coding part. We are giving an exhaustive and very
detailed description below, for the sake of completeness and to save you from digging deeper
into the starter code. The actual coding part is very small – so please be patient if you think
there is too much writing.Note: if you wish to run Pac-Man in the terminal using a text-based interface, check out
the terminal directory.Before you code up Pac-Man as a minimax agent, notice that instead of just one adversary,
Pac-Man could have multiple ghosts as adversaries. So we will extend the minimax algorithm
from class (which had only one min stage for a single adversary) to the more general case
of multiple adversaries. In particular, your minimax tree will have multiple min layers (one
for each ghost) for every max layer.Specifically, consider the limited depth tree minimax search with evaluation functions
taught in class. Suppose there are n + 1 agents on the board, a0, . . . , an, where a0 is PacMan and the rest are ghosts. Pac-Man acts as a max agent, and the ghosts act as min agents.A single depth consists of all n + 1 agents making a move, so depth 2 search will involve
Pac-Man and each ghost moving two times. In other words, a depth of 2 corresponds to a
height of 2(n + 1) in the minimax game tree.First, design the recurrence for Vmax,min(s, d) in math. You should express the idea in
terms of the following functions: IsEnd(s), which tells you if s is an end state; Utility(s), the
utility of a state; Eval(s), an evaluation function for the state s; Player(s), which returns
the player whose turn it is; Actions(s), which returns the possible actions; and Succ(s, a),
which returns the successor state resulting from taking an action at a certain state. It would
be helpful to review the recurrence of depth-limited search in lecture notes.Problem 1a [2 points] ¥
Now fill out MinimaxAgent class in submission.py using the recurrence you designed. Remember that your minimax agent should work with any number of ghosts, and your minimax
tree should 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. The class 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 from the command line options.Other functions that you might use in the code: GameState.getLegalActions() which
returns all the possible legal moves, where each move is Directions.X for some X in the set
NORTH, SOUTH, WEST, EAST, STOP. Go through ReflexAgent code as suggested before to
see how the above are used and also for other important methods like GameState.getPacmanState(),
GameState.getGhostStates(), GameState.getScore() etc. These are further documented
inside the MinimaxAgent class.Hints and Observations
• The evaluation function 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 futurestates whereas reflex agents evaluate actions from the current state. Use self.evaluationFunction
in your definition of Vmax,min wherever you used Eval(s) in part 1a.• The minimax values of the initial state in the minimaxClassic layout are 9, 8, 7, -492
for depths 1, 2, 3 and 4 respectively. You can use these numbers to verify if
your implementation is correct. Note that your minimax agent will often win
(just under 50% of the time for us–be sure to test on a large number of games using
the -n and -q flags) despite the dire prediction of depth 4 minimax.python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4• Pac-Man is always agent 0, and the agents move in order of increasing agent index.
Use self.index in your minimax implementation, but only Pac-Man will actually be
running your MinimaxAgent.• Functions are provided to get legal moves for Pac-Man or the ghosts and to execute a
move by any agent. See GameState in pacman.py for details.
• 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.• getAction should use Vmax,min to determine the best action for Pac-Man.
• On larger boards such as openClassic and mediumClassic (the default), you’ll find
Pac-Man to be good at not dying, but quite bad at winning. He’ll often thrash around
without making progress. Don’t worry if you see this behavior.• Consider the following run:
python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3
Why do you think Pac-Man rushes the closest ghost in minimax search on trappedClassic?
• You can assume that you will always have at least one action from which to choose in
getAction.• If there is a tie between multiple actions for the best move, you may break the tie.
• getQ should return Qmax,min for the current state given action.Random ghosts are of course not optimal minimax agents, so modeling them with minimax
search is not optimal. Let’s assume that ghosts follow the uniform policy, therefore ghosts
take legal actions uniformly in any state. Before implementing it, first extend Expectimax
recurrence, so the algorithm considers multiple ghosts as opponents.Your recurrence should
resemble that of Problem 1aProblem 2a [2 points] ¥
Fill in ExpectimaxAgent, where your agent will no longer take the min over all ghost actions,
but the expectation according to your agent’s model of how the ghosts act. Assume Pac-Man
is playing against RandomGhosts, which each choose getLegalActions uniformly at random.
You should now observe a more cavalier approach to close quarters with ghosts. In particular, if Pac-Man perceives that he could be trapped but might escape to grab a few more
pieces of food, he’ll at least try:
python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3You may have to run this scenario a few times to see Pac-Man’s gamble pay off. PacMan would win half the time on an average and for this particular command, the final score
would be -502 if Pac-Man loses and 532 or 531 (depending on your tiebreaking method and
the particular trial) if it wins (you can use these numbers to validate your implementation).
Why does Pac-Man’s behavior in expectimax differ from the minimax case (i.e., why doesn’t
he head directly for the ghosts)?Now assume that policy ghosts follow is biased to select to stop (i.e. Directions.STOP).
Specifically, ghosts decide their next action according to the following distribution:
p(a∈A) = (
0.5 + 0.5 ∗
1
len(A)
for a = Directions.STOP
0.5 ∗
1
len(A)
elsewhere,
where A is a set of legal actions of a player from the current state.Problem 3a [6 points] ¥
Fill in BiasedExpectimaxAgent. This time, your agent should take the expectation over
ghosts’ biased action policy. Assume Pac-Man is playing against RandomGhosts which are
likely to choose to stop in place.Your agent now would show some foolish actions. In particular, Pac-Man sometimes rush
to the very-close ghost even though there are no benefits for the game score (i.e. food pellets):
python pacman.py -p BiasedExpectimaxAgent -l trappedClassic -a depth=3
Compared to the expectimax, the winning rate would still be half. The final score,
however, would change when Pac-Man loses: you will get -503 not -502. In case the game
loses, Pac-Man will stop to move between the two approaching ghosts before it dies. Do you
know why?In real world, it is not the best prediction that treating (if playing with multiple opponents)
all adversaries follow the same policy. From now on, you assume that ghosts are divided
into two groups of following either min policy or random policy. Specifically, the ghosts
with odd-number select the action for the minimum value and the ghosts with even-number
select the action randomly according to a certain distribution. For the simplicity of your
implementation, suppose the action chosen by even-numbered ghosts are from uniform distribution.Problem 4a [4 points] ¥
Fill in ExpectiminimaxAgent, where your agent will take the min over half of the ghosts
and the expectation over others. Assume Pac-Man is playing against RandomGhosts, some
choosing the worst action for Pac-Man and others uniformly randomly choosing the action:
python pacman.py -p ExpectiminimaxAgent -l minimaxClassic -a depth=4
The expectiminimax values of the initial state in the minimaxClassic layout are almost
similar to the minimax values. They would be 9.0, 8.0, 7.0 and 263.75 for depths 1, 2, 3 and
4 respectively. Why the values for the expectiminimax and minimax are same for depths 1,
2 and 3 but differ for depth 4?Problem 5a [8 points] ¥
Make a new agent that uses alpha-beta pruning to more efficiently explore the expectiminimax tree, in AlphaBetaAgent. Again, your algorithm will be slightly more general than the
pseudo-code in the slides, so part of the challenge is to extend the alpha-beta pruning logic
appropriately to multiple expectiminimizer agents.You should see a speed-up. Ideally, depth 3 on mediumClassic should run in just a few
seconds per move or faster.
python pacman.py -p AlphaBetaAgent -a depth=3
The AlphaBetaAgent expectiminimax values should be identical to the ExpectiminimaxAgent
expectiminimax values, although the actions it selects can vary because of different tiebreaking behavior. Again, the expectiminimax values of the initial state in the minimaxClassic
layout are 9.0, 8.0, 7.0, and 263.75 for depths 1, 2, 3, and 4, respectively. Running the command given above this paragraph, the expectiminimax values of the initial state should be
9.0, 18.0, 27.0, and 36.0 for depths 1, 2, 3, and 4, respectively.Problem 6a [8 points] ¥
Write a better evaluation function for Pac-Man in the provided function betterEvaluationFunction.
The evaluation function should evaluate states (rather than actions). You may use any tools
at your disposal for evaluation, including any util.py code from the previous assignments.After implementing it, choose the Pac-Man agent model to be used for the test. You
can choose among the agents you’ve implemented in Problem 1-5 or design your own agent
model. You can test your code with:
python pacman.py -l smallClassic -p ExpectimaxAgent -a evalFn=better -q -n 20
python pacman.py -l smallClassic -p MyOwnAgent -a evalFn=better -q -n 20
We will run your Pac-Man agent 20 times, and calculate the average score you obtained.If your average score is less than 1000, you’ll get no point. If your average score is more than
1500, you’ll get 8 points. Check the grader.py to see how the scores are calculated.Hints and Observations
• Having gone through the rest of the assignment, you should play Pac-Man again yourself and think about what kinds of features you want to add to the evaluation function.
How can you add multiple features to your evaluation function?• You may want to use the reciprocal of important values rather than the values themselves for your features (such as distances between Pac-Man and ghosts).
• For your information, our solution code gets more than 1600 scores in average with
various random seeds.