Pacman has a chance to learn the lay of the land.
A Pacman agent needs to efficiently find paths through a maze, either to reach a particular location or collect remaining food quickly. In this project, you will build general search algorithms and apply them to Pacman scenarios.
The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignor for now. You can download the code and supporting files as a zip archive.
|Key files to read:|
|search.py||Where all of your search algorithms will reside.|
|searchAgents.py||Where all of your search-based agents will reside.|
|pacman.py||The main file that runs Pacman games. This file also describes a Pacman GameState type, which you will use extensively for the Pacman projects|
|game.py||The logic behind how the Pacman 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 Pacman|
|graphicsUtils.py||Support for Pacman graphics|
|textDisplay.py||ASCII graphics for Pacman|
|ghostAgents.py||Agents to control ghosts|
|keyboardAgents.py||Keyboard interfaces to control Pacman|
|layout.py||Code for reading layout files and storing their contents|
What to submit: You will fill in portions of
searchAgents.py during the assignment. You should submit these two files (only) along with a
partners.txt file. Directions for submitting and setting up your account are on the course website.
Evaluation: Your code will be graded for technical correctness with the help of an autograder. Please do not change the names of any functions within the code, or you will wreak havoc on the autograder. Your answers to various rhetorical written questions in this document need not be handed in.
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. Our cheat detector is 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.
python pacman.pyPacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman's first step in mastering his domain.
The simplest agent in searchAgents.py is called the
GoWestAgent, which always goes West (a trivial reflex agent). This agent can occasionally win:
python pacman.py --layout testMaze --pacman GoWestAgentBut, things get ugly for this agent when turning is required:
python pacman.py --layout tinyMaze --pacman GoWestAgentNote:
pacman.pysupports a number of options that can each be expressed in a long way (e.g.,
--layout) or a short way (e.g.,
-l). You can see the list of all options and their default values via:
python pacman.py -h
Question 0 (not graded) For practice, fill in code for
TinyMazeAgent so that it can solve tinyMaze. Your agent should follow the
Agent interface in
game.py, implementing a function called
getAction. Your code can be entirely tailored to this single scenario, but the agent should win it:
python pacman.py --layout tinyMaze --pacman TinyMazeAgent
Now that you've gotten your feet wet, we'll solve the problem of efficiently getting Pacman from one place to another. The layouts
testMaze, tinyMaze, mediumMaze and
bigMaze all have only one piece of food in the bottom-left corner. The job of your agents will be to navigate to that dot (and eat it). The problem of finding a path to some goal position is cast into a general search framework in
PositionSearchProblem in searchAgents.py. Make sure you understand this code.
Now it's time to write full-fledged generic search functions to help Pacman plan routes! Pseudocode for the search algorithms you'll write can be found in the lecture slides and textbook. Remember that a search node must contain not only a state but also the information necessary to reconstruct the path (plan) to that state.
Important note: All of your search functions (questions 1, 2, 3, 4 & 6) need to return a three-item tuple containing:
Hint: Each algorithm is very similar. Algorithms for DFS, BFS, UCS, and A* differ only in the details of how the fringe is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit).
Hint: Make sure to check out the
Stack, Queue and
PriorityQueue types provided to you in
Question 1 (2 points) Implement the depth-first search (DFS) algorithm in the
depthFirstSearch function in search.py. To make your algorithm complete, write the graph search version of DFS, which avoids expanding any already visited states (textbook section 3.5).
Your code should quickly find a solution for:
python pacman.py -l tinyMaze -p DepthFirstSearchAgent
python pacman.py -l mediumMaze -p DepthFirstSearchAgentWhen you run a search agent using
PositionSearchProblem, the Pacman board will show an overlay of the positions explored and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected?
Hint: The solution found by your DFS algorithm for
mediumMaze should have a length of 162 (provided you push successors onto the fringe in the order provided by getSuccessors; you might get 264 if you push them in the reverse order). Is this a least cost solution? If not, think about what depth-first search is doing wrong?
Question 2 (2 point) Implement the breadth-first search (BFS) algorithm in the
breadthFirstSearch function in search.py. Again, write a graph search algorithm that avoids expanding any already visited states. Test your code the same way you did for depth-first search.
python pacman.py -l mediumMaze -p BreadthFirstSearchAgent
python pacman.py -l bigMaze -p BreadthFirstSearchAgent -z .5Does BFS find a least cost solution? If not, check your implementation.
mediumScaryMaze. We can use varying cost functions provided to cause differing paths through these mazes to have least weighted cost. For example, we can charge more for dangerous steps in ghost-ridden areas or less for steps in food-rich areas, and a rational Pacman agent should adjust its behavior in response.
Question 3 (3 points) Implement the uniform-cost graph search algorithm in
uniformCostSearch function in search.py. You should now observe different behavior in all three of these conditions, where the agents below are all UCS agents which differ only in the cost function they (the agents and cost functions are written for you):
python pacman.py -l mediumMaze -p UniformCostSearchAgent
python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
searchAgents.py. A solution will now be a series of actions that collects all of the food in the Pacman game. Such a solution will not change if there are ghosts or power pellets in the game; it only depends on the placement of walls, food and Pacman, though of course ghosts can ruin the execution of a solution! If you have written your general search methods correctly, the
UniformCostFoodSearchAgentshould quickly find optimal solutions to testSearch with no code change on your part.
python pacman.py -l testSearch -p UniformCostFoodSearchAgentWhile your UCS code may be correct on this problem, it will not scale very well. You should find that UCS starts to slow down even with the seemingly simple
tinySearch. As a reference, our implementation takes 10 seconds to find a path of length 27 after expanding 4902 search nodes. Why does such a tiny board give rise to such a large search problem? We'll turn to A* to help us scale up while keeping our agent optimal.
Question 4 (3 points) Implement A* graph search in the empty function
aStarSearch in search.py. You will need to pass a heuristic function into
aStarSearch upon construction. The heuristic function should take one argument: a state in the search problem. See the
nullHeuristic heuristic function in
search.py for an example.
You can test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic. The appropriate classes are already written for you (and their structure should serve as an example for question 6). Notice that this particular heuristic must be configured with the goal location, and so our code bundles up a custom heuristic for each problem instance using functional closures. Run the following to test your A* agent:
python pacman.py -l bigMaze -p ManhattanAStarSearchAgent -z .5You should see that A* finds the optimal solution slightly faster than uniform cost search (549 vs. 621 search nodes expanded in our implementation). What happens on
openMazefor the various search strategies?
On this simple path-to-point problem, A* doesn't really help much, since the search space is so tiny. The real power of A* will only be apparent with the more challenging
FoodSearchProblem. Here, UCS grinds to a halt and well-designed heuristics are king.
Question 5(a) (5 points) Write an
FoodSearchProblem in one of two places in
searchAgents.py. You may fill in
foodHeuristic or you may fill in
getFoodHeuristic (for more flexibility in designing complex heuristics). Then,
Question 5(b) (2 points) Fill in
AStarFoodSearchAgent so that is runs A* using the
python pacman.py -l trickySearch -p AStarFoodSearchAgentOur UCS agent finds the optimal solution in about 60 seconds, exploring 16749 nodes. Our A* agent solves the problem optimally in about 2 seconds, exploring 410 nodes. See how well you can do. Can you solve
mediumSearchin a short time? If so, we're either very, very impressed, or your heuristic is inadmissible. Note: Question 5 will be graded in part on how fast you can solve search problems, and in part on whether or not your heuristic is admissible. Think through admissibility carefully as inadmissible heuristics may manage to produce fast searches and optimal paths.
Sometimes, even with A*, finding the optimal path through all the dots is just too hard. In these cases, we'd still like to find a reasonably good path, quickly. Greedy search is can be a good option here:
Question 6 (2 points) Implement greedy graph search in the empty function
greedySearch in search.py. Again, you will need to pass in a heuristic function. Then, fill in
GreedyFoodSearchAgent. With a simple heuristic, our implementation solves the following using a path of 350 steps:
python pacman.py -l bigSearch -p GreedyFoodSearchAgent -z .5With a better heuristic (closer to the truth), ours finds a solution of less than 300 steps. Your heuristic for greedy search need not be any different from your A* heuristic.
Question 7(a) (3 points) Define a new search problem in
SafeSearchProblem (searchAgents.py). The search problem should replicate
FoodSearchProblem in that the goal is to eat all of the food. However, the successor function should specify that a move is only legal if there is either a capsule in the square moved to, or the ghosts are still scared from the last capsule. Eating a capsule scares the ghost for a specified number of moves (see
searchAgents.py).* Once you define the search problem, you should quickly find solutions to:
python pacman.py -l tinySafeSearch -p SafeSearchAgent
python pacman.py -l smallSafeSearch -p SafeSearchAgent
* Note: when ghosts are already scared and Pacman eats another capsule, their scared time resets to its maximum (default 40, see code). Scared time is not additive, so eating two capsules in a row can be a waste of resources.
Question 7(b) (2 points) Now, write a more efficient
SafeSearchAgent that can quickly find solutions to
bigSafeSearch (i.e., less than a minute of searching). Supplying the greedy search algorithm with the right heuristic should do the trick.
python pacman.py -l mediumSafeSearch -p SafeSearchAgent
python pacman.py -l bigSafeSearch -p SafeSearchAgentOur agent finds a solution to
bigSafeSearchin less than a second.
Congratulations! You've finished the first project. Now Pacman is ready to take on some ghosts for real...