游戏 AI 挑战进阶,即时策略游戏和非完美信息游戏成为热点

2019-08-21 | 作者:微软亚洲研究院

在前面两篇文章中,我们回顾了游戏 AI 历史上的几个经典算法和里程碑事件,还介绍了如何从数学角度衡量象棋、围棋、扑克、麻将等棋牌类游戏 AI 的复杂度。在这篇文章里,我们将分享几个近年来非常成功的游戏 AI,同时介绍几个尚未被 AI 攻克的流行游戏,它们无疑代表着未来游戏 AI 的发展方向和趋势。

达到或超过人类顶尖水平的游戏 AI

多人德州扑克:Pluribus

不同于国际象棋和围棋,德州扑克作为一个不完美信息游戏,有着不同的挑战:玩家看不见彼此的牌,并且玩家往往会利用这种不对称进行诈唬(Bluff),从而误导对手。AlphaGo/AlphaZero 等适用于完美信息游戏的算法无法在扑克中直接使用。在 AI 领域,德州扑克仍然被视为尚未被攻克的挑战。

最近由 CMU 联合 Facebook 开发的 Pluribus,第一次在六人不限注德州扑克中战胜了顶级人类玩家。这些人类玩家都是曾经赢下超过百万美金的职业选手,Pluribus 在12天之内和这些人类玩家进行了超过10,000次对局,并最终取得胜利。

Pluribus 的训练并未借助人类牌谱,而是从零开始,通过与6个自己的副本进行对战,不断提高自己的性能。在自我对局中,Pluribus 通过基于 MCCFR(Monte Carlo CFR)算法搜索和学习更好的打牌技巧,并将不同的自我对局结果称之为蓝图(Blueprint)策略。由于不限注德州扑克的状态空间过大,该蓝图策略只能涉及到有限的策略空间,因此在实际对战中, Pluribus 会采用蓝图策略做初步决策;并在之后的对局中,通过往前搜索有限的几步来做进一步细化的决策。Pluribus 的主要开发者 Noam Brown 相信,Pluribus 的一些策略将会改变职业玩家的打法。

但是,尽管德州扑克属于非完美信息游戏,给定任何局面,每个对手可能的隐藏状态数目只有一千多种(从50张牌中选择2张)。不管是 Pluribus,还是另一个非常成功的扑克 AI DeepStack 的算法,都非常依赖于对手牌的概率分布的估计来做细粒度搜索,其实现难度相对可控。而这些近似算法在隐藏状态数目大得多的游戏中(比如桥牌和麻将),是很难适用的。

图1:Pluribus在和五个职业玩家的对战中做了一个诈唬

星际争霸2:AlphaStar

AlphaStar 是由 DeepMind 联合暴雪开发的「星际争霸2」游戏 AI,其在2019年1月战胜了顶尖的职业玩家。

「星际争霸」是一款多人即时战略游戏,常见的1v1对战模式中,每个玩家会从三个种族中选择一个,在不同的地图上进行对战。游戏开始时,每个玩家会分配一些初始单位,基于这些单位,玩家需要从地图上获取可发展资源,并利用这些资源建造更多的单位和科技。游戏的目标是通过运营资源,制造军队,从而摧毁对方所有的单位。

星际争霸玩家需要同时考虑宏观规划和微观操作,游戏的时间可以长达一个小时,这意味着 AI 的策略需要有长期规划的能力。且不同于传统的棋牌游戏,星际玩家需要在短时间内连续地操作分布于不同地区的多个单位。此外,星际争霸也是一个不完美信息游戏,初始的地图上弥漫着一层「战争迷雾」,使得对方的信息不可见,因此玩家需要不断地试探对方的位置,并作出相应的应对操作。

AlphaStar 使用深度神经网络接收由暴雪提供的游戏内部信息,然后输出一系列指令来指导 AI 做出行为选择。该智能体首先通过学习人类玩家的对战模式,然后通过多智能体(multi-agent)强化学习算法来进一步提高性能。AlphaStar 的网络结构结合了Transformer、LSTM、Auto-Regressive policy head、指针网络(pointer network)以及中心化评分基准(centralized value baseline)。

在监督学习之后,AlphaStar 创建了一个可以让 AI 之间自我学习的联赛机制,通过基于人口理论的强化学习算法,使得 AI 可以在保持足够的多样性的前提下,能够不断地变得强大。由于星际争霸2中不同的策略和种族有一些相生相克的关系,该训练方式使得 AI 能够朝着综合实力更强的方向进行训练。

AlphaStar 无疑是非常成功的,但是也有很多人持有不同的看法,在和人类的较量中,AlphaStar 仍然存在策略之外的不对等:AI 可以在极短的时间内,高细粒度地操控上百个不同的个体,进行不同的任务。这种短时间内的高细粒度、多任务的操控,与人类玩家相比,有着巨大的优势。此外,AlphaStar 只在特定地图上训练了特定的种族,仍然可能有短板。

AlphaStar 开发团队希望他们的模型可以对其他任务有所帮助,尤其是需要对长序列进行建模,并且有很大的输出空间的任务,比如机器翻译、语言模型和视觉表达等。

图2:AlphaStar 和 MaNa(顶级人类玩家)对战的可视化。图中展示了 AI 眼中的游戏:包括输入到神经网络的原始信息,神经网络的内部激活单元,一些备选的动作以及输赢的概率等。

Dota2:OpenAI Five

Dota2 也是一款需要多人参与的即时战略游戏(MOBA),比赛由两个队伍进行对战,每个团队由五位「英雄」组成,这些英雄往往有着不同的特色和各自的职责,因此,团队的获胜依赖于不同职责的选手们之间的分工合作,是一款非常强调团队协作的游戏。和星际争霸类似,Dota2 也是非完美信息游戏,玩家们需要抢占地图上的不同资源和视野,最终打倒对方队伍的核心建筑。

不同于 AlphaStar,Dota2 的训练则完全从自我对战中进行学习,通过近端策略优化(Proximal Policy Optimization)来更新它们的神经网络。很多研究员认为,要想解决 Dota 中的长期规划问题,需要类似分层强化学习这样的技术来分别处理长期和短期的规划。但他们惊喜地发现,仅仅通过强化学习训练的策略也会拥有长期规划的能力。

OpenAI Five 用五个神经网络代表五位“英雄”。五位“英雄”的神经网络之间并没有显式的连接,而是通过控制自己和团队的奖励(reward)的权重来学习协作。

2019年4月,OpenAI Five 在三局两胜制的比赛中, 以2-0的分数战胜了 Dota2 世界冠军 OG 俱乐部。但随着 OpenAI Five 的策略被进一步地分析,网友们也找到了OpenAI Five 的弱点——擅长团队作战却不擅长分推,并根据弱点定制战术,战胜了OpenAI Five.

游戏 AI 的下一轮挑战:桥牌和麻将

在以上游戏中,AI 均可以达到或者超过顶尖人类玩家的水平。而拥有广泛群众基础的桥牌和麻将,因为有着诸多不同的属性,现有的算法并不能很好地处理。毋庸置疑,它们将会是游戏 AI 的下一轮挑战目标。

桥牌

桥牌是非完美信息4人游戏,在游戏的开始,玩家只能看见自己的手牌。桥牌分为叫牌、打牌两个步骤。

不同于德州扑克,桥牌拥有大得多的隐藏信息,尤其是在叫牌和打牌的初期阶段。计算机非常擅长在完全信息下做搜索,但人类玩家更擅长在非完美信息下进行推理和决策,而这恰恰是计算机不擅长的。此外,桥牌中4个玩家之间既有竞争又有合作,玩家在两两合作的同时,不仅需要估计对手的信息,还需要估计队友的信息。

现在的桥牌算法会随机生成很多次符合当前局面的对手手牌,然后使用双明手算法(double-dummy-solver)估算最佳的出牌方式,最终选择所有抽样手牌中综合性能最好的出牌。这样的算法非常依赖于随机生成手牌的数量和质量,以及双明手算法的性能。在游戏快结束的时候,因为隐藏的手牌不多,通过抽样做搜索的算法可能会更加有效。

从1997年开始,每年都有世界计算机桥牌大赛,但是至今仍然没有一个 AI 可以战胜顶级的人类玩家。

麻将

麻将也是一个多人非完美信息博弈游戏,在世界各地,尤其是亚洲有着广泛的群众基础。

常见的麻将由4位玩家组成,每个玩家可以有13张私有手牌。类似于围棋,麻将有着巨大的状态复杂度。和德州扑克相比,麻将在任一局面下,每个对手的隐藏状态数要大出十几个数量级,这种不确定性让玩家很难估计对手的状态。人类玩家在游戏的过程中,会根据“直觉”估算对手的一些影响自己决策的信息,比如听牌状态、听牌分数等;而对于自己的手牌部分,往往对能够拿到什么分数做了精确的搜索。如何平衡模糊估计和精确搜索,对 AI 来说是一个巨大的挑战。

不同于德州扑克和桥牌,麻将玩家在出牌前,需要从底牌中随机抽出一张牌替换丢掉的这张手牌。因为这张随机抽取的底牌,麻将的强随机性贯穿游戏的始终,并将深刻地改变游戏的结果。举个例子,如果有两位玩家同时听相同的牌,最终谁是赢家,主要取决于运气。

麻将的强随机性将使 AI 的学习效率成为一种挑战。假如我们想知道:“玩家打赢了,是因为打得好还是运气好?”,要想得到这个答案,我们通常需要进行大量的游戏来衡量。如何在强随机性的环境中更高效地进行自我学习,是 AI 需要解决的一个难题。

同时,由于麻将游戏强大的随机性,如何衡量麻将 AI 的水平也是一个挑战。

小结

为了解决这些新的挑战,未来,游戏 AI 需要具备在大量隐藏状态下进行推理决策、高效学习的能力,也需要更强大的应对随机事件能力和协作能力。我们期待游戏 AI 技术能够在这些充满挑战的游戏中不断突破,同时将从游戏中学到的经验和能力应用在真实世界中,帮助人类更出色地完成各种复杂任务。

 

参考文献:

[1] Superhuman AI for multiplayer poker

[2] CMU's news on Pluribus

[3] AlphaStart's official blog

[4] Advantage of micromanagement for AlphaStar

[5] Reddit discussion on AlphaStar

[6] OpenAI Five

[7] Reddit discussion on OpenAI-Five

[8] Computer-Bridge