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