The Pac-Man Projects

Pac-Man Game

Overview

The Pac-Man projects were developed for UC Berkeley's introductory artificial intelligence course, 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 students to visualize the results of the techniques they implement. They also contain code examples and clear directions, but do not force students 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.

In our course, these projects have boosted enrollment, teaching reviews, and student engagement. The projects have been field-tested, refined, and debugged over multiple semesters at Berkeley. We are now happy to release them to other universities for educational use.

Using Pac-Man in your AI Course

You are welcome to use the Pac-Man projects and infrastructure for any educational or personal use. We ask only that you:

  1. Please do not distribute or post solutions to any of the projects.
  2. Please retain the attribution text at the top of each Python file.
  3. Let us know that you're using the projects.
  4. Provide us with a bit of feedback at the end of your course.
  5. Talk to us before re-releasing, repacking, or extending the projects.

The projects are sufficiently complicated that we strongly suggest that you use our testing and deployment infrastructure. Due to the sensitive nature of this material, it is available to instructors by request only. Email us with Pac-Man in the subject and we will provide you with the instructor package, which includes:

  1. Solutions to all projects
  2. Grading scripts for all projects
  3. A deployment script that creates syntax-highlighted HTML of each Python file
  4. Tournament administration code for running the multi-player contest

This package includes some documentation about how to deploy projects, run the contest, and etc. We are also happy to help make sure that the projects are a successful addition to your course.

Contact Information: Email us at denero@cs.berkeley.edu and/or klein@cs.berkeley.edu. The Pac-Man projects were developed primarily by John DeNero and Dan Klein. Many others have contributed to the projects, including Nimar Arora, David Burkett, Jeremy Cowles, Dan Gillick, Aria Haghighi, Nick Hay, Ed Karuna, Jeremy Maitin-Shepard, Barak Michener, Aditi Muralidharan, Adam Pauls, and Daniel Urieli.

Projects

Search Project (search.zip)
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.


Multi-Agent Search Project (multiagent.zip)
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.


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


Probabilistic Tracking Project (tracking.zip)
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.


Multi-Player Contest (contest.zip)
The Pacman contest is an open-ended project in which student agents compete directly against each other in a capture-the-flag style multi-player variant of Pacman. While the contest does not designate particular AI techniques to be used, successful past entries have included state-space search, adversarial search, and probabilistic tracking.


Python Tutorial (tutorial.zip)
This short Python tutorial introduces students to the Python programming language.


Technical Notes

The Pac-Man projects are written in pure Python 2.5 and do not depend on any packages external to a standard Python distribution. The server code for the multi-player contest does have some dependencies, described in the instructor package.

Support

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