路 李泽南参与

用人工智能打王者荣耀:匹茨堡大学&腾讯AI Lab为游戏AI引入MCTS方法

如果让人工智能来打王者荣耀,应该选择什么样的英雄?近日,匹茨堡大学和腾讯 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)。

研究者称,新论文的主要贡献如下:

  1. 提出了一个基于批量 MCTS 的强化学习方法,其在连续状态、有限动作 MDP 上运行,且利用了子节点鉴别器可以通过之前的树搜索结果进行更新来生成更强大的树搜索。函数逼近器用于追踪策略和价值函数逼近,后者用于减少树搜索 rollout 的长度(通常,策略的 rollout 变成了复杂环境中的计算瓶颈)。

  2. 提供对该方法的完整样本复杂度分析,表明足够大的样本规模和充分的树搜索可以使估计策略的性能接近最优,除了一些不可避免的逼近误差。根据作者的认知,基于批量 MCTS 的强化学习方法还没有理论分析。

  3. 基于反馈的树搜索算法的深度神经网络实现在近期流行的 MOBA 游戏《王者荣耀》上进行了测试。结果表明 AI 智能体在 1v1 游戏模式中很有竞争力。

图 1. 基于反馈的树搜索算法。

图 2. 反馈循环图示。

案例分析:《王者荣耀》MOBA 游戏 AI

研究者在全新的、有挑战性的环境:《王者荣耀》游戏中实现了基于反馈的树搜索算法。该实现是第一次为该游戏 1v1 模式设计 AI 的尝试。

游戏介绍

在《王者荣耀》中,玩家被分为对立的两队,每一队有一个基地,分别在游戏地图的相反角落(与其他 MOBA 游戏类似,如英雄联盟和 Dota 2)。每条线上有防御塔来防御,它可以攻击在一定范围内的敌人。每支队伍的目标是推塔并最终摧毁对方的水晶。本论文仅考虑 1v1 模式,该模式中每个玩家控制一个「英雄」,还有一些稍微弱一点的游戏控制的「小兵」。小兵负责守卫通往水晶的路,并自动攻击范围内的敌人(其攻击力较弱)。图 4 显示了两个英雄和他们的小兵,左上角是地图,蓝色和红色标记表示塔和水晶。

图 4.《王者荣耀》1v1 游戏模式截图。

实验设置

系统的状态变量是一个 41 维的向量,包含直接从游戏引擎获取的信息,包括英雄位置、英雄健康度(血量)、小兵健康度、英雄技能状态和不同结构的相对位置。有 22 个动作,包括移动、攻击、治疗术(heal)和特殊的技能动作,包括(扇形)非指向技能。奖励函数的目标是模仿奖励形态(reward shaping),使用信号组合(包括健康、技能、伤害和靠近水晶的程度)。研究者训练了五个《王者荣耀》智能体,使用的英雄是狄仁杰:

  1. FBTS 智能体使用基于反馈的树搜索算法进行训练,一共迭代 7 次,每次进行 50 局游戏。搜索深度 d = 7,rollout 长度 h = 5。每次调用 MCTS 运行 400 次迭代。

  2. 第二个智能体因为没有 rollout 被标注为「NR」。它使用和 FBTS 智能体相同的参数,除了未使用 rollout。总体来看,它在批量设置上与 AlphaGo Zero 算法有些相似。

  3. DPI 智能体使用 Lazaric et al., 2016 的直接策略迭代技术,进行 K = 10 次迭代。没有价值函数和树搜索(因为计算限制,不使用树搜索就可能进行更多次迭代)。

  4. AVI 智能体实现近似价值迭代(De Farias & Van Roy, 2000; Van Roy, 2006; Munos, 2007; Munos & Szepesvari ´ , 2008),K = 10 次迭代。该算法可被认为是 DQN 的批量版本。

  5. 最后是 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 智能体。

理论蒙特卡洛树搜索游戏腾讯AI Lab论文
1
相关数据
OpenAI 机构

OpenAI是一家非营利性人工智能研究公司,旨在以惠及全人类的方式促进和发展友好的人工智能。OpenAI成立于2015年底,总部位于旧金山,旨在通过向公众开放其专利和研究与其他机构和研究人员“自由合作”。创始人的部分动机是出于对通用人工智能风险的担忧。

https://www.openai.com/
DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年,最初名称是DeepMind科技(DeepMind Technologies Limited),在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯,谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后,Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏,例如即时战略游戏《星际争霸II》(StarCraft II)。深度AI如果能直接使用在其他各种不同领域,除了未来能玩不同的游戏外,例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作,基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

激活函数技术

在 计算网络中, 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数(例如 ReLU 或 S 型函数),用于对上一层的所有输入求加权和,然后生成一个输出值(通常为非线性值),并将其传递给下一层。

策略迭代技术

策略迭代算法直接操纵策略,而不是通过最优值函数间接找到策略。

迭代 技术

模型的权重在训练期间的一次更新。迭代包含计算参数在单个批量数据上的梯度损失。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

阿尔法围棋技术

阿尔法围棋是于2014年开始由英国伦敦Google DeepMind公司开发的人工智能围棋程序。AlphaGo是第一个打败人类职业棋手的计算机程序,也是第一个打败围棋世界冠军的计算机程序,可以说是历史上最强的棋手。 技术上来说,AlphaGo的算法结合了机器学习(machine learning)和树搜索(tree search)技术,并使用了大量的人类、电脑的对弈来进行训练。AlphaGo使用蒙特卡洛树搜索(MCTS:Monte-Carlo Tree Search),以价值网络(value network)和策略网络(policy network)为指导,其中价值网络用于预测游戏的胜利者,策略网络用于选择下一步行动。价值网络和策略网络都是使用深度神经网络技术实现的,神经网络的输入是经过预处理的围棋面板的描述(description of Go board)。

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

马尔可夫决策过程技术

马尔可夫决策过程为决策者在随机环境下做出决策提供了数学架构模型,为动态规划与强化学习的最优化问题提供了有效的数学工具,广泛用于机器人学、自动化控制、经济学、以及工业界等领域。当我们提及马尔可夫决策过程时,我们一般特指其在离散时间中的随机控制过程:即对于每个时间节点,当该过程处于某状态(s)时,决策者可采取在该状态下被允许的任意决策(a),此后下一步系统状态将随机产生,同时回馈给决策者相应的期望值,该状态转移具有马尔可夫性质。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

深度神经网络技术

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

推荐文章
暂无评论
暂无评论~