Pac-Man

Learn foundational AI concepts with Pac-Man, including search, probabilistic inference, and reinforcement learning.

Overview

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

I implemented 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.

Classic Pacman is modeled as both an adversarial and a stochastic search problem. I implemented multiagent minimax and expectimax algorithms, as well as designing evaluation functions.

Part 3: Logic and Classical Planning

Pacman world is represented with booleans, and logical inference is used to solve planning tasks as well as localization, mapping, and SLAM.

Project 4: Bayes Nets and HMMs

Pacman uses probabilistic inference on Bayes Nets and the forward algorithm and particle sampling in a Hidden Markov Model to find ghosts given noisy readings of distances to them.

Part 5: Machine Learning

I implemented the perceptron algorithm, neural network, and recurrent nn models, and applied the models to several tasks including digit classification and language identification.

Part 6: Reinforcement Learning

I implemented Value Function, Q learning, and Approximate Q learning to help pacman and crawler agents learn rational policies.

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 Logic and ML projects.