Exploring exploitation and exploration algorithms in Ms. Pac-Man
Loading...
Date
2019-02
Authors
Hoque, Sanyat
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Video game technology has grown to include the development of more sophisticated game play by including computer controlled agents or Non-Player Characters (NPCs). Moreover, game environments provide ideal benchmarking tools to examine new and more sophisticated game related algorithms. Ideal testbeds are games like Pac-Man and Ms. Pac-Man. Ms. Pac-Man is a stochastic game played in a complex maze environment. In this thesis, a novel probabilistic tree search algorithm loosely based on the simulated annealing algorithm is used by the ghost agents that pursue Ms. Pac-Man in order to minimize the score of Ms. Pac-Man (the opponent). In general, simulated annealing is a non-deterministic search optimization algorithm to search for a global maximum/minimum in a non-convex discrete search space. A major advantage of simulated annealing over the tree search models used in past research (Ant Colony Optimization and Monte Carlo Tree Search) as applied to the ghost agents in Ms. Pac-Man is the time and memory complexity. Although simulated annealing is still computationally intensive, it is less so in comparison to the search algorithms mentioned above. Simulated annealing and variants are also excellent sources of easy-to-understand analogs. This thesis investigates the trade-off between exploration and exploitation phases of search algorithms used by ghost agents as they attempt to contain or constrain the movements of Ms. Pac-Man. New algorithms are developed and presented to better control the NPCs within Ms. Pac-Man. The proposed models or algorithms are evaluated on two different experimental setups; 1) maze navigation to test the convergence efficiency with respect to the number of iterations, and 2) within the game of Ms. Pac-Man itself to determine the effectiveness of attacking strategies such as flanking and blocking. These new algorithms may have application within similar types of problems.
Description
Keywords
Simulated, Annealing, Pac-Man