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 pacman-vs-ghosts.net (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: MyPacMan.java

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.