Project 1.2: Single-Agent Pacman

Due 9/19 at 11:59pm
Critical update 9/12, 7pm: modified base code, changed question 3 targets.

Update 9/15, 10am: fixed .

Pacman without ghosts
A* search and heuristics
Eat up all the dots


In this checkpoint, you will design agents for a simplified version of Pacman in which there are no ghosts, applying various techniques from lecture, including A* search and heuristic design.

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.


What to submit: You will fill in portions of during the assignment. You should submit this file along with a text or pdf file containing answers to the discussion questions. If you change other files, submit those as well.

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.


Welcome to Pacman

Your first task is to play some Pacman interactively, to familiarize yourself with the game and make sure you're correctly set up.  Begin by putting the project files in a new working directory and typing in that directory:


Control keys are 'a', 's', 'd', and 'w'; depending on your setup, the arrow keys may also work.  Note that CS188 Pacman is different from the classic game in several respects.  One important difference is that you lose points for sitting around.

You can also try out the single-agent board with

    python -l tinySearch

You can look in and to see which layouts are available, and, if you want, construct your own.  Many command line options exist.  You can get a list with the "-h" option.

Next, you will switch control from your interactive keyboard agent to a random agent, using the following command:

    python -l testSearch -p random

Even the random agent should clear this trivial board.  On the larger single-agent boards, the random agent will wander around and accomplish little; on the multi-agent boards he will be eaten relatively quickly.

Inspect the RandomPacmanAgent class in to see how the PacmanAgent interface works.  Your agents need to respond to the single method getAction(state), which should return one of the legal actions from the given state.  States provide many accessor functions, which are detailed in  In particular, you can get the legal actions from a state using state.getLegalPacmanActions().  The random agent calls this method and selects an actions randomly.  If you return an illegal action, the game will end with an exception.


Single-Agent Pacman

Now that you've seen a bad pacman agent, you will write some better ones.  In this checkpoint, you will work with the single-agent boards, where your pacman does not need to worry about ghosts.

Question 1 (4 points)  Write a reflex pacman agent in the provided ReflexPacmanAgent class stub in the file  A strict reflex agent would react directly to the state, without computing the results of the available actions.  However, to make your reflex agent more compatible with future checkpoints, 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.

You can load your reflex agent with the "-p reflex" option.  It should be able to clear the open layout given by the command line option "-l openSearch". 

    python -p reflex -l openSearch

However, it will likely have problems with the layout "trickySearch", unless it's implicitly searching. 

    python -p reflex -l trickySearch

The autograder will check that your agent can rapidly clear the open layout from several starting positions.  Your reflex agent should not use search, and can ignore ghosts entirely for now.  If you like, see if you can make a better reflex agent which solves the tricky board (not needed for full credit).

Question 2 (3 points) Now you will write a planning agent in the provided AStarSearchPacmanAgent class stub, which takes a heuristic function on construction.  Your planning agent should use A* search to find an optimal sequence of actions which clear the board with the highest possible score, then execute that plan (blindly, without replanning).  Note that the search problem is not neatly packaged for you like it was in Mazeworld, and you will have to learn a little about the provided code to bundle it up.  The state.getLegalPacmanActions(state) will return the actions Pacman can take in the current state.  The states resulting from these actions are given by state.getPacmanSuccessor(action).  The cost should be 1.0 for all actions, not the score change resulting from the action.  Convince yourself that a lowest cost solution in path length will also be a highest scoring one in points.  Why don't we want to use the change in score as a cost?  You will probably want to create a SearchProblem subclass for the board-clearing task.

Try your A* agent with the trivial zeroHeuristic, provided in  Make sure your agent can clear the board "testSearch" with the zeroHeuristic ("-p ucs").  The autograder will test your agent on a new board with a staff heuristic, so make sure not to change the constructor signature. We have provided code containing our solutions for 1.1. You may of course reuse your own code rather than use ours. 

Question 3 (5 points) Try your A* planning agent on the "tinySearch" layout with the zero heuristic.  Even on a board this small, the search will be fairly slow.  To improve your agent's efficiency, design a better heuristic in the betterHeuristic(state) method provided in ("-p aStar").  We will check your heuristic for admissibility, and the resulting agent for optimality.  Better heuristics will get more credit. A full credit solution should be able to clear the tinySearch board while calling getSuccessor() on fewer than 3000 states.  Under 6000 should be easy to achieve and will receive most of the credit. Far less is possible. Make sure you comment your heuristic so we can tell what you did; we'll be announcing the best ones in lecture.

Question 4 (3 points) Your A* agent may be fast for very small boards, but it is unlikely to clear a large board in a reasonable time.  Your final Pacman task is to build an agent in FastSearchPacmanAgent ("-p fast") which will clear any board with relatively little computation.  Your agent, however, no longer needs to be optimal.  A good solution should be able to clear the "mediumSearch" and "bigSearch" layouts in well under a minute, though the exact timing is unimportant.  You may use any design you like.  Be warned: the autograder will try out your agent on a new board like "bigSearch", so try to create an agent which will you think will always clear any board.  Again, document your design so that we can announce the best solutions in lecture.  Note: an agent which clears any board eventually should be easy to write; an agent which clears any board with relatively few wasted steps will be much harder.  A full credit solution should clear "bigSearch" with a score of at least 2350 (if your agent is random, we'll run it a few times).

Question 5 (5 points) Assume that you are given a Mazeworld map with only walls and open squares (no water), and you wish to find a path from the start S to the exit E of length exactly k.  Formulate a CSP for which the solutions are the possible paths.  What are the variables, domains, and constraints?  How can you use this CSP to find a shortest path?  [Note: submit your answer in a text or pdf file. No written responses need to be submitted for questions 1-4.]


Congratulations, you're done with checkpoint 1.2!  If you're hungry for more Pacman, go ahead and try to design a reflex agent for the multi-agent game (use a layout with ghosts, such as "medium").