pacman-agent
2023
What it is
Two coursework projects built on top of UC Berkeley's Pacman AI framework for ASU's intro AI
course. I implemented the search algorithms Pacman uses to path-find through mazes: DFS, BFS,
uniform-cost search, and A* (search.py), plus custom search problems like visiting all four
maze corners with an admissible heuristic (searchAgents.py). I also implemented adversarial
decision-making for Pacman playing against one or more ghosts: a reflex agent, minimax,
alpha-beta pruning, and expectimax (multiAgents.py).
The problem
The starter framework handled the game engine, GUI, and problem scaffolding, but left the pathfinding and decision logic stubbed out.
Approach
I gave the four search algorithms a shared frontier/node structure, differing only in what data structure orders the frontier: stack, queue, or priority queue by cost (or cost plus heuristic). For the corners heuristic, I computed an admissible, consistent lower bound by brute-forcing all permutations of the remaining unvisited corners and summing Manhattan distances between consecutive corners.
For the adversarial agents, I generalized minimax, alpha-beta, and expectimax to N ghosts using depth plus agentIndex recursion, treating one full ply as Pacman's move plus every ghost's move in sequence. I modeled expectimax's ghosts as uniformly random rather than optimal adversaries, instead of assuming worst-case play the way minimax does.