Transpositions and move groups in Monte Carlo tree search
Transpositions and move groups in Monte Carlo tree search
复制标题
蒙特卡洛树搜索中的转置和移动组
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Levente Kocsis
中科院分区：
文献类型：
--
作者：
Benjamin E. Childs;James H. Brodeur;Levente Kocsis
蒙特卡洛搜索，特别是UCT（适用于树的上置信界）算法，对围棋游戏的显著改进做出了贡献，并在其他应用中受到了相当大的关注。本文研究了UCT算法的两个增强。首先，我们考虑当搜索树被视为一个图（并且交换之间的信息是共享的）时，对UCT的可能调整。第二个修改引入了移动分组，这可能会降低有效分支因子。这两个增强的实验进行了使用人工树和围棋比赛。从实验结果中，我们得出结论，利用图形结构和分组移动可能有助于增加游戏程序使用UCT的播放强度。
Monte Carlo search, and specifically the UCT (Upper Confidence Bounds applied to Trees) algorithm, has contributed to a significant improvement in the game of Go and has received considerable attention in other applications. This article investigates two enhancements to the UCT algorithm. First, we consider the possible adjustments to UCT when the search tree is treated as a graph (and information amongst transpositions are shared). The second modification introduces move groupings, which may reduce the effective branching factor. Experiments with both enhancements were performed using artificial trees and in the game of Go. From the experimental results we conclude that both exploiting the graph structure and grouping moves may contribute to an increase in the playing strength of game programs using UCT.