Pac-Man AI
search · minimax · Q-learning agents
Bellman backups propagate reward outward from the +1 goal; the arrows are the greedy policy under the current values, the same MDP solve the project runs.
Interactive Gridworld: watch value iteration converge in your browser.
The agent logic for UC Berkeley's three Pac-Man AI projects: Berkeley ships the game engine, layouts and autograder, the agents are the work here. Search: depth-first, breadth-first, uniform-cost and A* graph search, plus a CornersProblem state encoding with admissible corners and food heuristics (the food heuristic prices the farthest pellet by true maze distance) so A* routes Pac-Man optimally. Adversarial: a reflex evaluation function, a multi-agent minimax that cycles Pac-Man and every ghost per ply, an expectimax agent modeling ghosts as uniform-random, and a hand-tuned evaluation weighing food and ghost distance, scared timers and remaining pellets. Reinforcement learning: a value-iteration agent that solves known MDPs with batch Bellman sweeps over Gridworld, a tabular ε-greedy Q-learning agent with temporal-difference updates, an approximate Q-agent that learns linear weights over extracted features, and discount/noise/living-reward settings derived to force five target Gridworld policies. The in-page demo reruns the Gridworld value-iteration loop in the browser.
- Python
- Search (DFS/BFS/UCS/A*)
- Minimax
- Expectimax
- MDPs
- Value Iteration
- Q-Learning
- Search algorithms
- 4 (DFS/BFS/UCS/A*)
- Agent code
- 1,549 LOC (6 core files)
- Q-learning
- ε .05 · γ .8 · α .2
- Value iteration
- γ .9 · 100 sweeps
What I'd improve
The honest gap is alpha-beta pruning: the AlphaBetaAgent is still a stub, so minimax pays the full game-tree cost and search depth stays shallow. Next would be closing that, then replacing the corners heuristic's greedy Manhattan chain with true maze distances (the food heuristic already uses them), and learning the evaluation weights instead of tuning them by hand.