利用统计数据并行蒙特卡罗树搜索算法的中国象棋博弈  

Chinese Chess Game Using Statistical Data Parallel Monte Carlo Tree Search Algorithm

作　　者：朱舟 闵华松[1] ZHU Zhou;MIN Huasong(School of Information Science and Engineering,Wuhan University of Science and Technology,Wuhan 430081,China)

机构地区：[1]武汉科技大学信息科学与工程学院,武汉430081

出　　处：《计算机工程与应用》2024年第23期340-348,共9页Computer Engineering and Applications

基　　金：国家重点研发计划(2022YFB4700400);国家自然科学基金(62073249);湖北省重点研发计划(2023BBB011)。

摘　　要：针对蒙特卡洛树搜索算法(Monte Carlo tree search,MCTS)收敛速度过慢,且在博弈过程中关键节点会出现信息丢失等问题,以中国象棋为载体,构建适用于中国象棋博弈系统的策略价值网络,提出了一种基于统计数据的并行蒙特卡洛树搜索算法(parallel Monte Carlo tree search based on statistics,SPMCTS)。将并行化的重点设置在MCTS四个步骤中最耗时的扩展和模拟步骤,有效避免了算法执行过程中的等待时差。并且引入一组新统计数据,这些数据用于在MCTS的选择步骤中修改节点的选择策略,保证在进行节点选择时获取和利用更多的可用信息,缓解信息丢失对精度造成的影响。实验结果表明,与现有并行蒙特卡洛树算法相比,SPMCTS在搜索速度上加快了约34%,且在对弈实验中,博弈胜率也能保持在80%左右。验证了SPMCTS的有效性。Aiming at the problems of slow convergence of Monte Carlo tree search(MCTS)and information loss of key nodes in the game process,a strategic value network suitable for Chinese chess game system is constructed with Chinese chess as the carrier,and a parallel Monte Carlo tree search based on statistics(SPMCTS)algorithm is proposed.The focus of parallelization is set to the most time-consuming expansion and simulation steps among the four steps of MCTS,which effectively avoids the waiting time lag during the algorithm execution.A new set of statistical data is introduced,which is used to modify the node selection strategy in the selection step of MCTS,ensuring that more available information is obtained and utilized during node selection,and alleviating the impact of information loss on accuracy.The experimental results show that compared with the existing parallel Monte Carlo tree algorithm,SPMCTS can accelerate the search speed by about 34%,and the game win rate can be maintained at about 80%in the chess experiment,which indicates the effectiveness of SPMCTS.

关 键 词：蒙特卡洛树搜索 中国象棋 博弈系统 策略价值网络 并行化 统计数据 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]