游戏 AI 的缘起与进化

计算机科学家们一直对游戏 AI 乐此不疲，原因并非为了精进棋艺，而是希望在此过程中不断提升人工智能的算法和处理复杂问题的能力。实际上，游戏 AI 的历史几乎和人工智能的历史一样长，很多关于人工智能的研究，都起源于研究如何构建能够完成游戏的智能体（agent）。游戏 AI 的进化，始终与 AI 研究进展相生相伴。

人工智能研究之所以会选择棋牌类游戏作为实验对象，如双陆棋、国际跳棋、国际象棋、扑克、围棋等，主要因为它们往往具有以下特点：

1) 均有一个简单而清晰的规则，有清晰的胜负判定条件和行动准则；

2) 在公众认知中，掌握和精通这些棋牌类游戏往往在一定程度上是人类智力的彰显。

1956 年，国际跳棋就开始使用强化学习算法

其实早在 Alan Turing 勾勒出人工智能的轮廓之前，计算机科学家们就已经开始在游戏上测试他们编写的『智能』程序了。

1928 年，John Vonn Neuman 发表了 Minimax（极小化极大）算法，而在 1949 年，Claude Shannon 将该算法重新组织，并用于解决国际象棋问题。1956 年，达特茅斯会议召开, 人工智能被确立为一个学科。同年，Arthur Samuel 发明了一种能够通过自我学习攻克国际跳棋（Checkers）游戏的算法，现在该算法被称为强化学习（Reinforcement Learning）。

延伸阅读

博弈树（Game Tree）是用一棵树来表达一个赛局中各种后续可能性，一棵完整的博弈树会有一个起始节点，代表赛局中某一个情形；下一层的子节点是上层父节点赛局下一步的各种可能性，依照这种规则扩展，直到赛局结束为止。博弈树中的叶子节点代表了各种游戏结束的可能情形。
极小化极大算法（Minimax）是由 Claude Shannon 定义的用于解决国际象棋的算法，该算法最早在 1927 年被 John Vonn Neuman 发明。该算法可被概括为：对于两个玩家的对抗游戏，其中任何一个玩家的决策会依赖于另外一个玩家之前的决策，且另外一个玩家总是竭尽所能地想要获得胜利。因此，一方会在所有选项中选择令其自身优势最大的一个，而另一方则会选择令对手优势最小的一个。通过穷举不同玩家之间的策略，该算法可以构建一棵搜索树，并通过穷举不同的可能，选择其中能得到最佳结果的路径。实践中，由于不同的游戏可能涉及的状态空间复杂度不同，该算法的计算复杂度会呈指数级增长，因此往往需要引入剪枝策略来简化搜索的复杂度，例如，使用用于预估局面（结果）的预估函数（Evaluation Function）。
Alpha-Beta 剪枝是一种用于减少在极小化极大算法中所需评估的节点数的搜索剪枝算法。该算法在搜索过程中始终维持着两个值，alpha 和 beta，其中 alpha 用来描述搜索到的最好值，任何比它小的值的节点则不需要继续搜索，beta 用来描述对于对手来说最坏的值，其中任何一个选择如果比 beta 值大，则意味着对手不会选择走到目前这个局面，因此也可以停止搜索。

图1：一个简单的 Minimax 搜索树（左）；带有 Alpha-Beta 剪枝策略的 Minimax 搜索树（右）（来自于http://gameaibook.org/book.pdf）

1992 年，双陆棋的突破成为里程碑

双陆棋（Backgammon）智能程序的突破，被认为是人工智能研究史上的一个里程碑式的事件。在 1970 年左右，一名德国棋手 Hans Berliner 编写了双陆棋智能程序BKG 9.8。

图2：双陆棋（左）；TD-Gammon 的模型结构（右）

到了 1992 年，Gerald Tesauro 编写了 TD-Gammon，该程序采用了人工神经网络作为模型，并采用了 TD-lambda 算法进行训练。通过大量的自我博弈，TD-Gammon 达到了顶级人类的水平，而且正是这种没有人类玩家参与的训练方式，使得 TD-Gammon 的下棋方式不同于人类玩家。TD-Gammon 的意义不仅在于采用了强化学习进行训练，更是证明了不需要任何的特征工程，单纯使用棋子的位置作为神经网络的输入亦可训练出达到顶级人类玩家水平的智能体。

双陆棋输赢小插曲

开始时，双陆棋智能程序 BKG 9.8 跟初学者下棋也经常输。但后来 Berliner 使用了模糊逻辑的原理，使程序不断改进，最终在 1979 年 7 月以 7:1 击败了当时的双陆棋世界冠军——意大利棋手 Luigi Villa。不过 Berliner 也指出，这多半是运气的原因，掷得的骰点对计算机比较有利。

20 世纪 90 年代，国际跳棋、国际象棋 AI 纷纷超越人类

随着计算机算力的大幅提升和人工智能算法的逐渐成熟，在 Arthur Samuel 编写第一个用于解决国际跳棋的算法的 38 年之后，艾尔伯特大学的 Jonathan Schaeffer 教授于 1994 年带领团队编写了 Chinook，该程序核心依然采用了搜索树算法，为了减少搜索树的计算复杂度，以及提高预估函数的准确性，它建立了一个包含国际跳棋大师的开局方法和残局局面胜负情况的数据库，并采用了一个基于手工特征的 Alpha-Beta 树搜索算法。

1994 年，在 Chinook 与世界冠军 Marion Tinsley 进行的国际跳棋决赛中，Marion Tinsley 由于身体不适，在与 Chinook 连续打平 6 次之后放弃了比赛，因此 Chinook 成为了第一个在与人类玩家对抗中获得国际跳棋世界冠军的智能程序。Jonathon Schaeffer 教授于 2007 年发表了文章，证明国际跳棋问题已经被人工智能解决。

图3：Marion Tinsley 与 Chinook 对战（左）；Garry Kasparov 与 Deep Blue 对战（右）

而另一边，国际象棋 AI 也被由许峰雄带领的深思（Deep Thought）团队所攻克。深思采用了特殊的硬件设计用于搜索加速，并在此基础上引入了单步延伸（singular extensions）算法，其核心思想是：如果在逐层进行策略搜索时，发现某一步的结果显著好于其他步，则会进一步加深这一步棋的搜索以确认其中没有陷阱。

之后深思团队被 IBM 公司聘用，并应用于 Big Blue 大型机（后改名为深蓝 Deep Blue），于 1997 年以 3.5:2.5 击败国际象棋世界冠军 Garry Kasparov。在与 Kasparov 的比赛中，深蓝受益于专门设计的大型机的强大运算能力，能够每秒钟运算 2 亿步棋，且可搜索及估计随后的 12 步棋（在单步延伸的情况下可搜索 40 步棋）。最终，深蓝计算机成为首个在标准比赛时限内击败国际象棋人类世界冠军的计算机系统。

围棋 AI 完成进化，初步实现历史使命

相比较而言，围棋的状态远复杂于上述棋类游戏（每一步棋可选范围为 19*19 种），而且下棋的策略十分依赖于对于牌局的评估，因此围棋一直被认为是比国际象棋等更难的棋类游戏。

1968 年，Albert Zobrist 编写了第一个围棋程序，该程序仅能打败初级玩家。1993 年，Bernd Brügmann 编写了 Monte Carlo Go 程序，使用了蒙特卡洛算法替代预估函数，该程序不再根据任务精心设计对于结果的预估函数，而是用多次采样（rollout）——自我博弈到终局结束——的平均值替代预估结果。该算法也被认为是 AlphaGo 成功的核心算法。

2006 年，法国国家信息与自动化研究所（INRIA）研究员 Sylvain Gelly 在 Monte Carlo Go 的基础上引入了 UCT 算法，创造了 MoGo 程序，该程序于 2008 年在被让 7 子的情况下打败了职业 8 段选手 Kim Myung Wan。MoGo 的成功充分地证明了 MCTS（UCT） 算法在解决围棋问题上的重要性。

2015 年，DeepMind 团队在上述程序的基础上开发了基于深度强化学习的程序 AlphaGo，并成功击败了欧洲围棋冠军樊麾，成为第一个无需让子即可在 19 路棋盘上击败围棋职业棋手的计算机围棋程序。

延伸阅读

蒙特卡洛树搜索（MCTS）是由 Rémi Coulom 于 2006 年发明的将蒙特卡洛算法应用于博弈树搜索上的算法。该算法的核心思想是用模拟环境跑出来的结果替换根据预估函数估计出来的结果。同年，L. Kocsis 和 C. Szepesvari 发明了 UCT 算法，该算法在蒙特卡洛搜索上结合了 UCB，为搜索策略提供了一个平衡探索（exploration）和利用（exploitation）的方式。目前所实现的 MCTS 一般采用了 UCT 的实现方式。

CFR（Counterfactual Regret Minimization）是由 Martin Zinkevich 于 2007 年提出的算法，该算法从随机策略开始，通过最小化遗憾值的方法，在游戏结束后，寻找事后最优的选择，从而寻找最优的博弈策略和纳什均衡。该算法需要遍历游戏所有的可能状态，因此也需要采用剪枝、估值网络、状态压缩等方法减少计算量。

不完美信息游戏 AI 复杂度更高，开始登上历史舞台

相对于上述棋类而言，扑克、桥牌、麻将等牌类游戏则被认为是另一类游戏，在这些游戏中的玩家往往信息是不对称的，这类游戏被称为不完美信息游戏（imperfect information game）。

由于信息不对称，在德州扑克这样的游戏中，玩家可以通过诈唬（Bluff）来误导对手，通常人们认为顶级人类玩家早已熟练掌握了这门技术（艺术）。阿尔伯特大学的研究人员一直在推动德州扑克 AI 的发展，继 1984 年职业扑克玩家 Mike Caro 编写了 Orac 程序之后，阿尔伯特大学的研究人员 Jonathon Schaeffer 于 1997 年编写了 Loki 用于模拟德州扑克玩家的诈唬行为，2001 年，该程序更名为 PsOpti，并引入了基于博弈论的方法，并在 2015 年发布了 Cepheus，该程序在之前的基础上引入了 CFR+ 算法解决了两人有限注德州扑克，证明了计算机在有限注的情况下可以完胜人类。2017年，卡耐基梅隆大学和阿尔伯特大学相继发布了 Libratus 和 DeepStack，在两人无限注德州扑克上成功击败了世界顶级人类玩家。2019 年，卡耐基梅隆大学又联合 Facebook AI 发布了 Libratus 的后继版本 Pluribus，成功在六人不限注扑克上打败了职业扑克玩家。

另一方面，这种不完美信息状态使得游戏策略的复杂度变得更高，进而使得基于树搜索和 CFR 算法的系统计算复杂度更大。桥牌由于其相对繁复的游戏规则（包含叫牌阶段和打牌阶段），也逐渐成为人工智能跃跃欲试的对象。从上世纪 80 年代开始，曾在美国海军科伦比亚地区实验室任职的 Tom Throop 就开始编写 Bridge Baron 程序，经过十几年的更新，于 1997 年赢得了第一届世界计算机桥牌大赛。第二年，该比赛的冠军则被由俄勒冈大学 Matthew Ginsberg 开发的 GIB 程序获得。同年，该程序被邀请参加了世界桥牌大赛，最终在 35 位参赛者中获得了第 12 名的成绩。在之后的十多年里，基于蒙特卡洛方法的 Jack 和 Wbridge5 轮番取得了该比赛的冠军。对麻将而言，东京大学的 Naoki Mizukami 于2015年开发了名为爆打的 AI 程序，日本 Dwango 公司也于 2018 年开发了基于深度学习模型的 NAGA025。只不过整体而言，这些人工智能程序依然与顶级人类选手有一些差距。

相比象棋、围棋这样「信息完美」的棋类游戏，和德州扑克这样「信息不完美」的牌类游戏，桥牌、麻将更具挑战，因为它们不仅「信息不完美」，而且拥有更多隐藏空间。这样的性质，使它们更接近人类真实生活中的决策过程。此类游戏 AI 的突破，可能会是下一个游戏 AI 研究的里程碑。

图4：游戏 AI 发展历史

参考资料：

[1]http://www.bridgeguys.com/CGlossary/Computer/CBProgrammers.pdf

[2]http://gameaibook.org/book.pdf

[3]http://www.andreykurenkov.com/writing/ai/a-brief-history-of-game-ai/

你也许还想看：

感谢你关注“微软研究院AI头条”，我们期待你的留言和投稿，共建交流平台。来稿请寄：[e-mail]。