The Pac-Man Projects


Pac-Man Game

Overview

The Pac-Man projects were developed for CS 188. They apply an array of AI techniques to playing Pac-Man. However, these projects don't focus on building AI for video games. Instead, they teach foundational AI concepts, such as informed state-space search, probabilistic inference, and reinforcement learning. These concepts underly real-world application areas such as natural language processing, computer vision, and robotics.

We designed these projects with three goals in mind. The projects allow you to visualize the results of the techniques you implement. They also contain code examples and clear directions, but do not force you to wade through undue amounts of scaffolding. Finally, Pac-Man provides a challenging problem environment that demands creative solutions; real-world AI problems are challenging, and Pac-Man is too.


Projects Overview

P0: UNIX/Python Tutorial

This short UNIX/Python tutorial introduces students to the Python programming language and the UNIX environment.


P1: Search

Students implement depth-first, breadth-first, uniform cost, and A* search algorithms. These algorithms are used to solve navigation and traveling salesman problems in the Pacman world.


Mini-Contest 1: Multi-Agent Pacman

Students will apply the search algorithms and problems implemented in Project 1 to handle more difficult scenarios that include controlling multiple pacman agents and planning under time constraints


P2: Multi-Agent Search

Classic Pacman is modeled as both an adversarial and a stochastic search problem. Students implement multiagent minimax and expectimax algorithms, as well as designing evaluation functions.


Mini-Contest 2: Multi-Agent Adversarial Pacman

This minicontest involves a multiplayer capture-the-flag variant of Pacman, where agents control both Pacman and ghosts in coordinated team-based strategies. Each team will try to eat the food on the far side of the map, while defending the food on their home side.


P3: Reinforcement Learning

Students implement model-based and model-free reinforcement learning algorithms, applied to the AIMA textbook's Gridworld, Pacman, and a simulated crawling robot.


P4: Ghostbusters

Probabilistic inference in a hidden Markov model tracks the movement of hidden ghosts in the Pacman world. Students implement exact inference using the forward algorithm and approximate inference via particle filters.


P5: Classification

Students implement standard machine learning classification algorithms using Naive Bayes, Perceptron, and MIRA models to classify digits. Students extend this by implementing a behavioral cloning Pacman agent.


Contest: Pacman Capture the Flag

Students create strategies for a team of two agents to play a multi-player capture-the-flag variant of Pacman.


Technical Notes

The Pac-Man projects are written in pure Python 3.6 and do not depend on any packages external to a standard Python distribution.


Support

This project was supported by the National Science foundation under CAREER grant 0643742. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).


Credits

The projects were developed by John DeNero, Dan Klein, Pieter Abbeel, and many others.