Portal de Periódicos da CAPES

Fast Approximate Max-n Monte Carlo Tree Search for Ms Pac-Man

2011; Institute of Electrical and Electronics Engineers; Volume: 3; Issue: 2 Linguagem: Inglês

10.1109/tciaig.2011.2144597

1943-0698

Spyridon Samothrakis, David Robles, Simon M. Lucas,

Gambling Behavior and Treatments

We present an application of Monte Carlo tree search (MCTS) for the game of Ms Pac-Man. Contrary to most applications of MCTS to date, Ms Pac-Man requires almost real-time decision making and does not have a natural end state. We approached the problem by performing Monte Carlo tree searches on a five player max n tree representation of the game with limited tree search depth. We performed a number of experiments using both the MCTS game agents (for pacman and ghosts) and agents used in previous work (for ghosts). Performance-wise, our approach gets excellent scores, outperforming previous non-MCTS opponent approaches to the game by up to two orders of magnitude.