Project 1: Search in Pacman

Due 9/12 at 11:59pm

Pacman has a chance to learn the lay of the land.

Introduction

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.
Supporting files:
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 search.py and 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.

Welcome to Pacman

First, check to see that your python installation is working. You should be able to play a game of Pacman by typing the following from the command line:
python pacman.py
Pacman 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 GoWestAgent
But, things get ugly for this agent when turning is required:
python pacman.py --layout tinyMaze --pacman GoWestAgent
Note: pacman.py supports 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

Finding a Fixed Food Dot using Search Algorithms

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:

  1. Path: The sequence of search states that connect the start to the goal
  2. Actions: The sequence of actions the agent takes to follow that path
  3. Total cost: the total cost of the path

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 util.py!

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 DepthFirstSearchAgent
When 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 .5
Does BFS find a least cost solution? If not, check your implementation.

Varying the Cost Function

While BFS will find a fewest-actions path to the goal, we might want to find paths that are "best" in other senses. Consider mediumDottedMaze and 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 the 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

Eating All The Dots

Now we'll solve a much harder search problem: eating all the Pacman food in as few steps as possible. For this, we'll need a new search problem definition which formalizes the food-clearning problem. This formalization is provided for you in FoodSearchProblem in 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 UniformCostFoodSearchAgent should quickly find optimal solutions to testSearch with no code change on your part.
python pacman.py -l testSearch -p UniformCostFoodSearchAgent 
While 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 .5 
You 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 openMaze for 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 admissible heuristic for a 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 admissible heuristic you designed. Try your agent on the trickySearch board:

python pacman.py -l trickySearch -p AStarFoodSearchAgent
Our 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 mediumSearch in 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 .5 
With 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.

What about Ghosts?

The planning agents you have built so far make all of their decisions before the game even begins. But, who knows what those pesky ghosts will do to get in our way. In this last question, we'll continue to ignore the ghosts, but make sure to eat enough capsules (power pellets) to keep the ghosts scared of us while we collect all the food.

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 mediumSafeSearch and 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 SafeSearchAgent 
Our agent finds a solution to bigSafeSearch in less than a second.

Congratulations! You've finished the first project. Now Pacman is ready to take on some ghosts for real...