After taking the course CS7032: Agents, AI & Games at Trinity College, Dublin. We were asked to design and implement an artificial intelligence algorithm for the famous PacMan game, under the rules of (Which seems to be down as of now) and using our knowledge of abstract architectures.

We could choose to design either the behaviour of Ms PacMan or the phantoms. I though implementing Ms PacMan AI would be “faster” as there’s only one entity to design. Never have I been so wrong. It took me around one week of spare time to get it right. Though in the end, I got some acceptable results.

The core AI algorithm is inspired by reactive agents and the evaluative feedback approach. I ran around a thousand games with multiple strategies and identified the best one by plotting the score histogram. The results are on the report.

One algorithm which I found particularly interesting is “Clustering regions by connected components”, which is a linearithmic algorithm with respect to the number of components. This algorithm has certainly many different use cases outside the PacMan world. I explain this algorithm in the report. A screenshot showing the pills clustered by region:


The project is open source and is hosted on github. Feel free to browse the code and adapt it to your needs:

Without further ado, here you have the full report. Enjoy the reading!

NB: the report was rendered using LaTeX and the graphs where plotted using Mathematica 9.