Real-Time Search Method in Nondeterministic Game — Ms. Pac-Man

Article type: Research Article

Authors: Gan, Xiaocong¹ | Bao, Yun | Han, Zhangang²

Affiliations: Department of Systems Science, Beijing Normal University, P. R. China

Note: [1] Department of Systems Science, Beijing Normal University, P. R. China. Email: [email protected]

Note: [2] Department of Systems Science, Beijing Normal University, P. R. China. Email: [email protected], the corresponding author.

Abstract: A search-based method is proposed to control the real-time and nondeterministic game Ms. Pac-Man automatically. First, a detailed survey is given, including (1) some details of the game, (2) a literature review of more than 20 works from the competition organized by Simon M. Lucas and (3) some other papers. Then we propose an image recognition method for the game that can recognize partially occluded objects effectively by using corner pixels. Based on the recognition results, we use the game-tree search algorithm to make the decisions. Heuristic rules are carefully designed to ensure that the search tree can be expanded sufficiently deep within a limited time. A vector is evaluated for each node in the tree. This vector facilitates the implementation of hand-coded rules. We achieve an average score of 67,602 and a high score of 106,980, both remarkably higher than previous works.

DOI: 10.3233/ICG-2011-34404

Journal: ICGA Journal, vol. 34, no. 4, pp. 209-222, 2011