季辉,丁泽军.双人博弈问题中的蒙特卡洛树搜索算法的改进[J].计算机科学,2018,45(1):140-143
双人博弈问题中的蒙特卡洛树搜索算法的改进
Improvement of Monte Carlo Tree Search Algorithm in Two-person Game Problem
投稿时间:2017-05-08  修订日期:2017-09-21
DOI:10.11896/j.issn.1002-137X.2018.01.023
中文关键词:  蒙特卡洛树搜索,剪枝策略,双人博弈问题
英文关键词:Monte Carlo tree search,Progressive pruning,Two-person games
基金项目:
作者单位E-mail
季辉 中国科学技术大学物理系 合肥230026  
丁泽军 中国科学技术大学物理系 合肥230026 zjding@ustc.edu.cn 
摘要点击次数: 671
全文下载次数: 375
中文摘要:
      蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。 由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显著改进了蒙特卡洛树搜索的准确性和效率。
英文摘要:
      Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes,most notably those employed in game play.In the decision process of a very complex game,like a computer Go game,the basic Monte Carlo tree search method converges very slowly due to large computation cost.This article indicated that MCTS cannot converge to the best strategy of the two-person complete information games.Therefore,this article proposed a new search algorithm which combines MCTS with the min-max algorithm in order to avoid the failure due to the randomness of Monte Carlo method.For further improving computation efficiency of MTCS in complex two-person games,this article also considered to employ some progressive pruning strategies.An experimental test shows that the new algorithm significantly improves the accuracy and efficiency of MCTS.
查看全文  查看/发表评论  下载PDF阅读器