The Pacman Projects are a collection of programming assignments designed to teach students fundamental concepts in artificial intelligence by applying them to Pacman. However, these projects aren't just about coding the AI for a video game character. Rather, they provide a foundation for real-world problems such as computer vision, natural language processing, robotics, etc.
Students are provided with infrastructure and graphics code that can run different Pacman-related programs. However, the crucial algorithms that give Pacman his intelligence have been removed. The student's job to fill in the missing code and make Pacman smart!
The projects were created at UC Berkeley and are shared with other universities. More information can be found at the UC Berkeley page.
First things first, Pacman must be able to navigate his world. I implemented breadth first, depth first, uniform cost, and A* search algorithms to help Pacman find dots and eat them efficiently.
With enemies added to the mix, I implemented minimax and expectimax searches to help Pacman eat dots while avoiding his ghost adversaries. This involved designing state evaluation functions. In addition, I implemented the alpha/beta pruning versions of these algorithms to improve search efficiency.
One assignment provides a Markov Decision Process for a simple gridworld with non-deterministic actions. I computed the expected utility of each state by implementing value iteration. Then, taking away the transition and reward functions, I calculated the optimal policy by implementing Q-learning.
The state space for a Pacman game is too large for exact Q-learning. Real-valued features are extracted from states, and Q-values are defined to be the dot product of this feature vector with a vector of weights. I implemented approximate Q-learning to learn these weights, adjusting them with each experience.
One assignment has Pacman chase ghosts he cannot see. Pacman receives noisy measurements of ghosts' distances. I implemented a tracking algorithm which maintains a belief state for each ghost being tracked. Belief states are updated with each observation and with each time lapse.
Sometimes the state space is too large to store. I implemented approximate inference with a joint particle filter algorithm. Each ghost action is influenced by the positions of the other ghosts, so resampling required querying a provided Bayes Net which describes the ghosts' transition function.
The final assignment is a month-long, open-ended competition. Students create their own AI for a team of Pacman agents to play capture the flag against each other. Success requires both technical ability and creativity.
The board is divided into red and blue halves. Agents are ghosts on their own side, where their job is to attack invading opponents and prevent them from eating dots. When agents cross over into enemy territory, they transform into Pacman and eat the opponent's dots. Whichever team eats all but 2 dots first wins.
The game provides a partially observable environment. Agents can only see opponents within 5 cells of each other. Otherwise, agents only receive noisy distance measurements. Implementing inference to track opponent location over time added enormous value to my team.
Offensive agents should avoid getting eaten by enemy ghosts. I developed a notion of "risk" when determining which dot my Pacman should target. My offensive agents use a form of A* search that incorporates both distance to nearest dot and distance to ghosts into its cost function. This helped my team identify safer dots.
During the month-long project, teams competed against each other in a round-robin fashion every night, and results were posted online. My agents slowly moved up the leader board as time went on. Our professor held a final tournament at the end of the semester, and my agents won 1st place!