🕹️ Basic AI algorithms for Pacman game

Project undertaken as part of the INFO8006 course given by Pr. Louppe.
Grades :

• Project 1 - A* : 16/20
• Project 2 - Minimax and h-minimax : 19/20
• Project 3 - Bayes filter : 20/20

Note : No copying (even partial) of this code within the scope of the INFO8006 course will be tolerated.

Summary

1. Installation
2. Project 1 - A*
3. Project 2 - Minimax
4. Project 3 - Bayes filter
5. Credits

Installation

This section is taken from the project page of the INFO8006 course.

• Install conda
• Create a conda environment to run the programs, activate it and install NumPy

conda create --name pacman python=3.8
conda activate pacman
conda install numpy

• Clone the repository

git clone git@github.com:sgardier/pacman-ai-from-scratch.git

Project 1

The first project involves developing a pathfinding algorithm to eat all the dots while minimizing the total distance traveled.

BFS solution

This solution makes use of Breadth-First search to find the direction to the nearest dot.

Run it (from the projet-1 folder) :

python run.py --agent bfs --layout medium

Multiple layout are available : small, medium, large

A* solution

This solution make use of A* to find the direction to the nearest dot which minimizes the heuristic.
In our solution the heuristic to compute the forward cost is the Manhattan distance between the position of Pacman in the state and the farthest food dot from this position.

Run it (from the projet-1 folder) :

python run.py --agent astar --layout medium

Multiple layout are available : small, medium, large

Project 2

The second project involves developing a algorithm which maximizes the score value.
Eating the food, eating a ghost and winning the map give points (+10, +5, +500) while walking, eating the capsules and losing the game take away points (-1, -5, -500).

Minimax

This solution is a direct implementation of minimax.

Run it (from the projet-2 folder) :

python run.py --agent minimax --ghost dumby --layout small_adv

Since Minimax is a computationally intensive algorithm, we recommend trying only the small layout.
Multiple ghost behaviors are available : dumby, greedy, smarty

H-Minimax

This solution is a variant of minimax called h-minimax.
H-minimax reduces the required computation to find a solution by adding a maximum recursion count and an heuristic.
When the maximum recursion is reached, the score given to the action =
score at recursion state reached - shotest path to all remaining foods at recursion state reached - exp(number of previous walkthrough at the position in the recursion state)

Run it (from the projet-2 folder) :

python run.py --agent minimax --ghost dumby --layout small_adv

Multiple ghost behaviors are available : small_adv, medium_adv, large_adv

Project 3

The third project involves implementing a Bayes filter over noisy reading of the ghost positions.
Here the goal of pacman is to eat all the ghosts in a minimum number steps while having only access to a noisy manhattan distance to each remaining ghost.

Run it (from the projet-3 folder) :

python run.py --ghost afraid --nghosts 1 --layout large_filter --seed 19

Credits

• Simon Gardier (Co-author)
• Jamaa Jair (Co-author)
• Dario Rinallo (Co-author)