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
复制标题
用于同时移动游戏的蒙特卡罗树搜索：Tron 游戏中的案例研究
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
N. D. Teuling
中科院分区：
文献类型：
--
作者：
Marc Lanctot;Christopher Wittlinger;M. Winands;N. D. Teuling
MCTS已成功应用于许多序列游戏。本文研究了同时移动游戏Tron的蒙特卡罗树搜索（MCTS）。在本文中，我们描述了两种不同的方法来模拟同时移动游戏，作为一个标准的序列游戏和堆叠矩阵游戏。提出了几种变体，以适应MCTS的同时移动游戏，如顺序UCT，解耦UCT，Exp 3，和一种新的随机方法的基础上遗憾匹配。通过在四种不同棋盘上的Tron游戏中的实验，结果表明，解耦UCB 1-Tuned表现最好，总体获胜率为62.3%。我们还发现，遗憾匹配赢得了53.1%的游戏整体和搜索技术，模型的游戏顺序赢得了51.4-54.3%的游戏整体。
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.