基于启发式剪枝优化蒙特卡洛树搜索的爱恩斯坦棋算法研究

浩笛 杨(计算机与软件工程学院辽宁科技大学，中国)

摘要

针对标准蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）在爱恩斯坦棋中存在的搜索冗余高、有效深度不足和时间预算利用率低等问题，本文提出一种基于启发式剪枝的改进算法（Heuristic-Pruned MCTS，HP-MCTS）。该方法在保留MCTS“选择—扩展—模拟—回传”主流程的基础上，将局面启发式评估融入选择与扩展环节：在选择阶段构建改良HUCT（Heuristic UCT）公式，在探索项与经验价值项之外增加启发式修正项；在扩展阶段采用动态阈值与安全保留机制进行分支剪枝，从而减少低价值分支的后续模拟开销。围绕爱恩斯坦棋“随机骰子驱动+单步方向约束+近似替代选子”的博弈特征，本文构建了由“可行动概率权重”“目标逼近收益”“关键防线惩罚”组成的综合评估函数，并给出参数标定和复杂度分析。实验在统一思考时限（5s/步）条件下，将HP-MCTS与标准MCTS进行多轮对弈比较。结果表明：HP-MCTS可显著降低扩展节点总数，提升平均搜索深度与对战胜率；在重度剪枝配置下，算法胜率达到82.0%，扩展节点较标准MCTS下降58.2%，验证了启发式剪枝在复杂随机博弈中的有效性。本文研究可为爱恩斯坦棋AI与同类随机对抗问题的搜索优化提供参考。

关键词

爱恩斯坦棋；蒙特卡洛树搜索；启发式剪枝；博弈AI；算法优化

参考

徐心和，邓志立，王骄，等。机器博弈研究面临的各种挑战[J]. 智能系统学报，2008, 3 (4): 288-293.

王亚杰，邱虹坤，吴燕燕，等。结合神经网络的改进 UCT 在国际跳棋中的应用 [J]. 重庆理工大学学报 (自然科学), 2021, 35 (7): 112-118.

Silver D, Huang A, Maddison C J, et al. Mastering the Game of Go with Deep Neural Networks and Tree Search [J]. Nature, 2016, 529 (7587): 484-489.

DOI: http://dx.doi.org/10.12345/bdai.v7i3.38183