The Pac-Man Projects
Overview
The Pac-Man projects were developed at UC Berkeley for the education purpose of AI, and adapted by our course staff for Rutgers CS440. The projects 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.
These projects were designed 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
Project 0: Python, Setup, & Autograder Tutorial
This short tutorial introduces students to setup examples, the Python programming language, and the autograder system.
Project 1: 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.
Project 2: Reinforcement Learning
Students implement Value Function, Q learning, and Approximate Q learning to help pacman and crawler agents learn rational policies.
Project 3: Multi-Agent Games
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.
Project 4: Machine Learning
Students implement the perceptron algorithm, neural network, and apply the models to several tasks including digit classification.
Bonus Project: Bayesian Networks
Students use probabilistic inference on Bayes Nets to find ghosts given noisy readings of distances to them.
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, except the ML project.
Credits
The projects were developed at UC Berkeley by John DeNero, Dan Klein, Pieter Abbeel, and many others. The core projects and autograders were primarily created by John DeNero and Dan Klein. Student side autograding was added by Brad Miller, Nick Hay, and Pieter Abbeel.