Intelligent controller for the ghost team in the Ms. PacMan game

Abstract

The aim of this project is to control the ghost team so as to minimize the score obtained by Ms Pac-Man in the game. We only focus on how to capture Ms Pac-Man as fast as possible. A capturing algorithm is used in order to determine if the ghost team can have a guaranteed success to capture Ms. Pac-Man collaboratively. The algorithm is based on the idea of breath-first search in a tree data structure. A tree is built and searched during the calculation. The location of Ms Pac-Man is the root of tree. The children are the connected vertices of that location. If there is any ghost that can reach a certain vertex before Ms Pac-Man can, it will be assigned to that vertex. If all leaf nodes are occupied by ghosts, a collaborative capturing strategy is found. The algorithm proceeds level by level. If a capturing strategy has not been found, the tree will extend from unoccupied vertices and search continuously until the algorithm finds out a capturing strategy or number of leaf nodes is more than number of non-edible ghosts. This algorithm is implemented in an open-source platform of the Ms. Pac-Man game and its performance is evaluated. The ghost team using this algorithm eats Ms Pac-Man effectively and efficiently.