Compatibility & Prerequisites

This project has been tested and works on Linux, macOS, and Windows.

• Python 3.10+ — no external packages required (only the standard library)
• Tkinter — usually bundled with Python; needed for the graphical display
• pytest — for running the self-check tests

sudo apt-get install python3-tk        # Debian / Ubuntu
sudo dnf install python3-tkinter       # Fedora / RHEL
sudo pacman -S tk                      # Arch

Verify your setup

python main.py

You should see a Pac-Man game window open. Use the arrow keys to play manually and confirm everything works.

Install pytest (if needed)

pip install pytest

Learning Objectives

• Implement reusable graph-search algorithms over a generic SearchProblem API.
• Understand frontier strategies: stack (DFS), queue (BFS), and priority queue (UCS / A*).
• Design admissible and consistent heuristics for A*.
• Model richer state spaces (e.g., visited corners, food grid).

Project Structure

pac-man-search/
├── main.py                        # Entry point — run this to start Pac-Man
│
├── pacman/                        # Main game package
│   ├── search.py                  # ✏  search algorithms   (YOU EDIT THIS)
│   ├── search_agents.py           # ✏  search problems & heuristics (YOU EDIT THIS)
│   ├── engine.py                  # Game runner and command-line interface
│   ├── game.py                    # Core types: GameState, Agent, Directions, Grid
│   ├── layout.py                  # Maze loading and parsing from .lay files
│   ├── util.py                    # Data structures: Stack, Queue, PriorityQueue
│   ├── eight_puzzle.py            # 8-puzzle domain (tests generic search)
│   ├── agents/
│   │   ├── pacman_agents.py       # Pre-built Pac-Man agents
│   │   ├── ghost_agents.py        # Ghost behaviour controllers
│   │   └── keyboard_agents.py    # Human-playable keyboard agent
│   └── display/
│       ├── graphics_display.py    # Tkinter graphical display
│       ├── graphics_utils.py      # Graphics helper utilities
│       └── text_display.py        # Text-only display (no GUI needed)
│
├── layouts/                       # 37 maze layout files (.lay)
│
└── tests/
    └── check.py                   # 45 self-check tests — run with pytest

Files you will edit

You only need to modify two files. All places are marked with # TODO comments. Do not modify any other files.

Exact functions & methods to implement

pacman/search.py — 4 functions

pacman/search_agents.py — 7 methods and functions

Getting Started

Step 1 — Play the game manually

python main.py

Use the arrow keys to control Pac-Man. This helps you understand the game mechanics.

Step 2 — Try different layouts

python main.py --layout smallMaze
python main.py --layout mediumMaze
python main.py -l bigMaze

Step 3 — Understand SearchProblem

Every search problem implements the abstract class defined in search.py:

class SearchProblem:
    def get_start_state(self):      # Returns the start state
    def is_goal_state(self, state): # Returns True if state is a goal
    def get_successors(self, state):# Returns list of (state, action, step_cost)
    def get_cost_of_actions(self, actions): # Total cost of action sequence

Step 4 — Understand the provided data structures (pacman/util.py)

stack = util.Stack()          # LIFO — use for DFS
queue = util.Queue()          # FIFO — use for BFS
pq    = util.PriorityQueue()  # Min-heap — use for UCS and A*

pq.push(item, priority)
pq.update(item, priority)     # Update priority if lower

# All three support:
data_structure.is_empty()

Homework Tasks (Q1–Q8)

python main.py -l tinyMaze -p SearchAgent
python main.py -l mediumMaze -p SearchAgent
python main.py -l bigMaze -z .5 -p SearchAgent

python main.py -l mediumMaze -p SearchAgent -a fn=bfs
python main.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

python main.py -l mediumMaze -p SearchAgent -a fn=ucs
python main.py -l mediumDottedMaze -p StayEastSearchAgent
python main.py -l mediumScaryMaze -p StayWestSearchAgent

python main.py -l bigMaze -z .5 -p SearchAgent \
  -a fn=astar,heuristic=manhattan_heuristic

python main.py -l tinyCorners -p SearchAgent \
  -a fn=bfs,prob=CornersProblem
python main.py -l mediumCorners -p SearchAgent \
  -a fn=bfs,prob=CornersProblem

python main.py -l mediumCorners \
  -p AStarCornersAgent -z 0.5

python main.py -l trickySearch \
  -p AStarFoodSearchAgent

python main.py -l bigSearch \
  -p ClosestDotSearchAgent -z .5

General Algorithm Hints

Graph Search Pattern (all four algorithms share this skeleton)

1. Initialize the frontier with the start state
2. Initialize an empty set of visited states
3. While the frontier is not empty:
   a. Pop a node from the frontier
   b. If this node is the goal → return the path
   c. If this node has been visited → skip it
   d. Mark this node as visited
   e. For each successor not yet visited → add to frontier
4. Return failure (no path found)

The only difference between the four algorithms is the frontier data structure and priority:

Common mistakes to avoid

• Tree search instead of graph search — always track visited states; without this your algorithm may loop forever.
• Checking goal at push time vs. pop time — check goal when you pop a node, not when you push. This is required for UCS and A* correctness.
• Mutable state in tuples — if your state includes a list, convert it to a tuple before adding to the visited set (lists are not hashable).
• Forgetting the path — each frontier entry should carry the sequence of actions taken to reach that state.

Testing Your Implementation

Self-check tests (tests/check.py) — 45 tests total

# Run all tests
pytest tests/check.py -v

# Run tests for a specific question
pytest tests/check.py -v -k "q1"
pytest tests/check.py -v -k "q2"
pytest tests/check.py -v -k "q3"
pytest tests/check.py -v -k "q4"
pytest tests/check.py -v -k "q5"
pytest tests/check.py -v -k "q6"
pytest tests/check.py -v -k "q7"
pytest tests/check.py -v -k "q8"

# Run a single test by name
pytest tests/check.py -v -k "test_q1_pacman_tiny_maze"

Official autograder

python grader/autograder.py --no-graphics           # all questions
python grader/autograder.py --no-graphics -q q1      # one question
python grader/autograder.py --no-graphics --mute

What each pytest test checks

Q1–Q4: 6 tests each

Q5 (Corners Problem): 5 tests

Q6 / Q7 heuristics print your grade tier:

tests/check.py::TestQ6_CornersHeuristic::test_q6_medium_corners PASSED
  [Q6] mediumCorners: expanded 1100 nodes → 9/9

tests/check.py::TestQ7_FoodHeuristic::test_q7_tricky_search PASSED
  [Q7] trickySearch: expanded 6800 nodes → 12/12

Useful Command-Line Options

python main.py --help                # Show all options

# Layout selection
python main.py -l smallMaze

# Agent and algorithm selection
python main.py -p SearchAgent -a fn=bfs
python main.py -p SearchAgent -a fn=ucs
python main.py -p SearchAgent -a fn=astar,heuristic=manhattan_heuristic
python main.py -p SearchAgent -a fn=bfs,prob=CornersProblem
python main.py -p AStarCornersAgent
python main.py -p AStarFoodSearchAgent

# Display options
python main.py --frameTime 0         # Instant moves (no animation delay)
python main.py -z 0.5                # Zoom out for large mazes
python main.py -q                    # Quiet mode (no graphics)
python main.py --textGraphics        # Text-only display (no Tkinter needed)

Troubleshooting

"Method not implemented" / SystemExit: 1

You haven't filled in a # TODO section yet. The stub calls util.raise_not_defined(). Replace it with your implementation.

TypeError: unhashable type: 'list'

Your state uses a list somewhere. Convert to a tuple:

# Wrong
state = (position, [True, False, True, False])

# Correct
state = (position, (True, False, True, False))

"Path goes through a wall"

Your get_successors() generates invalid moves. Check self.walls[next_x][next_y] before adding a successor.

Q5 fails even though Q1–Q4 pass

Q5 depends on Q2 (BFS). Verify BFS first:

pytest tests/check.py -v -k "q2"

Q6 / Q7 pass but with a low grade tier

Your heuristic is admissible but not tight enough. Tips:

• Q6: Instead of distance to the farthest corner alone, estimate the total tour through all unvisited corners.
• Q7: Instead of distance to the farthest food, consider the maze_distance between the two food pellets that are farthest apart from each other.

Tests hang or run forever

Your algorithm has an infinite loop — you are doing tree search instead of graph search. Add a visited set and skip states you've already expanded.

No graphics / Tkinter errors

python main.py -q               # No graphics at all
python main.py --textGraphics   # Text-only display

The pytest tests in tests/check.py never require graphics — they always work headless.

Points Breakdown

Academic Integrity

• Do not distribute or publish solutions.
• Do not copy solutions from the internet.
• You may discuss general approaches with classmates, but write your own code.