A Monte-Carlo Approach for the Endgame of Ms. Pac-Man

Abstract

The objective of this project is to design an effective module for the endgame of Ms. Pac-Man. In my design, there are two major components. The first component uses depth first search to find a number of short paths from the current position of Ms. Pac-Man to some specified locations. The second one uses Monte Carlo simulations to simulate the random movement of the ghosts and test whether each of the paths selected by the first component is safe if Ms. Pac-Man moves according to it. The one with the largest alive rate will be chosen. This endgame module is invoked when the number of remaining pills in a maze is smaller than a certain value. Experimental results show that when this module is added to an existing controller, both the average score and the number of cleared stages can been improved significantly.