维护全局博弈图的蒙特卡洛图搜索
Monte Carlo tree search for maintaining the global game graph
徐长明 1周其磊 1王一川 1王栋年 2金张根 2王军伟1
作者信息
- 1. 东北大学秦皇岛分校 计算机与通信工程学院, 河北 秦皇岛 066004
- 2. 东北大学 研究生院, 河北 秦皇岛 066004
- 折叠
摘要
AlphaGo系列算法利用具备学习价值神经网络和策略神经网络主导蒙特卡洛树搜索的方法,成功地推动了棋类游戏人工智能的迅速发展.而最近,已有成果表明采用蒙特卡洛图搜索替代蒙特卡洛树搜索能够进一步提高程序的对弈水平.在此基础上,提出了一种新的基于蒙特卡洛图搜索的方法——维护全局博弈图的蒙特卡洛图搜索算法.该方法通过维护一个全局的博弈图,采用过期结点删除算法清除无价值的结点和边,并利用对手的时间进行推理计算等措施,提高了程序的博弈水平.以海克斯棋为实验对象,结果证明,在计算资源受限情况下相比其他搜索算法胜率有所提升.
Abstract
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系列算法/计算机博弈/蒙特卡洛图搜索/计算资源Key words
AlphaGo series algorithms/computer-based game/Monte Carlo graph search/computational resources引用本文复制引用
基金项目
河北省自然科学基金面上项目(F2023501006)
出版年
2024
国家科技期刊平台
NSTL
万方数据