PROJECT 1: SEARCH IN PACMAN

All those colored walls, Mazes give Pacman the blues, So teach him to search. Introduction In this project, your Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. 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, andsome of which you can ignore. You can download all the code and supporting files as a zip archive. Files you'll edit: search.py Where all of your search algorithms will reside. searchAgents.py Where all of your search-based agents will reside. Files you might want to look at: pacman.py The main file that runs Pacman games. This file describes a Pacman GameState type, which you use in this project. 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 you can ignore: 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

Finding a Fixed Food Dot using Search Algorithms In searchAgents.py, you'll find a fully implemented SearchAgent, which plans out a path through Pacman's world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented -- that's your job. As you work through the following questions, you might find it useful to refer to the object glossary (the second to last tab in the navigation bar above). First, test that the SearchAgent is working correctly by running: python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm, which is implemented in search.py. Pacman should navigate the maze successfully. 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. Remember that a search node must contain not only a state but also the information necessary to reconstruct the path (plan) which gets to that state. Important note: All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls). 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. Your code should quickly find a solution for: python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent python pacman.py -l bigMaze -z .5 -p SearchAgent The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal? Hint: If you use a Stack as your data structure, the solution found by your DFS algorithm for mediumMazeshould have a length of 130 (provided you push successors onto the fringe in the order provided by getSuccessors; you might get 244 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.