游戏 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 的下一轮挑战目标。
桥牌
桥牌是非完美信息4人游戏，在游戏的开始，玩家只能看见自己的手牌。桥牌分为叫牌、打牌两个步骤。
不同于德州扑克，桥牌拥有大得多的隐藏信息，尤其是在叫牌和打牌的初期阶段。计算机非常擅长在完全信息下做搜索，但人类玩家更擅长在非完美信息下进行推理和决策，而这恰恰是计算机不擅长的。此外，桥牌中4个玩家之间既有竞争又有合作，玩家在两两合作的同时，不仅需要估计对手的信息，还需要估计队友的信息。
现在的桥牌算法会随机生成很多次符合当前局面的对手手牌，然后使用双明手算法（double-dummy-solver）估算最佳的出牌方式，最终选择所有抽样手牌中综合性能最好的出牌。这样的算法非常依赖于随机生成手牌的数量和质量，以及双明手算法的性能。在游戏快结束的时候，因为隐藏的手牌不多，通过抽样做搜索的算法可能会更加有效。
从1997年开始，每年都有世界计算机桥牌大赛，但是至今仍然没有一个 AI 可以战胜顶级的人类玩家。
麻将
麻将也是一个多人非完美信息博弈游戏，在世界各地，尤其是亚洲有着广泛的群众基础。
常见的麻将由4位玩家组成，每个玩家可以有13张私有手牌。类似于围棋，麻将有着巨大的状态复杂度。和德州扑克相比，麻将在任一局面下，每个对手的隐藏状态数要大出十几个数量级，这种不确定性让玩家很难估计对手的状态。人类玩家在游戏的过程中，会根据“直觉”估算对手的一些影响自己决策的信息，比如听牌状态、听牌分数等；而对于自己的手牌部分，往往对能够拿到什么分数做了精确的搜索。如何平衡模糊估计和精确搜索，对 AI 来说是一个巨大的挑战。
不同于德州扑克和桥牌，麻将玩家在出牌前，需要从底牌中随机抽出一张牌替换丢掉的这张手牌。因为这张随机抽取的底牌，麻将的强随机性贯穿游戏的始终，并将深刻地改变游戏的结果。举个例子，如果有两位玩家同时听相同的牌，最终谁是赢家，主要取决于运气。
麻将的强随机性将使 AI 的学习效率成为一种挑战。假如我们想知道：“玩家打赢了，是因为打得好还是运气好？”，要想得到这个答案，我们通常需要进行大量的游戏来衡量。如何在强随机性的环境中更高效地进行自我学习，是 AI 需要解决的一个难题。
同时，由于麻将游戏强大的随机性，如何衡量麻将 AI 的水平也是一个挑战。
小结
为了解决这些新的挑战，未来，游戏 AI 需要具备在大量隐藏状态下进行推理决策、高效学习的能力，也需要更强大的应对随机事件能力和协作能力。我们期待游戏 AI 技术能够在这些充满挑战的游戏中不断突破，同时将从游戏中学到的经验和能力应用在真实世界中，帮助人类更出色地完成各种复杂任务。
[2]CMU's news on Pluribus
https://www.cmu.edu/news/stories/archives/2019/july/cmu-facebook-ai-beats-poker-pros.html
[3]AlphaStart's official blog
https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/
[4]Advantage of micromanagement for AlphaStar https://bdtechtalks.com/2019/01/28/deepmind-alphastar-ai-starcraft-2/
[5]Reddit discussion on AlphaStar https://www.reddit.com/r/MachineLearning/comments/ajgzoc/we_are_oriol_vinyals_and_david_silver_from/
[6]OpenAI Five
https://openai.com/blog/openai-five/
[7]Reddit discussion on OpenAI-Five https://www.reddit.com/r/MachineLearning/comments/bfq8v9/d_openai_five_vs_humans_currently_at_410633_992/
[8]Computer-Bridge
https://en.wikipedia.org/wiki/Computer_bridge
你也许还想看：
感谢你关注“微软研究院AI头条”，我们期待你的留言和投稿，共建交流平台。来稿请寄：msraai@microsoft.com。