Pacman Search

# Teach Pacman how to intelligently find his food in the shortest time possible!

Many problems in AI can be solved in theory by intelligently searching through many possible solutions: reasoning can be reduced to performing a search. For example, logical proof can be viewed as searching for a path that leads from premises to conclusions, where each step is the application of an inference rule. Planning algorithms search through trees of goals and subgoals, attempting to find a path to a target goal, a process called means-ends analysis. Simple exhaustive searches are rarely sufficient for most real world problems: the search space (the number of places to search) quickly grows to astronomical numbers. The result is a search that is too slow or never completes. The solution, for many problems, is to use "heuristics" or "rules of thumb" that eliminate choices that are unlikely to lead to the goal (called "pruning the search tree"). In this project, we will explore a few fundamental search algorithms (DFS, BFS, UCS, A*), and apply them to Pacman scenarios. The goal of the Pacman agent will be to find paths through his maze world (void of ghosts), both to reach a particular location and to collect food efficiently.

# Depth-First Search

Notes:
- Implemented using a graph search version of DFS; avoids expanding already visited states.
- Search algorithm is complete (finds some goal).
- The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration).
- The fringe is managed using a stack data structure.

Notes:
- Again, uses a graph search algorithm that avoids expanding any already visited states.
- Implemented using a graph search version of DFS; avoids expanding already visited states.
- Code is generic - can be used for puzzle solving algorithms.

# Uniform-Cost Search

Notes:
- BFS finds the fewest-actions path to the goal, we might want to find paths that are "best" in other senses.
- By changing the cost function, we can encourage Pacman to find different paths. 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.
- Left image: original BFS algorithm.
- Right image: modified with UCS cost-function algorithm.

# A* Search

Notes:
- A* implemented to take a heuristic function as an argument.
- A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic.
- Finds the optimal solution slightly faster than uniform cost search in the maze (about 549 vs. 620 search nodes).

Corners Search Problem:
- In corner mazes, there are four dots, one in each corner. The search problem is to find the shortest path through the maze that touches all four corners (whether the maze actually has food there or not).
- A* implementation is used with a Manhattan distance heuristic.
- Finds the optimal solution much faster than BFS.