Pac-Man

Overview

The Pac-Man projects were developed by CS 188 Fall 2021 . 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.

Note: this project is not written by me from scratch, skeleton code is provided by course staff. The project is composed by three parts: Search, Multiagent, and RL.

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.

Multiagent

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

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