Pac-Man AI agents

• Search: DFS, BFS, uniform-cost and A* on the pathing graph, then the harder framing problems, an eat-all-four-corners state and a food heuristic, where the state is a position plus a set of goals. Graded on node-expansion counts, so an inadmissible or loose heuristic that still finds the path fails; the heuristic has to be provably admissible and consistent.
• Adversarial: the ghosts are opponents, so search becomes a game tree. Minimax, then alpha-beta pruning for the same answer at less depth cost, then expectimax for ghosts that move randomly rather than optimally, plus a hand-built evaluation function over food distance, ghost distance and scared timers to score non-terminal states.
• Reinforcement learning: reward is unknown until acted on. Value iteration on a known MDP, then tabular Q-learning with epsilon-greedy exploration when the MDP is not given, then approximate Q-learning over a feature extractor so a policy learned on a small grid transfers to layouts the agent never trained on.
• Probabilistic tracking: the ghosts go invisible and only a noisy distance reading remains. Exact inference as a hidden Markov model updated by variable elimination, then particle filtering when exact inference is too expensive, then a joint particle filter tracking several interacting ghosts at once from the noisy sonar alone.
• Neural networks: a small autodiff engine of node objects with forward and backward passes, then models built on top of it, a perceptron, a regression net that fits sin(x), and a fully-connected classifier for 28×28 digit images, each trained by minibatch gradient descent to a target accuracy.

Code for classes still running is kept private under Berkeley's academic-honesty policy. Happy to walk through it in person. ← Back to all projects