Project 1.3: Multi-Agent Pacman

Due 9/29 at 11:59pm
Update 9/23, 7pm: modified to correct ordering bug.

Pacman, now with ghosts.
Minimax, Expectimax,


In this checkpoint, you will design agents for the full version of Pacman, including ghosts. Along the way, you will implement both minimax and expectimax search and try your hand at evalution function design.

The code base has not changed significantly from the previous project, but please start with a fresh installation of this code for the project, rather than intermingling files from previous checkpoints. The code for this project contains the following files, available as a zip archive.

Pacman The main code for the game of Pacman. You should familiarize yourself with the general outline of this code, which you will be interacting with for the rest of Project 1. Board layouts. You can ignore this file. Interactive controller. You can ignore this file. Plug-in for the gui interface. You can ignore this file. Plug-in for the text interface. You can ignore this file. Graphics utilities. You can especially ignore this file.
Search Generic search code, including our solution to checkpoint 1.1.  You may use this, or your own search code. Useful data structures for implementing search algorithms (from 1.1).
Agents A home for your Pacman agents, and the file you will be editing. Don't ignore this file.


What to submit: You will fill in portions of during the assignment. You should submit this file with your code and comments. If you change other files, submit those as well. You need not submit a readme unless you want to.

Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. Your answers to discussion questions will also be graded.

Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don't try. We trust you all to submit your own work only; please don't let us down. Instead, contact the course staff if you are having trouble.


Multi-Agent Pacman

Question 1 (3 points)  Extend your reflex pacman agent from checkpoint 1.2 to play in the presence of ghosts (in the provided ReflexPacmanAgent class stub in the file  As before, your agent should use the state's generatePacmanSuccessor(action) function to obtain the possible result states, score the result states using a real-valued evaluation function, and select the action with the highest-scoring result. To facilitate checkpoint 1.4, in which you will learn evaluation function weights, you may wish to write your evaluation function as a linear combination of features that you extract from the state under evaluation.

You can again load your reflex agent with the "-p reflex" option.  It should be able to play reasonably well on the default board with one (or even two) ghosts. You can control the number of ghosts with the "-k" command line option. 

    python -p reflex -k 1

Note that you can never have more ghosts than the layout permits. Your agent will likely often die with 2 or more ghosts on the default board, unless your evaluation function is quite good.

The autograder will check that your agent can rapidly clear the open adversarial layout ("-l openAdversarial") without dying. Don't spend too much time on this question, though, as the meat of the project lies ahead.

Question 2 (5 points) Now you will write an adversarial search agent in the provided MinimaxPacmanAgent class stub in 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 appears in the textbook. In particular, your minimax tree will have multiple min layers (one for each ghost) for every max layer.

Your agent should use the __init__ function provided, which specifies an evaluation function and a search depth. When using this depth, remember that 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. Hence, the reflex agent in question 1 is not a full one-ply minimax agent, but instead a "partial-ply" searcher.

Score the leaves of your minimax tree with the function provided (self.evaluationFunction), which simply returns the score of the state by default (scoreEvaluationFunction in the code). Check your agent on the testAdversarial layout. You should have no problem clearing it with either one or two ghosts, which are either random or directional. Directional ghosts seek pacman with some probability; random ghosts do not. Experiment with various depths. Higher depths should produce visibly better play, but require much more planning time.

To increase the search depth achievable by your pacman agent, remove the Directions.STOP action from Pacman's list of possible actions. Don't fret if you still can't search past depth 3; the next question will speed up the search.

The code gives you many options to allow for easy testing and experimentation. Use the option "-p minimax" to load your minimax agent. You can specify the depth passed to this constructor using the "-d" command line option. You can control the ghosts' agent function with the "-g random" and "-g directional" options, and control the number of ghosts with "-k". Run "python --help" for more details.

The functions you'll need to call for each state are similar to those you used for the previous project. Note that you can get the number of agents from state.getNumAgents(). Pacman is always agent 0, and the agents move in increasing number. Functions are provided to get legal moves for pacman or the ghosts and to execute a move by any agent. Note that state.score is not part of the equality condition for game states, but is available for you to use at evaluation. If some piece of information seems not to be available to you that you would like to know, please post to the newsgroup from the course website.

Your minimax agent should clear the testAdversarial layout handily. On larger boards such as openAdversarial and medium (the default), you'll find Pacman to be good at not dying, but quite bad at winning.

Question 3 (3 points) Modify your minimax agent to use alpha-beta pruning ("-p alphaBeta") in the AlphaBetaPacmanAgent class stub. You should see a substantial speed-up. Make sure your depth of search still matches the depth passed on construction. Again, your algorithm will be slightly more general than the pseudo-code in the textbook, so part of the challenge is to extend the alpha-beta pruning logic appropriately to multiple minimizer agents.

Question 4 (3 points) Random ghosts are of course not optimal minimax agents, and modeling them with minimax search may not be appropriate. Create an expectimax agent ("-p expectimax") in the ExpectimaxPacmanAgent class stub. 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 you will only be running against random ghosts, which choose amongst their getLegalActions uniformly at random (option "-g random").

Question 5 (6 points) Write a better evaluation function for pacman in the provided function betterEvaluationFunction. You can load this evaluation function from the command line with the "-e betterEvaluationFunction" option. In fact, you can load any evaluation function this way just by naming it. Your function can take any form, but you'll save yourself some work on 1.4 if you make it a linear combination of features as we discussed in class. With depth 2 search, your evaluation function should clear the default layout with two random ghosts more than half the time for full credit. The autograder will run multiple games and bound your average win rate.

Document your evaluation function! You will be graded both on the performance of your evaluation function and the ingenuity of what you tried. We're very curious about what great ideas you have, so don't be shy. To reward you with everlasting glory, we will announce the highest scoring entries in lecture.

Go Pacman!