游戏人工智能 读书笔记 （二） 游戏人工智能简史

大部分的棋类游戏的规则都很简单，但是在方寸的棋盘之内，七百年来无数的人类天才都期望找到最优的解法。因此一个可以战胜顶尖的棋手的AI足以成为人工智能的圣杯。人工智能专家寻找棋类AI的历史可以上溯到阿兰-图灵(Alan Turing)和克劳德-香农（Claude Shannon）的时代。在最早的时候，图灵和香农就尝试使用Minimax 算法来让AI下棋，强化学习+自我对弈也很快被Arthur Samuel应用到跳棋(Checker)中(1959年）。

克劳德-香农

棋类AI的发展中的一些里程碑(Milestone)如下：

1952年，A.S. Douglas 开发了第一个 井字棋（Tic-Tac-Toe)游戏

1992年，基于神经网络和temporal difference来进行自我对弈训练的西洋双陆棋（又称 十五子棋）的AI "TD-Gammon" 就达到了人类的顶尖水平。这个AI对于领域外的人来说可能意义不大，但是对于人工智能技术来说，是很重要的一步，其中用到的很多技术也在后续的AI，如Alphago中得到应用。

1994年，Chinook跳棋AI在跳棋世界锦标赛上战胜了世界冠军；到了2007年，跳棋游戏的最优解也被找到了。

Kasparov V.S. Deepblue

1997年，IBM的深蓝在一个令人瞩目的比赛中战胜了当时的国际象棋特级大师 Garry Kasparov。深蓝是基于一个经过大量的国际象棋规则修正和棋盘评估修正后的极大极小算法来下棋的，并且是运行在一台定制的超级计算机上。从人工智能研究的角度来说，可能在圈内没有其在世界上对普通人的冲击来的大。最主要的原因是，在当时的人们看来，国际象棋在某种程度上象征着人类智慧的最高等级。当然，人们不久就将这一荣誉放到围棋上面了。

Alphago 和 李世石 注定载入史册的5番棋

然后到了2016年，Google的DeepMind开发的Alphago在5番棋中战胜了韩国的李世石，这也标记着，围棋也从代表着人类独有的智慧的荣光的神坛上走了下来。而历史的车轮在此刻也在逐渐的加快，第二年，中国的柯洁也在3番棋上输给了升级版的AlphaGo, 而后面DeepMind也迅速的发布了AlphaGo Zero 和 AlphaZero, 基于深度强化学习+MCTS+自我对弈的方式，完全抛弃人类知识，只从棋类的规则出发，不单在围棋上，在国际象棋和将棋上也同样达到了世界最强的水平。因此，一时之间，各种机器狗横行天下。而这一情况，随着Facebook开源了ELF的基于AlphaZero的围棋算法之后会更加的严重。

战胜职业棋手，只需一块GPU

除了棋类游戏之外，牌类游戏也是游戏AI关注的一个焦点。相比于棋类这样的完全信息博弈游戏，牌类这样的非完全信息博弈游戏在本书中的关注不多。一方面来说，牌类游戏有一定的运气因素，同时还牵扯到和对手的博弈，不完全是计算智能所关注的方向，更多的可能要和博弈论相结合。但是最近学术界在两人无限注的德州扑克上取得的突破性进展，还是值得关注的。目前德州AI Libratus是一套完全和围棋不一样的算法，它是基于反事实遗憾最小化（Counter Factual Regret Minimization）的算法来寻找两人博弈的一个纳什均衡点。但是在多人博弈的问题上，例如麻将，多人德州，并没有这样的一个纳什均衡，因此目前还没有比较好的算法。去年的时候，Libratus之父Prof. Sandholm来腾讯演讲的时候就曾表示，目前不会投入精力来做多人的德州AI。

Tuomas Sandholm: 德州AI Libratus的创造者

另一方面，和人工智能发展早期学术界的研究者一门心思的来搞棋类AI相比，游戏业界通常要更现实一些，干活的时候，不管怎么样先搞上线再说。和学术界关注理论上的突破相比，业界会更注重工程方面，不管是多low的算法，好用就行。这也让早期人工智能技术和游戏的结合主要是由业界引领。而他们也关注的领域也会窄一些，大部分的精力都投入到：游戏中的NPC要怎么用算法控制中去，但也有一些使用程序生成内容的尝试。

Halo 2

在最早的时候，受限于硬件设备和AI的能力，大部分的NPC行为都是基于简单的规则来进行控制的。直到微软在2001年推出光晕(Halo), 才让行为树成为大部分游戏控制NPC行为的标配。但游戏开发者一直致力于提高NPC行为的合理性，从而提升玩家在游戏中沉浸感。而在游戏设计的时候，游戏的开发者需要考虑到人工智能技术的限制，用某种方式避免人工智能算法产生”灾难性”的后果，这里面一个经典的例子就是 文明(Civilization)中扔核弹的甘地。

疯狂的甘地

文明2有一个有趣的bug：疯狂的甘地。

早期玩家都知道，印度文明一出现在视野里，必须立刻毫不迟疑地卧薪尝胆跟其他文明媾合、集中全部力量无论多么遥远，也要把印度早早摁死。无论怎样诱人的和平条约，都不要和印度签署，一定要跟甘地（印度的领袖）死磕到底。

否则，一旦印度发展出核武器，就会疯狂地四处乱炸，把全地球彻底搞当。相比之下，鑫十五天简直是个乖宝宝。

原因很简单。游戏设定里甘地是非常和平的，其野蛮度极低。文明发展，野蛮度越来越低，等到原子弹出现的时代，就差不多降到零。降到零是小事，一旦降为负数，程序无法处理负号，于是变成255，极大值。这是比希特勒还疯狂好多倍的数值。于是一个极端和平的甘地，眨眼成了核弹狂魔。

回答来源自知乎用户：齐遨

事实上，大部分的游戏大作都某种程度上结合了一定的人工智能技术，以期让游戏内NPC的行为可以自适应于不同的玩家(V社(Valve)的半条命，世嘉的异形），或者可以自动化的生成游戏中的某些场景（模拟人生系列，文明系列，暗黑破坏神系列）。

另一个游戏业界比较关注的方面是了解游戏中的玩家。这个在最初的时候是更偏重于数据挖掘的，09年的时候Zynga就通过一些数据挖掘技术来分析游戏中不间断收集来的数据，从而可以半自动的更新其在Facebook 上的农场游戏(FarmVille)游戏以适应玩家需求。到了18年的今天，相信各个游戏公司内都会有或大或小的数据分析团队。现在业界大部分都还是基于玩家在游戏外部的一些数据来做数据分析和数据挖掘。不过现在也有一些公司希望通过AI技术来分析玩家在游戏内的行为来更好的对玩家建模。不过这上面也会有一些争议，比如EA提交的“动态难度调整”论文就通过记录玩家在线游戏的方式，包括你的游戏技巧，进攻性，以及游戏瓶颈期（也就是难度时间）来自动为你匹配合适的对手，让你的游戏体验更为平滑，但一方面也是在鼓励你氪金。

EA发布的引起争议论文

近些年来，学术界也开始投入越来越多的精力在视频游戏上面。不过学术界还是更希望能够开发出一个AI可以在视频游戏中也超过人类最高的水平。在视频游戏AI人工智能中一个重要的里程碑是由谷歌的Deepmind在2014年达成的。Deepmind开发的程序以游戏的原始图像作为输入，学会了经典的雅达利(Atari) 2600游戏主机中的一些游戏，并超过人类的最高得分。目前Deepmind和其他的一些团队应该投入了很多精力在研究星际争霸AI，而OpenAI也在研究Dota中的AI。不过目前还没有像围棋一样的突破出现, 只是有一些API提供出来供研究人员去使用。

Deepmind 提供的星际2的建模方式

所以，可以明显看到，学术界和工业界对于游戏人工智能的研究方向是有一定的区别的。对于人工智能的学院派来说，人工智能是在游戏前面的，他们的目标是尽可能的应用人工智能和计算智能的技术来增强NPC的行为能力。但通常他们会关注在一些普遍意义上比较简单，面向研究，很难扩展的项目下，这些项目同时在商业上价值比较低。而游戏业界通常抱怨学术界缺乏领域知识和实践的经验，因此没法解决游戏制作过程中的真实问题和挑战。NPC的实时的自适应和学习就是一个很好的例子。对于学术界的研究者来说，创造一个可以通过和玩家以及其他NPC们进行交互来学习的NPC是令人兴奋的。但是，游戏开发者会担心这样会让这些NPC不按设计那样工作，于是很可能会”破坏整个游戏”。这个其实在聊天机器人上面就出现过教训。几乎所有的没有强规则约束的聊天机器人都被网友们玩坏了。

另外，书中其实提了一个很有意思的观点：

当我们思考怎么在现在的视频游戏中应用人工智能的时候，很重要的是，我们要明白大多数的游戏类型都是从早期的游戏设计中慢慢发展而来的。举例说来，第一个平台游戏是80年代中期发行的，第一个第一人称射击游戏和实时战略游戏都是90年代早期发行的。在那个时代，在游戏中使用先进的人工智能技术的能力是远远不如现在的。所以游戏设计师只能在缺乏人工智能能力的情况下设计游戏。这些基本的设计模式大部分都被现在的游戏继承了。因此可以说，大部分的游戏其实在设计的时候都是不需要人工智能的。对于希望创造一个有趣的人工智能游戏角色的学术界研究者来说，最好的方式可能是设计一种新的从源头上就需要人工智能的游戏。

不过虽然有分歧，乐观的看，其实学术界和工业界没必要用同样的一套方法去解决同样的问题。双方做的事情虽然有区别，还是其实还是可以互相之间带来新的方法和思路。一方面来说，NPC的拟人化还是有更多的提高空间的，比如说情感的捕捉和表达。这个也是学术界和工业界都关注的问题。当然还有一方面的观点是，其实现在NPC已经基本上在工程上被解决了，对于游戏来说，创造一个AI并不是一件困难的事情，可能双方需要更关注一些玩家建模和程序化生成内容的研究。整体上来看，学术界和工业界都是为了共同的目标互相共享实践经验和理论知识：最大程度的推进人工智能技术和改进游戏。

最后，这本书不是关于游戏人工智能在工业界的实践。相反，它本质上是一本学院的教科书，因此要了解更多人工智能在游戏业界的应用情况，可以参考书中的介绍的《游戏人工智能编程智慧》系列。

本文内容包含以下章节：

Chapter 1.2 A Brief History of Artificial Intelligence and Games

本书英文版： Artificial Intelligence and Games - A Springer Textbook