Monte Carlo Tree Search for Simultaneous Move Games: A Case Study in the Game of Tron

Monte Carlo Tree Search for Simultaneous Move Games: A Case Study in the Game of Tron

Lanctot, M.
Wittlinger, C.
Den Teuling, N.G.P.
Winands, M.H.M.

2013-11-08

MCTS has been successfully applied to many sequential games. This paper investigates Monte Carlo Tree Search (MCTS) for the simultaneous move game Tron. In this paper we describe two different ways to model the simultaneous move game, as a standard sequential game and as a stacked matrix game. Several variants are presented to adapt MCTS to simultaneous move games, such as Sequential UCT, Decoupled UCT, Exp3, and a novel stochastic method based on Regret Matching. Through the experiments in the game of Tron on four different boards, it is shown that Decoupled UCB1-Tuned perform best, winning 62.3% of games overall. We also show that Regret Matching wins 53.1% of games overall and search techniques that model the game sequentially win 51.4-54.3% of games overall.

http://resolver.tudelft.nl/uuid:814a4ba7-9508-410e-ba12-79de980cb67b

Conference proceedings

conference paper

(c) 2013 Lanctot, M.; Wittlinger, C.; Den Teuling, N.G.P.; Winands, M.H.M.