2012 · 36 citations · 18 references
ComputingComputer ScienceDecision SciencesAlgorithmsGame TheoryReal-time SystemsMonte Carlo MethodsMonte Carlo SimulationStochastic GamesMonte Carlo Tree SearchOptimization In Stochastic GamesThompson SamplingTurn-based Stochastic GamesTwo-player GamesTwo-player Stochastic Games
Monte-Carlo Tree Search (MCTS) techniques are essentially known for their performance on turn-based games, such as Go, for which players have considerable time for choosing their moves. In this paper, we apply MCTS to the game of Tron, a simultaneous real-time two-player game. The fact that players have to react fast and that moves occur simultaneously creates an unusual setting for MCTS, in which classical selection policies such as UCB1 may be suboptimal. In this paper, we perform an empirical comparison of a wide range of selection policies for MCTS applied to Tron, with both deterministic policies (UCB1, UCBl-Tuned, UCB-V, UCB-Minimal, OMC-Deterministic, MOSS) and stochastic policies (ϵ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> -greedy, EXP3, Thompson Sampling, OMC-Stochastic, PBBM). From the experiments, we observe that UCBl-Tuned has the best behavior shortly followed by UCB1. Even if UCB-Minimal is ranked fourth, this is a remarkable result for this recently introduced selection policy found through automatic discovery of good policies on generic multi-armed bandit problems. We also show that deterministic policies perform better than stochastic ones for this problem.
18
Reinforcement Learning: An Introduction
Richard S. Sutton, Andy Barto · IEEE Transactions on Neural Networks · 1998 · 27.1K citations
Reinforcement Learning: An Introduction
IEEE Transactions on Neural Networks · 2005 · 25.8K citations
Murray Campbell, A. Joseph Hoane, Feng-hsiung Hsu · Artificial Intelligence · 2002 · 1.2K citations