1.2　游戏AI的历史和背景

关于会下国际象棋的计算机的描述，可以在Norbert Wiener[1]的代表性著作Cybernetics（《控制论》）中找到[11]。Wiener探讨了是否能够开发出可以下国际象棋的机器，如果能够开发出来，是否意味着需要彻底弄明白机器的智能和人类智力的区别。关于这一点，我认为Wiener抱着否定的态度。另一个比较有趣的内容就是，机器是否能够成为不同级别的人类棋手的对手。这一点会与第6章的内容产生联系。

之后，Claude Elwood Shannon[2]在1949年编写的论文（1950年出版）被认为是最早的关于会下国际象棋的计算机的论文[76]。Shannon第一次提出了“分支逻辑树”的想法。这个想法将会与4.2节中的AND/OR树相关。Alan Turing[3]在1951年开发了能够实现Shannon这一想法的程序（以下内容的叙述参考了文献[76]）。但由于当时的计算机无法运行这个程序，于是图灵就让两个人类模仿计算机进行下棋。结果，搜索能力弱的一方输掉了棋局。1956年，这个程序在美国洛斯阿拉莫斯国家实验室（LANL）的称为MANIAC I的计算机上被试着执行。由于受限于当时计算机的计算能力，所以程序被设定为在6×6的棋盘上执行。最终，计算机抓住了人类棋手的失误战胜了人类棋手。实际上，真正意义上成熟的国际象棋程序是在1957年由Alex Bernstein开发出来的。这个程序能够预测到未来两棋步，被评价为“还算过得去的外行国际象棋棋手”。

到了1960年，Richard Greenblatt用PDP-6型计算机开发出了相当强的国际象棋程序。这个程序参与了针对初学者的各种比赛，并获得了冠军。当他再次审视他开发的这套程序时，发现了一个惊人的现象：程序往往会不按照他设计的思路下出一步好棋。这是程序Bug造成的，把最糟糕的选择和6个最好的选择排除在外。关于这个Bug，在程序运行的第一年中一直没有被发现，但实际上程序在各种水平（level）下运行后，下棋的方式以及思考的水准开始不断提高，程序会意识到糟糕的下子方式，并且会尽可能避免全面溃败这样的最坏结局。Marvin Minsky[4]把机器的最糟糕选择定义为机器“内心中的恶魔”（自毁的冲动），并描述道：“就算有恶魔存在，它也会在机器意识到它之前被自动删除。”

此外，在早期的AI研究中，西洋跳棋也是一个重要的内容。Arthur Samuel非常成功地开发出了西洋跳棋AI。他用汇编语言在拥有36位存储位置的IBM700系列的计算机上完成了开发。同时，Samuel还提出了能够显示棋盘盘面，并能高速运算的方案。这个内容和3.6节的位棋盘（Bit Board）相关。

让人惊讶的是，Samuel开发的算法能够学习经验，变得更加强大[74]。Minsky还谈到Samuel开发的这个西洋跳棋程序有着奇妙的缺陷。据说程序会在某个地方发生符号逆转，如主动弃子或主动让对方吃掉。即使有这样的缺陷，但它仍然可以用来进行一场激烈的对决。这个缺陷在某种程度上可以被认为为了胜利而采取的弃卒保车的战术。实际上这是很多西洋跳棋玩家认可的一种战术。如果是这样的话，则需要对棋局的控制具有相当谨慎的权衡感，也就是说，没有直接建立手段（对于棋局的控制）和目的（赢棋）的单纯关系，而是把注意力放在了比手段更加长远的地方。这种情况实际上和人的思考方式以及AlphaGo（见5.1节）的强化学习原理相关。Minsky说过，实际上人脑中会浮现很多不好的思考方式，但一直都在被好的思考方式检查着。人类的意识层无法意识到自己拥有一些可怕的思考方式[5]。也就是说，游戏AI的研究和实现人类级别的智能（强AI）有着密切的关系。在这里描述过的“谨慎的权衡感”和“奇妙的操作”会引申出后文当中提到的蒙特卡罗树搜索（见4.5节）与基于学习的游戏AI（见第5章）。

近几年来，针对游戏以及谜题的AI技术得到了惊人的发展。比如说，2017年发表了能够解开西洋跳棋问题的论文[73]。此外，还原魔方的最短步数一直都被认为需要22步，但最近已经被改写为需要20步。遗憾的是，这个数字是通过谷歌的研究员用全搜索的方法获得的，而不是用AI解开的。这个数字甚至被称为“上帝之数”[6]（Texs hold'em）的论文被发表。在这篇论文里，统计结果表明，采用近似纳什均衡[7]的手法不会输于任何对手。

有一个在国际象棋中人类和游戏AI对弈的历史案例。1997年5月，在纽约曼哈顿举行了一场人类（Garry Kasparov[8]）和AI（深蓝）的对弈[9]。然后，在6次对弈的第6局中，计算机获得了胜利。Kasparov虽拿下了第一局，但第二局输了。实际上本来可以以平局终结的一局，Kasparov却主动选择认输。他本人曾经描述道[17]：“如果对手是人类，碰到同样的局面，我是不会选择认输的，但我对深蓝带来的恐惧产生了动摇，对与深蓝对弈产生了恐慌情绪。”也就是说会忍不住考虑一般人类有时候会下的一步臭棋，计算机不会犯这种低级失误；会忍不住考虑计算机绝对不会允许自己被将军的局面出现。由于脑海中不断浮现这些想法，从而对局势产生误判，最终使自己出现了失误。虽然第3局、第4局以平局结束了，但令人惊讶的是深蓝有在极其不利的局面下把棋局导向平局的能力。虽然第5局也是以平局作为终结，但在对弈的过程中Kasparov有好几次赢棋的机会，很遗憾的是他没有利用好这些机会，用现在的国际象棋分析软件分析的结果，本来有两次能够赢棋的机会（深蓝下过2次臭棋）。在最为关键的第6局，不到1小时的时间Kasparov就选择了认输。关于和深蓝对弈的感想，Kasparov表示：“感觉十分冰冷，感受不到与人对弈的感觉”，此外他还描述道：“简直就像棋桌上坐着一个全新的智能生命体。”[17]

由于这场对决的主办方是IBM，因此对于人类方的Kasparov来说有几个客观上不利的因素——无法提供计算机的日志（思考过程），以及由人类的介入、程序的错误崩溃引起的中断。此外，人类会因为连续对弈而感到疲劳，但机器却不会，甚至机器不会有任何心理负担或压力。基于以上客观原因，最近的人机对弈允许人类选手提前获得游戏AI的程序，可以提前对这个程序的特征进行调查。

在这场人机对弈以后，IBM也终结了针对这次对弈的项目，把解体后的深蓝赠予了史密森尼博物馆和计算机历史博物馆。对于IBM后续没有让深蓝回归比赛或者没有让研究开发继续有很多批评的声音，甚至有人讽刺道：“就像好不容易到了月球，但什么都没探索就回到地球了。”[17]

图1.1　我在学生时代购买的Kasparov国际象棋计算机Travl Mate II（SciSys公司于1986年生产）。它至今还可以运行，可以进行各种水平的对战，相当强大

最近，游戏AI的发展受到了更多的关注。2016年3月，谷歌旗下的DeepMind公司开发出了AlphaGo，在与韩国围棋棋手——李世石的对弈中，5局3连胜的结果给全世界带来了很大的震撼。然后在2018年5月与世界排名第一的中国棋手——柯洁的对弈中3局全胜，最后公开了所有棋谱，从此以后退出了人机对弈的世界（见5.1节）。

值得一提的是在2006年，针对将棋的游戏AI——Bonanza被揭示出超越人类的可能性。这种游戏AI的原理是基于评价函数的学习手法[41]。2015年，日本情报处理学会发布的分析结果表示：计算机在将棋方面的实力已经追赶上了顶级职业棋手。基于这种现状，AI的研究者宣布了计算机将棋项目的终结。将棋名人羽生善治表示：“如果运气好的话，或许能够击败AI，但是只要再花几年，AI的成长速度会到达F1赛车一般。这个时候，人类不会妄想在人机对弈中能够击败AI。”

[1] Norbert Wiener（1894-1964）：美国数学家。他提倡控制论，把基于生物和机械的控制理论和通信理论进行统一作为努力目标。这个理论在社会学、机械工学、系统工程学、机器人学等各种学科领域适用。也作为人工智能学科的支持理论之一。

[2] Claude Elwood Shannon（1916-2001）：美国数学家、电子工程学家。他被称为“信息论之父”，构筑了加密理论和符号理论。此外，他还在晚年期间，在股票和赌博领域实践了自己的理论［37］。

[3] Alan Turing（1912-1954）：英国数学家。在第二次世界大战期间参与破解德军的Enigma密码。他被称为“计算机科学之父”。基于计算理论的图灵机以及基于形态形成的图灵模型［10］使他成为这一领域的先驱。

[4] Marvin Minsky（1927-2016）：美国人工智能学者。也被称为“人工智能之父”。曾经因为证明了深度学习的基础单元——感知器的能力极限而出名［6］。他的名著The Emotion Machine是人工智能研究人员的必读书籍。

[5] 参考了Minsky的The Emotion Machine中的论点。http://www.cube20.org/。

[6] 每个玩家分2张牌作为“底牌”，5张由荷官陆续朝上发出的公共牌，然后进行组合。

[7] 纳什均衡指在对手采取某种策略时，假设自己不采用这种策略就必定会遭受损失的一种策略。比如在猜拳中，唯一能采用的均衡策略就是无论面对什么样的对手，都能够均衡分别出石头、剪刀、布的概率。近几年被称为CFR（Counterfactual Regret Minimization［87］）的近似计算方法被提出来了。

[8] Garry Kasparov（1963-）：阿塞拜疆人。国际象棋的世界冠军（1985-2000期间）。在计算机国际象棋时代到来前的黎明期，就已经将计算机用于国际象棋的数据分析。在20世纪80年代后期，以他的名字命名的国际象棋软件被发售了（见图1.1）。

[9] 1997年，一个叫作Logistello的游戏AI通过6局全胜击败了当时的黑白棋世界冠军村上健。