摘要

本文讨论了在通用视频游戏玩（GVGP）领域中，如何通过八种增强技术改进实时蒙特卡洛树搜索（MCTS）的性能。这些增强技术包括渐进历史、N-Gram选择技术、树重用、广度优先树初始化、损失避免、新颖性基础剪枝、知识基础评估和确定性游戏检测。这些技术旨在提高MCTS在处理未知游戏时的适应性和效率，特别是在GVGP框架中，通过这些增强技术，MCTS的平均胜率从31.0%提升到了48.4%，接近2015年GVG-AI竞赛中最佳代理的水平。

原理

本文提出的八种增强技术主要通过以下方式改进MCTS的性能：

1. 渐进历史（PH）和N-Gram选择技术（NST）：通过在选择和模拟步骤中引入偏差，倾向于选择在早期模拟中表现良好的动作或动作序列，从而提高搜索效率。
2. 树重用（TR）：利用前一游戏刻构建的搜索树的一部分作为当前搜索过程的初始状态，通过衰减旧结果来适应新状态，提高搜索效率。
3. 广度优先树初始化（BFTI）和安全预剪枝：通过在开始MCTS之前，使用1-ply广度优先搜索生成根节点的直接后继，并进行评估，以避免在模拟次数极少的情况下随机选择动作。
4. 损失避免（LA）：在遇到失败游戏状态时，不立即反向传播结果，而是尝试找到更好的替代方案，保持对节点价值的乐观初始视图。
5. 新颖性基础剪枝（NBP）：基于新颖性测试，剪枝冗余的玩法线路，避免MCTS在树的深层生成状态，而忽略了根节点附近的状态。
6. 知识基础评估（KBE）：使用在模拟过程中收集的知识和对象距离来区分具有相同评估值的状态，提高评估的准确性。
7. 确定性游戏检测（DGD）：检测游戏是否可能是确定性的，并对确定性游戏采用不同的处理方式，如修改MCTS的选择策略和树重用策略。

流程

MCTS的工作流程包括选择、模拟、扩展和反向传播四个步骤。本文的增强技术通过在这四个步骤中引入新的策略和机制，优化了MCTS的工作流程。例如，在选择步骤中，使用PH和NST来偏向选择表现好的动作；在模拟步骤中，使用LA来避免立即反向传播失败结果；在扩展步骤中，使用BFTI和安全预剪枝来初始化树结构；在反向传播步骤中，使用KBE来提高状态评估的准确性。这些增强技术的结合使用，使得MCTS在GVGP中的表现得到了显著提升。

应用

这些增强技术不仅适用于GVGP领域，还可以扩展到其他需要实时决策和搜索的领域，如机器人导航、自动驾驶和复杂系统管理等。通过这些技术的应用，可以提高系统的适应性和决策效率，具有广泛的应用前景。