Monte carlo tree search in simultaneous move games with applications to Goofspiel

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.