Course Projects
Overview
Our course includes 10 programming assignments. 3 of which are
contests where you will be graded based on your submission's
relative performance when compared to all other submissions. Most
projects will be based on the classic Pac-man game. The Pac-Man
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 are 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
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.
P2: Multiagent Pathfinding
Students define and implement heuristics for solving the multiagent
pathfinding problem efficiently. Students are also requested to
implement the Conflict-Based Search algorithm. These algorithms are
then tested within an Amazon warehouse domain.
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
P3: Multi-Player 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.
P4: 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.
P5: 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.
P6: Machine Learning
Students implement the perceptron algorithm and neural
network models, and apply the models to several tasks including digit
classification.
Contest 3: Multi-Agent Adversarial Pacman
This contest 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. Students are expected to fuse the different AI tools acquired along this semester and produce a competitive, intelligent player.
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.
Credits
The projects were developed by John DeNero, Dan Klein, Pieter Abbeel, and many others.
The Multiagent pathfinding and Game theory projects were developped by Guni Sharon.