Monte-Carlo Tree Search Enhancements for Havannah
Monte-Carlo Tree Search Enhancements for Havannah
复制标题
哈瓦那的蒙特卡洛树搜索增强功能
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Uiterwijk
中科院分区：
文献类型：
--
作者：
J. Stankiewicz;M. Winands;J. Uiterwijk
本文展示了如何通过在MCTS的播放和选择步骤中指导搜索来改进用于Havannah的蒙特卡罗树搜索（Monte-Carlo Tree Search， MCTS）播放器的性能。为了改进MCTS算法的播放步骤，我们使用了两种技术来指导模拟，即最后好回复（Last-Good-Reply， LGR）和N-grams。实验表明LGR给出了显著的改进，尽管这取决于使用哪种LGR变体。使用N-grams来引导游戏也可以显著提高胜率。将N-grams与LGR结合会带来额外的小改进。为了提高MCTS算法的选择步骤，我们基于模式知识初始化新节点的访问次数和获胜次数。通过将选择偏向于关节/邻居移动、局部连接和边缘/角连接，可以显著提高性能。实验表明，将访问次数和获胜次数初始化与LGR和N-grams相结合，可以获得最佳的综合性能。在最好的情况下，使用默认的MCTS程序可以达到77.5%的胜率。
This article shows how the performance of a Monte-Carlo Tree Search (MCTS) player for Havannah can be improved by guiding the search in the playout and selection steps of MCTS. To improve the playout step of the MCTS algorithm, we used two techniques to direct the simulations, Last-Good-Reply (LGR) and N-grams. Experiments reveal that LGR gives a significant improvement, although it depends on which LGR variant is used. Using N-grams to guide the playouts also achieves a significant increase in the winning percentage. Combining N-grams with LGR leads to a small additional improvement. To enhance the selection step of the MCTS algorithm, we initialize the visit and win counts of the new nodes based on pattern knowledge. By biasing the selection towards joint/neighbor moves, local connections, and edge/corner connections, a significant improvement in the performance is obtained. Experiments show that the best overall performance is obtained when combining the visit-and-win-count initialization with LGR and N-grams. In the best case, a winning percentage of 77.5% can be achieved against the default MCTS program.