Brandon Ra
Faculty Sponsor: Raghu Ramanujan
In this research, we attempted to solve two different path-finding problems presented in the context of Ms. Pac-Man, utilizing various search algorithms. We then compared the effectiveness of each methods. Among them are: Breadth First Search (BFS), Depth First Search (DFS), A* algorithm, Iterative Deepening A* (IDA*), and Simplified Memory Bounded A* (SMA*). Our paper however primarily focuses on IDA* and SMA* and its effectiveness relative to the other algorithms. The first path-finding task is a simple maze problem where the Pac-Man agent has to find its way to a single food pellet on the map. The second task was the original Pac-Man game where the agent had to collect all the food on the map. The scores were based on how fast all of the food pellets were collected. Ghost agents were removed for simplicity. Our results, as expected, suggests that A* far out-performs other search algorithms.
n this research, we attempted to solve two different path-finding problems presented in the context of Ms. Pac-Man, utilizing various search algorithms. We then compared the effectiveness of each methods. Among them are: Breadth First Search (BFS), Depth First Search (DFS), A* algorithm, Iterative Deepening A* (IDA*), and Simplified Memory Bounded A* (SMA*). Our paper however primarily focuses on IDA* and SMA* and its effectiveness relative to the other algorithms. The first path-finding task is a simple maze problem where the Pac-Man agent has to find its way to a single food pellet on the map. The second task was the original Pac-Man game where the agent had to collect all the food on the map. The scores were based on how fast all of the food pellets were collected. Ghost agents were removed for simplicity. Our results, as expected, suggests that A* far out-performs other search algorithms.
