Pacman Heuristics


AI implementations for games like chess and GO have had their recent fame in the AI spotlight. It's time that Pacman has it's day in the sun. Through Mini-max and AlphaBeta Implementations, I sought to give strategic future vision to our valiant 8-bit ghost-eater.


To understand what's going on underneath the hood here's a high-level explanation of both Mini-max and Expectimax.

Minimax is a recursive backtracking algorithm that fares exceptionally well when deciding the future paths one can take. As the game progresses down the decision tree, at each step, the best possible path is calculated, in accordance with the goal you want to maximize. (In this case food).

AlphaBeta works very similarly to Minimax except that certain parts of the recursive tree are pruned along the way (AB tree). Reducing computational time and speeding up the prediction process

Fig 1. A Decision Tree Heatmap drawn out by the AB algorithm before PacStart
50:50 Crystal | Rose
Latent Space Walk 50:50 Crystal | Rose
50:50 Crystal | Rose
75:25 Crystal | Rose
75:25 Crystal | Rose

See Pac Run!

To see this project for yourself:
1. Navigate to the Pac project
on github here
2. Open it in your favorite Py3 compatible IDE
3. A couple of options:
Run '-python3' to play the game on its own
Run '-python3 -p MinimaxAgent -l minimaxClassic -a depth=4' to see some minimax action
Run 'python3 -p AlphaBetaAgent -a depth=3 -l smallClassic' to see some AlphaBeta Action

Enjoy and let me know if you have any questions :^)

US Dept. of Homeland Security
Patrol Agent