Pacman AI

A set of projects developing AI for Pacman and similar agents, developed as part of CS 188 (Artifical Intellegence) at UC Berkeley in Fall 2017. This is a popular project used at multiple different universities, but it originated with this course. This iteration of the project contained several other applications of the techniques used for other AI problems, such as handwriting analysis, language recognition, and CartPole.

Topics covered include:

Graph Search Algorithms

Representing the maze as a graph, Pacman finds the most efficient path to a specific location using DFS, BFS, Djikstra’s Algorithm, and A* search. Additionally, these same algorithms can be used to find the most efficient path to eat all the pellets in the maze.

Adversarial Search

Introducing ghosts as enemy agents, Pacman attempts to survive as long as possible by predicting their moves using Minimax and Expectiminimax.

Reinforcement Learning

Representing the maze as an Markov Decision Process, Pacman trains using Q-Learning to attempt to find the best set of actions to take in order to survive. However, because the state space for even a medium-sized maze is very large, approximate Q-Learning is used instead. In approximate Q-Learning, a linear combination of each state’s features are used to assign a value to each possible action, and the value of the weights in the linear combination are what’s learned. This takes much less time compared to “regular” Q-learning, where a Q-value for each and every state must be learned and stored.

Bayesian Inference

In a twist on the normal game of Pacman, the maze Pacman travels around contains two houses - one of them “safe”, and the other containing ghosts. However, initially the maze is completely invisible, and only by traveling around the maze can its state be observed. Additionally, there is no way to tell for sure which house is which, but the more blue walls the house has, the more likely it is to be the safe house.

Therefore, we can create an AI which collects observations from the maze by traveling randomly around it for a set time. After it collects these observations, it infers which house is most likely to be the safe house using a Bayesian Network model.

Inference with Noisy Observations

In another variation on Pacman, the maze contains multiple invisible ghosts that give off noisy signals. Pacman’s goal is to track them down and eat them based on these signals. By constructing a Bayesian Network and using a joint particle filtering algorithm, Pacman generates a probability that each ghost is located at a specific square of the maze.

×

Finding a path through all the dots using A* search

A Pacman AI using expectiminimax to avoid ghosts. This is a pretty slow method, especially with the graphics engine.

A Pacman AI trained with 50 iterations of approximate Q-Learning. Even this short training period leads to pretty smooth movement.

An application of Q-Learning used to train a crawler robot to move.

Using Bayesian inference, Pacman is exploring the space (which was initially all invisible) to find the house most likely to be safe. The more blue walls it has, the more likely it is to be safe.

Using a particle filtering algorithm, this Pacman agent is attempting to find invisible ghosts which give off noisy signals. The colored tiles represent Pacman's belief that a ghost of that color is at that position.

The CartPole problem solved using a Deep Q Network to learn weights for Approximate Q-Learning.

Close