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.
||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.|
||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).|
||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.
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 pacman.py -l tinySearch
You can look in
layout.py 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 pacman.py -l testSearch -p
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.
RandomPacmanAgent class in
pacmanAgent.py to see how the
PacmanAgent interface works. Your agents need to respond to the single
getAction(state), which should return one of the legal actions from the given
States provide many accessor functions, which are detailed in
pacman.py. In particular, you can get the legal actions from a state using
random agent calls this method and selects an actions randomly. If you return an illegal
action, the game will end with an exception.
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 pacman.py -p reflex -l openSearch
However, it will likely have problems with the layout "trickySearch", unless it's implicitly searching.
python pacman.py -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.
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
pacmanAgent.py. Make sure your agent can clear the board "testSearch"
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
method provided in
searchAgent.py ("-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
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").