原标题:用人工智能打王者荣耀：匹茨堡大学&腾讯AI Lab为游戏AI引入MCTS方法
选自arXiv
作者：Daniel R. Jiang、Emmanuel Ekwedike、Han Liu
机器之心编译
参与：路、李泽南
如果让人工智能来打王者荣耀，应该选择什么样的英雄？近日，匹茨堡大学和腾讯 AI Lab 提交的论文给了我们答案：狄仁杰。在该研究中，人们尝试了 AlphaGo Zero 中出现的蒙特卡洛树搜索（MCTS）等技术，并取得了不错的效果。
对于研究者而言，游戏是完美的 AI 训练环境，教会人工智能打各种电子游戏一直是很多人努力的目标。在开发 AlphaGo 并在围棋上战胜人类顶尖选手之后，DeepMind 正与暴雪合作开展星际争霸 2 的人工智能研究。去年 8 月，OpenAI 的人工智能也曾在 Dota 2 上用人工智能打败了职业玩家。那么手机上流行的多人在线战术竞技游戏（MOBA 游戏）《王者荣耀》呢？腾讯 AI Lab 自去年起一直在向外界透露正在进行这样的研究。最近，匹茨堡大学、腾讯 AI Lab 等机构提交到 ICML 2018 大会的一篇论文揭开了王者荣耀 AI 研究的面纱。
本文中，我们将通过论文简要介绍该研究背后的技术，以及人工智能在王者荣耀中目前的能力。
2006 年 Remi Coulom 首次介绍了蒙特卡洛树搜索（MCTS），2012 年 Browne 等人在论文中对其进行了详细介绍。近年来 MCTS 因其在游戏 AI 领域的成功引起了广泛关注，在 AlphaGo 出现时关注度到达顶峰（Silver et al., 2016）。假设给出初始状态（或决策树的根节点），那么 MCTS 致力于迭代地构建与给定马尔可夫决策过程（MDP）相关的决策树，以便注意力被集中在状态空间的「重要」区域。MCTS 背后的概念是如果给出大概的状态或动作值估计，则只需要在具备高估计值的状态和动作方向扩展决策树。为此，MCTS 在树到达一定深度时，利用子节点鉴别器（策略函数（Chaslot et al., 2006）rollout、价值函数评估（Campbell et al., 2002; Enzenberger, 2004），或二者的混合（Silver et al., 2016））的指引，生成对下游值的估计。然后将来自子节点的信息反向传播回树。
MCTS 的性能严重依赖策略／值逼近结果的质量（Gelly & Silver, 2007），同时 MCTS 在围棋领域的成功表明它改善了用于子节点鉴别的给定策略，事实上，这可以被看作是策略改进算子（Silver et al., 2017）。匹茨堡大学、腾讯 AI Lab 等机构的研究者们新发表的论文研究了一种基于反馈的新型框架，其中 MCTS 利用根节点生成的观测结果更新其子节点鉴别器。
MCTS 通常被视为一种在线规划器，决策树以当前状态作为根节点开始构建（Chaslot et al., 2006; 2008; Hingston & Masek, 2007; Maˆıtrepierre et al., 2008; Cazenave, 2009; Mehat & ´ Cazenave, 2010; Gelly & Silver, 2011; Gelly et al., 2012; Silver et al., 2016）。MCTS 的标准目标是仅为根节点推荐动作。在采取动作之后，系统向前移动，然后从下一个状态中创建一棵新的树（旧树的数据可能会部分保存或完全丢弃）。因此 MCTS 是一个「局部」的步骤（因为它仅返回给定状态的动作），与构建「全局」策略的价值函数逼近或策略函数逼近方法存在本质区别。在实时决策应用中，构建足够的「运行中」（on-the-fly）局部逼近比在决策的短期时间内使用预训练全局策略更难。对于国际象棋或围棋等游戏而言，使用 MCTS 的在线规划可能是合适的，但是在需要快速决策的游戏中（如 Atari 或 MOBA 视频游戏），树搜索方法就太慢了（Guo et al., 2014）。本论文提出的算法可以离策略的方式在强化学习训练阶段中使用。训练完成后，与子节点鉴别有关联的策略可以实现，以进行快速、实时的决策，而无需树搜索。
主要贡献
MCTS 的这些特性推动了研究者们提出一种新方法，在训练步骤中利用 MCTS 的局部特性，来迭代地构建适应所有状态的全局策略。思路是在原始 infinite-horizon MDP 的多批小型 finite-horizon 版本上应用 MCTS。大致如下：（1）初始化随机价值函数和策略函数；（2）开始（可能是并行处理）处理一批 MCTS 实例（限制在搜索深度内，从采样状态集合中初始化而得），同时将价值函数和策略函数整合为子节点鉴别器；（3）使用最近的 MCTS 根节点观测结果更新价值函数和策略函数；（4）从第（2）步开始重复步骤。该方法利用 MCTS 策略优于单独的子节点鉴别器策略（Silver et al., 2016），同时改进子节点鉴别器也会改善 MCTS 的质量（Gelly & Silver, 2007）。
研究者称，新论文的主要贡献如下：
提出了一个基于批量 MCTS 的强化学习方法，其在连续状态、有限动作 MDP 上运行，且利用了子节点鉴别器可以通过之前的树搜索结果进行更新来生成更强大的树搜索。函数逼近器用于追踪策略和价值函数逼近，后者用于减少树搜索 rollout 的长度（通常，策略的 rollout 变成了复杂环境中的计算瓶颈）。
提供对该方法的完整样本复杂度分析，表明足够大的样本规模和充分的树搜索可以使估计策略的性能接近最优，除了一些不可避免的逼近误差。根据作者的认知，基于批量 MCTS 的强化学习方法还没有理论分析。
基于反馈的树搜索算法的深度神经网络实现在近期流行的 MOBA 游戏《王者荣耀》上进行了测试。结果表明 AI 智能体在 1v1 游戏模式中很有竞争力。
图 1. 基于反馈的树搜索算法。
图 2. 反馈循环图示。
案例分析：《王者荣耀》MOBA 游戏 AI
研究者在全新的、有挑战性的环境：《王者荣耀》游戏中实现了基于反馈的树搜索算法。该实现是第一次为该游戏 1v1 模式设计 AI 的尝试。
游戏介绍
在《王者荣耀》中，玩家被分为对立的两队，每一队有一个基地，分别在游戏地图的相反角落（与其他 MOBA 游戏类似，如英雄联盟和 Dota 2）。每条线上有防御塔来防御，它可以攻击在一定范围内的敌人。每支队伍的目标是推塔并最终摧毁对方的水晶。本论文仅考虑 1v1 模式，该模式中每个玩家控制一个「英雄」，还有一些稍微弱一点的游戏控制的「小兵」。小兵负责守卫通往水晶的路，并自动攻击范围内的敌人（其攻击力较弱）。图 4 显示了两个英雄和他们的小兵，左上角是地图，蓝色和红色标记表示塔和水晶。
图 4.《王者荣耀》1v1 游戏模式截图。
实验设置
系统的状态变量是一个 41 维的向量，包含直接从游戏引擎获取的信息，包括英雄位置、英雄健康度（血量）、小兵健康度、英雄技能状态和不同结构的相对位置。有 22 个动作，包括移动、攻击、治疗术（heal）和特殊的技能动作，包括（扇形）非指向技能。奖励函数的目标是模仿奖励形态（reward shaping），使用信号组合（包括健康、技能、伤害和靠近水晶的程度）。研究者训练了五个《王者荣耀》智能体，使用的英雄是狄仁杰：
FBTS 智能体使用基于反馈的树搜索算法进行训练，一共迭代 7 次，每次进行 50 局游戏。搜索深度 d = 7，rollout 长度 h = 5。每次调用 MCTS 运行 400 次迭代。
第二个智能体因为没有 rollout 被标注为「NR」。它使用和 FBTS 智能体相同的参数，除了未使用 rollout。总体来看，它在批量设置上与 AlphaGo Zero 算法有些相似。
DPI 智能体使用 Lazaric et al., 2016 的直接策略迭代技术，进行 K = 10 次迭代。没有价值函数和树搜索（因为计算限制，不使用树搜索就可能进行更多次迭代）。
AVI 智能体实现近似价值迭代（De Farias & Van Roy, 2000; Van Roy, 2006; Munos, 2007; Munos & Szepesvari ´ , 2008），K = 10 次迭代。该算法可被认为是 DQN 的批量版本。
最后是 SL 智能体，它通过在大约 100,000 个人类玩游戏数据的状态／动作对数据集上进行监督学习来训练。值得注意的是，此处使用的策略架构与之前的智能体一致。
事实上，策略和价值函数近似在所有智能体中都是一样的，二者分别使用具备五个和两个隐藏层的全连接神经网络和 SELU（scaled exponential linear unit）激活函数（Klambauer et al., 2017）。初始策略 π0 采取随机动作：移动（w.p. 0.5）、直接攻击（w.p. 0.2）或特殊技能（w.p. 0.3）。除了将移动方向挪向奖励方向之外，π0 不使用其他启发式信息。MCTS 是 UCT 算法的变体，更适合处理并行模拟：研究者不使用 UCB 分数的 argmax，而是根据对 UCB 得分应用 softmax 函数所获得的分布进行动作采样。
与理论不同，在算法的实际实现中，回归使用 cosine proximity loss，而分类使用负对数似然损失。由于在该游戏环境中我们无法「倒带」或「快进」至任意状态，因此采样分布 ρ0 由第一次采取的随机动作（随机的步数）来实现并到达初始状态，然后遵循策略 πk 直到游戏结束。为了减少价值逼近中的相关性，研究者丢弃了在这些轨迹中遇到的 2/3 的状态。对于 ρ1，研究者遵循 MCTS 策略，偶尔带入噪声（以随机动作和随机转向默认策略的方式）来减少相关性。在 rollout 中，研究者使用游戏内部 AI 作为英雄狄仁杰的对手。
结果
由于该游戏几乎是确定性的，因此研究者的主要测试方法是对比智能体对抗内部 AI 对手的有效性。研究者还添加了游戏内建 AI 的狄仁杰作为「完整性检查」基线智能体。为了选择测试对手，研究者使用内建 AI 狄仁杰对抗其他内建 AI（即其他英雄）并选择六个内建 AI 狄仁杰能够打败的射手类英雄。研究者的智能体每一个都包含内建狄仁杰 AI，使用智能体对抗测试对手。图 5 显示了每个智能体打败测试对手的时间长度（单位为帧）（如果对手赢了，则显示为 20,000 帧）。在与这些共同对手的战斗中，FBTS 显著优于 DPI、AVI、SL 和游戏内建 AI。但是，FBTS 仅稍微超出 NR 的表现（这并不令人惊讶，因为 NR 是另外一个也使用 MCTS 的智能体）。研究者的第二组结果帮助可视化了 FBTS 和四个基线的对决（全部都是 FBTS 获胜）：图 6 显示了 FBTS 智能体及其对手的金币比例，横轴为时间。王者荣耀游戏中英雄对敌人造成伤害或者战胜敌人时，都会得到金币，因此金币比例大于 1.0（高出红色区域）表示 FBTS 的良好性能。如图所示，每个游戏结束时 FBTS 的金币比例都在 [1.25, 1.75] 区间内。
图 5. 几种智能体战胜其他射手英雄所用时间（以帧为单位，即帧的数量），数字越小越好。其中 FBTS 为新研究提出的智能体。
图 6. 游戏内行为。
论文：Feedback-Based Tree Search for Reinforcement Learning
论文链接：https://arxiv.org/abs/1805.05935
摘要：蒙特卡洛树搜索（MCTS）已在多个人工智能领域取得了成功，受此启发我们提出了一种基于模型的强化学习技术，可以在原始 infinite-horizon 马尔可夫决策过程的多批小型 finite-horizon 版本上迭代使用 MCTS。我们使用估计值函数和估计策略函数指定 finite-horizon 问题的终止条件或 MCTS 所生成决策树的子节点鉴别器。MCTS 步骤生成的推荐结果作为反馈，通过分类和回归来为下一次迭代细化子节点鉴别器。我们为基于树搜索的强化学习算法提供第一个样本复杂度界限。此外，我们还证明该技术的深度神经网络实现可以创建一个适合《王者荣耀》游戏的有竞争力的 AI 智能体。
本文为机器之心编译，转载请联系本公众号获得授权。
✄------------------------------------------------
加入机器之心（全职记者/实习生）：hr@jiqizhixin.com
投稿或寻求报道：content@jiqizhixin.com
广告&商务合作：bd@jiqizhixin.com