Pacman-AI-Solver

Project Overview

PacMan AI Solver is a Python-based project implementing classic and heuristic search algorithms (DFS, BFS, A*) to solve a simplified PacMan problem on a linear grid. The goal is for PacMan to eat all fruits ('f') and poisonous fruits ('d') following specific movement and action rules. The updated version adds a robust iterative search loop, multiple A* heuristics, a batch runner, and CSV export for experiments.

What’s New (Updated Version)

• Iterative search loop with explicit frontier handling and expansion counting.
• Three A* heuristics: nearest, sum, and max distances (never return inf).
• Run All mode to benchmark DFS, BFS, and all A* variants in one go.
• Timing & metrics: runtime, nodes expanded, and path length are reported.
• CSV export to pacman_results.csv for downstream analysis.
• Cleaner boundary checks (e.g., right bound uses state[-1]) and small robustness tweaks.

Problem Definition

World Description

The world consists of a linear grid (default 6 cells), each of which can contain:

• PacMan ('p')
• Fruit ('f')
• Poisonous fruit ('d')
• Empty space ('')

Initial State

An example of an initial state is:

[['', 'd'], ['', 'f'], ['p', ''], ['', ''], ['', 'f'], ['', '']]

Constraints on the initial state:

• PacMan and a fruit cannot occupy the same cell initially.
• At most one poisonous fruit ('d').
• At most four fruits ('f') in total.

Goal State

A goal state is any state in which there are no fruits or poisonous fruits left on the grid. For example:

[['', ''], ['', ''], ['', ''], ['', ''], ['p', ''], ['', '']]

State Representation

Each state is represented as a list of lists:

 [ ['', 'd'], ['', 'f'], ['p', ''], ['', ''], ['', 'f'], ['', ''] ] 

- The first element in each sublist denotes the presence of PacMan ('p') or is empty (''). - The second element denotes the presence of fruit ('f'), poisonous fruit ('d'), or is empty ('').

Operators (Transition Functions)

The project defines the following operators:

• Move Left: PacMan moves one cell left if not at the leftmost edge.
• Move Right: PacMan moves one cell right if not at the rightmost edge.
• Eat: PacMan eats a fruit or poisonous fruit in the same cell. If PacMan eats a poisonous fruit ('d'), a new fruit ('f') is randomly generated in any empty cell.

Search Algorithms Implemented

1. Depth-First Search (DFS)

Explores paths as deep as possible before backtracking. DFS may explore long, irrelevant paths and is not guaranteed to find the shortest solution, but it has low memory overhead.

2. Breadth-First Search (BFS)

Explores all nodes at the current depth before moving deeper. Guarantees the shortest path but can be memory-intensive.

3. A* Search (with Heuristics)

Combines path cost (g-cost) with a heuristic estimate (h-cost). This version includes multiple admissible-style heuristics that guide the search:

• Nearest Distance (h_nearest): distance from PacMan to the closest target (fruit or poisonous fruit).
• Sum of Distances (h_sum): sum of distances from PacMan to all remaining targets.
• Max Distance (h_max): farthest target distance (emphasizes worst-case target).

All heuristics return a numeric value and never return inf (return 0 when no targets remain).

Heuristic Distance

Distances are computed as absolute index differences on the linear grid:

distance = abs(pacman_index - target_index)

Code Execution

To run the program:

 python pacman_solver.py 

You will be prompted to select a search method:

• 1 = DFS
• 2 = BFS
• 3 = A* (uses the default heuristic pipeline inside the code)
• 4 = Run All (DFS, BFS, A* with nearest/sum/max) → prints metrics and writes pacman_results.csv

Sample Console Output

 Running A* (nearest) ... _GOAL_FOUND_ Goal State: [['', ''], ['', ''], ['', ''], ['', ''], ['p', ''], ['', '']]
Path to Goal:
[['', 'd'], ['', 'f'], ['p', ''], ['', ''], ['', 'f'], ['', '']]
...
--- Experiment Results ---
Algorithm: A* (nearest)
Nodes Expanded: 8
Path Length: 7
Runtime: 0.012500 seconds

CSV Export

When selecting Run All, the solver writes a summary file:

pacman_results.csv

with columns:

Algorithm,Nodes Expanded,Path Length,Runtime (s)

Sample Results & Method Comparison

• DFS: Deep search, returns long/non-optimal paths but uses little memory.
• BFS: Finds the shortest path but expands many nodes (higher memory/time cost).
• A*: Heuristic guidance reduces expansions and runtime. Different heuristics expose trade-offs between solution quality and search effort.

Conclusion

All implemented methods successfully solve the PacMan problem by finding a state where all fruits are eaten. In practice, A* with a well-chosen heuristic offers the best balance of optimality and efficiency. The updated solver makes it easy to compare strategies across scales, record metrics, and export results, reinforcing core lessons in search algorithms and heuristic design.

How to Modify Heuristics

In run_all() you can add/remove A* variants or change the default heuristic:

 algorithms = [ ("DFS", None), ("BFS", None), ("A* (nearest)", h_nearest), ("A* (sum)", h_sum), ("A* (max)", h_max), ] 

You can also pass a specific heuristic directly into run_algorithm(initial_state, "A* (nearest)", h_nearest).

Dependencies

• Python 3.x
• Standard library only: copy, random, sys, time, csv