维护全局博弈图的蒙特卡洛图搜索  

Monte Carlo tree search for maintaining the global game graph

作　　者：徐长明 周其磊 王一川 王栋年 金张根 王军伟 XU Changming;ZHOU Qilei;WANG Yichuan;WANG Dongnian;JIN Zhanggen;WANG Junwei(School of Computer and Communication Engineering,Northeastern University,Qinhuangdao 066004,China;Graduate School of Northeastern University,Qinhuangdao 066004,China)

机构地区：[1]东北大学秦皇岛分校计算机与通信工程学院,河北秦皇岛066004 [2]东北大学研究生院,河北秦皇岛066004

出　　处：《重庆理工大学学报（自然科学）》2024年第5期130-136,共7页Journal of Chongqing University of Technology：Natural Science

基　　金：河北省自然科学基金面上项目(F2023501006)。

摘　　要：AlphaGo系列算法利用具备学习价值神经网络和策略神经网络主导蒙特卡洛树搜索的方法,成功地推动了棋类游戏人工智能的迅速发展。而最近,已有成果表明采用蒙特卡洛图搜索替代蒙特卡洛树搜索能够进一步提高程序的对弈水平。在此基础上,提出了一种新的基于蒙特卡洛图搜索的方法——维护全局博弈图的蒙特卡洛图搜索算法。该方法通过维护一个全局的博弈图,采用过期结点删除算法清除无价值的结点和边,并利用对手的时间进行推理计算等措施,提高了程序的博弈水平。以海克斯棋为实验对象,结果证明,在计算资源受限情况下相比其他搜索算法胜率有所提升。The AlphaGo series algorithms have significantly advanced artificial intelligence in board games by employing neural networks with learning value and policy networks to guide the Monte Carlo Tree Search method.Recent research results indicate replacing Monte Carlo Tree Search with Monte Carlo Graph Search can further enhance the program’s search efficiency.On this basis,this paper employs a novel method known as the Monte Carlo graph search for maintaining the global game graph.This method,by maintaining a global game graph,utilizes the expired node deletion algorithm to eliminate nodes and edges without value.Additionally,it employs measures such as reasoning calculations during the opponent’s turn,enhancing the program’s search efficiency.Our experiment on Hex demonstrates this method,under limited computing resources,exhibits an enhanced winning rate compared to alternative search strategies.

关 键 词：AlphaGo系列算法 计算机博弈 蒙特卡洛图搜索 计算资源 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]