酷应用

送书 | 计算机下棋简史：AlphaZero 8小时横扫一切棋类的背后

百家作者：AI100 2017-12-11 11:56:29

本文引自人民邮电出版社图灵教育《人工智能简史》的第六章——计算机下棋简史：机定胜人，人定胜天。

本书全面讲述人工智能的发展史，几乎覆盖人工智能学科的所有领域，包括人工智能的起源、自动定理证明、专家系统、神经网络、自然语言处理、遗传算法、深度学习、强化学习、超级智能、哲学问题和未来趋势等，以宏阔的视野和生动的语言，对人工智能进行了全面回顾和深度点评。本书既适合专业人士了解人工智能鲜为人知的历史，也适合对人工智能感兴趣的大众读者作为入门的向导。

参与方式：喜欢这本书，请在评论区留言，和大家分享你正在思考的关于AI的一些困惑，根据评论质量和评论点赞数，前五名同学可获得本书。活动截止时间为12月15日（本周五22点）

Play is the beginning of knowledge.

游戏是知识之源。

——George Dorsey（多尔西）

… because chess requires intelligence.

下棋需要智能。

——Alan Turing（图灵）

机器下棋史前史

1769年，德国发明家兼外交家肯佩伦（Wolfgang von Kempelen）男爵准备造一台机械的下棋装置，一年后机器完工，取名“土耳其人”（The Turk），那时大家就把这玩意叫作“自动机”（automaton）。肯佩伦把这台机器展示给奥匈帝国的掌权者特蕾西娅（Maria Theresia，奥国女大公、匈国女王），于是它就成为娱乐欧洲各皇室的保留节目。称为“土耳其人”是因为这个装置的后面坐着一个土耳其装束的木头人。1804年，男爵死后，“土耳其人”被转卖给德国发明家兼娱乐人马泽尔（Johann Nepomuk Maelzel），1809年马泽尔把它展示给拿破仑，并和这位欧洲不可一世的征服者对弈一局。拿破仑执白棋先手，但最后“土耳其人”大胜，拿破仑恼羞成怒，把棋盘上的棋子全胡撸到地上。有好事者把拿破仑和“土耳其人”的对战棋谱记录在案，确实艺不如“机”。陆续和“土耳其人”接触过的名人还有富兰克林、爱伦坡和数学家巴贝奇。

土耳其人

“土耳其人”在欧洲巡演了几十年，最后被人发现是个彻头彻尾的假货：那个装置里总是有个活人，而且是个下棋高手。肯佩伦只是发明了个魔术而已。那时的水平，想造台会下棋的机器，门儿都没有。1827年，“土耳其人”到美国巡演时，请了美国当时的顶级高手施伦伯杰（Schlumberger）藏匿其中。在巴尔的摩的一次表演中，两个孩子发现施伦伯杰频繁出入后台，发现了这个秘密并透露给报界。见过这台机器的高人（如富兰克林和巴贝奇）一开始就猜这是魔术而不是科技。但当时还是有很多人愿意相信“土耳其人”真会下棋。1838年马泽尔和施伦伯杰相继去世，随后“土耳其人”也退役，被费城的中国博物馆收藏，1854年博物馆的一场大火彻底摧毁了“土耳其人”。

和牛顿、霍金一样，巴贝奇还做过一届剑桥大学的卢卡斯教授，他对所有机器装置都感兴趣，他在看到“土耳其人”时，正在研制第一台机械计算机“分析机”（analytical engine）。他认为他的分析机也可以下棋，但那至多是猜测。

下棋一直就是人类智能的挑战，自然也成了人工智能的标志之一。二战没结束时，图灵就研究计算机下棋，他1947年编了第一个下棋程序，可惜那时计算机的时间（简称“机时”）很宝贵，轮不到他上机——地主家没余粮，图灵也不能保证机时。但即使后来拿到机时，那机器和程序的水平也很有限。米奇（Donald Michie）是图灵的追随者，1950年试着在纸上模拟程序，和图灵对弈，但这实在不是办法。图灵在曼彻斯特大学的同事普林茨（Dietrich Prinz）接着图灵的思路，在1951年写了一个残局程序，能在离将死还有两步的情况下，找到最优解。这个问题也被称为“两步将死”（mate-in-two）问题。

跳棋插曲

1951年，图灵的朋友斯特拉切（Christopher Strachey）在曼彻斯特Mark-1上写了第一款跳棋程序。图灵在1952年曾与之对弈一局，轻松取胜。1956年IBM的塞缪尔（ArthurSamuel，人工智能里程碑达特茅斯会议的参加者之一）写了第二个跳棋程序，这款程序的特点是自学习，这也是最早的机器学习程序之一，后来不断改进，曾经赢过盲人跳棋大师。

20世纪80年代末，最强的跳棋程序一直就是加拿大阿尔伯塔大学的Chinook，作者是现任阿尔伯塔大学理学院院长的计算机系教授舍佛（JonathanSchaeffer）。数学家丁斯利（Marion Tinsley）自20世纪50年代起就一直是跳棋的人类冠军。丁斯利对跳棋理论研究很深，对舍佛团队也很支持，但美国、英国和加拿大的跳棋协会一直拒绝Chinook参赛。为了和Chinook比赛，丁斯利放弃了他的冠军称号。1992年丁斯利大战Chinook并取胜，1994年再战，但在比赛期间不幸确诊患了胰腺癌，不久病逝。丁斯利的公开纪录，除了输给Chinook几局棋外，从没有输给过任何人类棋手。此后Chinook孤独求败。

舍佛团队继续精研跳棋理论和实践，直到2007年，他们证明对于跳棋，只要对弈双方不犯错，最终都是和棋，而Chinook已经可以不犯错。他们的结果发表在2007年9月的《科学》杂志上，自此跳棋这一页就算翻过去了。舍佛的兴趣遂转向德州扑克和围棋。

计算机下棋之初

几乎和图灵同时，冯诺伊曼也在研究计算机下棋，他和经济学家摩根斯顿合作的《博弈论》1944年出版，其中首先提出两人对弈的Minimax算法。香农（Claude Shannon）1950年在《哲学杂志》发表“计算机下棋程序”（Programming a Computer for Playing Chess）一文，开启了计算机下棋的理论研究，其中主要思路在“深蓝”和AlphaGo中还能看到。有趣的是，战时图灵在布莱彻利庄园破解德国密码，而香农在贝尔实验室研究密码理论，其中还用到了他后来发明的信息论。图灵的工作涉及军事，直到1974年才部分解密，而香农则偏理论。图灵战时到访美国普林斯顿大学和贝尔实验室，曾和香农多次会晤，但他们从来没聊过密码学，尽管香农猜到了图灵在干啥。1950年香农去英国参加信息论会议时到曼彻斯特大学图灵的办公室回访，他们这次只聊了下棋和大脑，仍然没聊密码。图灵没有参加这次在伦敦的会议，但贡献了两篇短文，一篇讲机器学习，另一篇讲下棋。直到图灵的工作解密，香农才知道图灵在战时已经用到了“熵”，但是不是从了解信息论的美国同事处学来的就无从考证了。信息安全专家史密斯（S. W. Smith）曾写过一篇题为“图灵来自火星，香农来自金星”的文章，很明显这是受那本《男人来自火星，女人来自金星》的启发。

香农把棋盘定义为二维数组，每个棋子都有一个对应的子程序计算棋子所有可能的走法，最后有个评估函数（evaluation function）。传统的棋局都把下棋过程分为三个阶段：开局、中局和残局，不同阶段需要不同的技术手段。香农的论文引用了冯诺伊曼的《博弈论》和维纳的《控制论》。

Minimax算法中，二人对弈的一方为max，另一方为min，max一方的评估函数要越高越好，min一方的则越低越好。max和min的对弈就形成了博弈树。树的增长是指数式的，当树很深时，树的规模会变得不可控。达特茅斯会议的组织者之一麦卡锡首先提出α-β剪枝术以控制树的增长。纽厄尔、司马贺和肖（Newell，Simon，Shaw，简称NSS）在他们著名的定理证明程序之后，又做了下棋程序。他们首先实现了α-β剪枝术，其程序是在一台Johnniac上实现的。原始的Minimax算法是在博弈树被全部画出后再静态地计算评估函数，而α-β剪枝术则采取边画树边计算评估函数的动态方法。当评估函数的值超越给定的上界和下界时，树的搜索过程就停止，这样大大减少了树的规模。平均而言，在同样资源限制下，α-β剪枝术要比原始Minimax算法搜索的树深度多一倍，也就是说，可以比Minimax向前看的步数多一倍。

第一个可以走完全局的下棋程序是IBM的工程师伯恩斯坦（Alex Bernstein）1958年在一台IBM 704上做的。估计那时IBM支持下棋就像后来支持“深蓝”和谷歌支持AlphaGo一样，虽没什么短期实用价值，但是很好的公关。机器每步要花8分钟想，随便会走几步棋的人就能击败这个程序。

1959年，麻省理工学院的几位本科生在当时刚到校任教的麦卡锡指导下开始学习计算机下棋，他们1962年本科毕业时，用Fortran实现了一款实战下棋程序，跑在IBM新出的 7090大型机上，此时已经可以击败一般的象棋初学者了。这个结果变成了其中一位学生Kotok的本科学位论文。1962年麦卡锡前往斯坦福大学任教，他进行了持续改进，这个程序后来被称为Kotok-McCarthy程序。

1966年，美苏的对抗也扩展到计算机下棋。苏联科学院的理论与实验物理研究所（ITEP）也在本所研制的一台M20计算机上开发了一款下棋程序，他们要和斯坦福大学的Kotok-McCarthy程序一决高下。从1966年11月22日开始，直到1967年3月10日止，他们通过电报的方式走了四局。最后苏联3:1战胜美国。

当时麻省理工学院的程序员格林布拉特（RichardGreenblatt）也在改进Kotok的程序，还是位成绩不错的棋手。他在PDP-6上实现了程序MacHack VI。1966年，一直批评人工智能的哲学家德雷弗斯[1]也和MacHack对弈过一局，并且输给了MacHack，这倒没有改变他对待人工智能的态度。1967年MacHack参加象棋锦标赛，并累计积分1400 ，这相当于不错的高中生水平。这个程序用了16KB内存，后来PDP的厂家DEC把它预装到所有PDP系列的机器中。MacHack也是Internet前身ARPANET上最早的网络游戏。当时给格林布拉特帮忙的志愿者中有个人叫克柔可（Steve Crocker），他后来成为Internet前身ARPANET的重要人物，并创办了互联网标准化组织IETF且写了第一个标准化文本RFC。

司马贺在1957年预言十年内计算机下棋程序可以击败人类，明显未果，于是他在1965年再度预言这个目标在20年内可以实现。1968年国际象棋大师列维（David Levy）和麦卡锡打赌十年内机器不可能赢列维。1978年最厉害的计算机程序CHESS和列维比了一盘，自然是列维赢，麦卡锡为此输了500英镑。CHESS在20世纪70年代末80年代初一直是计算机下棋的冠军。此时尚看不到计算机短期内可以赢人的可能性。

1971年，当年击败Kotok-McCarthy的苏联小组改进了他们的程序，新程序名叫KAISSA（象棋女神）。KAISSA和传奇大师斯帕斯基（BorisSpassky）赛了两局，一负一和，这个战绩惊动了棋界。1972年KAISSA接受了《共青团真理报》的挑战：KAISSA将和读者下两盘，《共青团真理报》从读者寄来的各种走法中挑出推荐最多的。这其实就是“众包”概念的雏形。最终，KAISSA还是一负一和。但1972年斯帕斯基却又输给美国怪人菲舍尔（BobbyFischer），这是美国第一次在国际象棋领域战胜苏联，尼克松稍晚在会见勃列日涅夫时送了对手一副袖珍国际象棋，成心恶心人家。

1970年开始，美国计算机学会（ACM）的年会都在晚餐时举行计算机象棋比赛，作为娱乐节目。CHESS连着四年都是冠军。第二届时，纽厄尔的学生柏林纳（Hans Berliner）参加了，取得第二名，这鼓舞了纽厄尔，他决定把柏林纳留校，专职在卡内基梅隆大学研究计算机做计算机象棋。柏林纳本人也是国际象棋高手，曾赢得美国通讯赛冠军，他留校后，并没有走教学制（tenure track），而是走了研究口——卡内基梅隆的研究制教员也分三级，研究员（Research Scientist）对应助理教授，高级研究员（Senior Research Scientist）对应副教授，而首席研究员（Principal Research Scientist）对应正教授。后面几年的比赛，都有纽厄尔的学生参加，成绩不错。

1974年，为了给在瑞典斯德哥尔摩召开的“国际信息联合会大会”（IFIP）找点乐子，组织者仿效美国计算机学会年会的做法，举行了第一届世界计算机象棋锦标赛。锦标赛的组织者是刚从哥伦比亚大学转往加拿大麦吉尔大学的牛伯恩（Monty Newborn）。除了计算机下棋，牛伯恩的另一个兴趣是机器定理证明，他写过两款定理证明程序，参加各种定理证明比赛。尽管他的下棋程序和定理证明程序在比赛中并没有出色表现，但他写的下棋和定理证明的书却很有意思。第一次锦标赛，除了美国和加拿大的几位高手外，还邀请了欧洲的几个团队，当然要包括苏联神秘的KAISSA。KAISSA击败了在ACM年会拿了四次冠军的CHESS，赢得头筹，报了两年前斯帕斯基输给菲舍尔的一箭之仇。勃列日涅夫倒是没把当年那副袖珍棋送还给已经下台的尼克松，不知算是小气还是大度。

进入20世纪80年代，又出了新一茬象棋程序。当时最厉害的两个电脑棋手，一个是跑在超级计算机克雷上的Blitz，另一个则是贝尔实验室的专用机器Belle。Belle的发明人之一汤普森（Ken Thompson）那可是了不起的人物，在计算机界无人不晓。他最杰出的成绩是发明了UNIX操作系统（现在苹果操作系统、波音747的飞行系统和安卓手机操作系统都是Unix的变种）和C语言，1999年被克林顿授予美国“国家技术奖章”。他在计算机下棋上的贡献多少被略视了。在1982年的北美计算机象棋锦标赛上，Belle击败了Blitz。Belle是第一个取得“大师”称号的计算机棋手。1982年在去苏联比赛的路上，Belle被美国政府在肯尼迪机场海关没收，理由是企图向苏联输送先进武器，Belle的终端里确实有当时对苏联禁运的超大规模集成电路。拖了小一年功夫，最后汤普森等破费了600美元罚款，才赎回Belle，但比赛耽误了。

20世纪80年代，机器之间的比赛此起彼伏，但机器和人之间仍然有着不可逾越的鸿沟。1980年，天才弗雷德金（Edward Fredkin）专为计算机下棋建立了弗雷德金奖金，奖有三等，头等奖是10万美元，奖给第一款能赢现任世界冠军的下棋机器。

“深蓝”

20世纪80年代中期，卡内基梅隆大学的柏林纳开始用专用硬件来实现下棋机，他的成果HiTech马上成为最强的机器棋手。这时来自中国台湾的许峰雄到卡内基梅隆大学计算机系跟随孔祥重读计算机体系结构（常说的“硬件”）方向的博士，孔祥重是孔子的嫡孙。许峰雄的室友很快把他拉到HiTech项目帮忙设计一个硬件的评估函数，但许峰雄却和柏林纳关系不睦。在资金有限的情况下，许峰雄和几个研究生利用业余时间快速开发出了ChipTest，而ChipTest立即变成了HiTech的竞争对手，并受到柏林纳的打压。许峰雄在计算机系也变成众矢之的，每次都是靠导师孔祥重的帮忙化险为夷。ChipTest的改进版“深思”（Deep Thought）1989年赢得弗雷德金二等奖：成为第一个国际象棋特级大师的机器棋手，累计分超过2400。随后HiTech也加入这个行列。而此时IBM意识到“深思”的商业价值，于是劝说整个团队在毕业后加入IBM，开发下棋机，把对手锁定为当时的世界冠军俄罗斯特级大师卡斯帕罗夫。卡斯帕罗夫对机器下棋非常熟悉，他在屡次和机器对决后曾说：机器下棋没有洞见（insight）。

IBM的外号叫Big Blue，于是新的项目1996年被命名为“深蓝”（Deep Blue）。1996年ACM年会的闭幕节目是“深蓝”对决卡斯帕罗夫，六局棋。“深蓝”旗开得胜，第一局就赢了老卡，最后还是老卡4:2赢得决赛。但此时老卡对“深蓝”刮目相看，他说机器对手不光有洞见，而且有几步简直像“上帝下的”。

第二年“深蓝”和老卡再战，老卡号称要捍卫人类的智力尊严。他赢了第一局，但随后则越来越保守，彻底输给“深蓝”。老卡下棋过程非常情绪化，这有时会给人类对手施加压力，但“深蓝”压根不吃这套。1997年5月11日，老卡认输，“深蓝”成了第一位战胜当时世界冠军的机器。事后，卡斯帕罗夫回忆：第二局是关键，机器表现超出他的想象，它经常放弃短期利益，表现出非常拟人的危险（“showing a very human sense of danger”）。

在“深蓝”赢了卡斯帕罗夫之后，职业棋手并没有因此而改行，他们反而更多地依赖计算机来训练。而职业比赛的解说者也越来越多地借助计算机程序来分析解说一场比赛。机器作为教练，反而更快地帮助人类棋手进步。有美国高中的象棋教练观察到从来就没有过这么多年轻棋手在年龄很小时就积分这么高，这都得益于计算机教练，因为过去的孩子从来就没有机会能和特级高手比赛。

瑞典青年棋手卡尔森（Magnus Carlsen）就是如此。内行说卡尔森的下法很像计算机。2013年卡尔森在印度的金奈（Chennai）客场击败印度老将、卫冕冠军阿南德。现在两台个人电脑下棋，人已经看不懂它们在下什么。尽管如此，“深蓝”队员，同样毕业于卡内基梅隆大学的坎普尔（Murray Campbell）仍然不认为机器有智能。这其实是整个“深蓝”团队的意见，他们都不是人工智能出身，反而和同系的人工智能教授结下梁子。“深蓝”获胜后，美国人工智能学会（AAAI）曾经组织过一个研讨会，对人工智能启发式搜索做出过杰出贡献的加州大学洛杉矶分校教授科夫（Rich Korf）曾不满“深蓝”团队的立场。

围棋和AlphaGo

相对于计算机在国际象棋中的胜利，中国象棋的进展一直落后。一些外行认为中国象棋要比国际象棋难，其实非也。“深蓝”胜利之后，聪明人认为计算机下棋这事已经到头了，没人愿意费力不讨好，IBM也解散了“深蓝”团队。迟至十年后的2006年，中国象棋程序开始击败特级大师级别的人类棋手。倒是围棋确实更具挑战性，但围棋在西方没什么受众，自然没什么聪明人愿意花时间。

围棋的棋子多，组合可能性也多，画出博弈树的所有可能枝叶后，在上面跑α-β不太经济。于是聪明人想到了蒙特卡洛方法。蒙特卡洛方法最常用的教学例子就是计算圆的面积：在一个正方形里贴边画一个圆，然后随机向这个正方形里扔沙粒，扔到足够多时，开始数有多少沙粒落在圆里，结果除以所扔沙粒总数再乘以正方形面积，就是圆的面积。

思路和求圆的面积类似，随机模拟对弈双方走棋。当走棋的次数很多时，就可算出下棋点的概率，然后挑概率最大的地方落子。谷歌的AlphaGo首次引用了强化学习（Reinforcement Learning），使得机器和自己对弈学习。强化学习的发明者是巴托（Andy Barto）和他的学生萨顿（Richard Sutton）。说来话长，冯诺伊曼在普林斯顿大学设计计算机的主要助手是伯克斯（Arthur Burks），伯克斯培养了有史以来第一个计算机科学的博士霍兰德（John Holland）。霍兰德发明了遗传算法。霍兰德的一个有名的学生是科德（Edgar Codd），因发明关系数据库而获图灵奖。巴托是霍兰德的一个大器晚成的弟子，巴托博士毕业后被神人阿比卜（Michael Arbib）招到麻省大学计算机系，在那里培养了自己的第一个博士生萨顿。在经历了人工智能的此起彼伏后，萨顿现在阿尔伯特大学任教。正是他和已经转向围棋研究的舍佛的碰撞，萌生了把强化学习应用到围棋的想法。在神经网络的低潮期，巴托和萨顿利用他们所在的麻省大学计算机系和GTE实验室资助了一帮同仁，其中就有后来成大器的麦克·乔丹。

强化学习从20世纪80年代就被发明，但一直不被重视，是AlphaGo使得它发出亮光。萨顿还值壮年，AlphaGo团队里就有4个萨顿的学生，其中包括首席科学家席尔瓦（David Silver）。巴托老兵不死，在做了一届计算机系主任后，几年前从麻省大学退休了。退休前，他终于看到强化学习渐成显学，他和萨顿合著的《强化学习》马上要出第二版了。

参考文献指南

Standage (2002)是关于最早的下棋机“土耳其人”最完整的描述，有兴趣深究历史的读者不妨翻翻这本书。
牛伯恩（Monty Newborn）是加拿大麦基尔大学计算机系的教授，他的主要研究方向一是机器定理证明，二是计算机下棋，而且他是实战派，他和他的学生做过几个机器定理证明的程序和计算机下棋程序，尽管成绩都不是很好，但他为学界做出了贡献。Newborn (1975)对机器下棋的早期历史有详实考证。
许峰雄的《深蓝解密》（Hsu (2004)）是一本关于IBM“深蓝”历史的书，对卡内基梅隆大学计算机系的内部政治也有精彩披露，可读性很强，近乎历史小说。而Newborn (2002)是一本关于IBM“深蓝”更加偏重技术也更加公正的读物。

[1] 那时德雷弗斯的那本后来引起争议的《计算机不能干什么》还没出版。

感谢图灵教育对本次活动的支持

热文精选

干货！这里有一份神经网络入门指导，请收下！

重磅 | 2017年深度学习优化算法研究亮点最新综述火热出炉

Reddit热点 | 想看被打码的羞羞图片怎么办？CNN帮你解决

多图 | 从神经元到CNN、RNN、GAN…神经网络看本文绝对够了

重磅 | 128篇论文，21大领域，深度学习最值得看的资源全在这了（附一键下载）

资源 | 多伦多大学“神经网络与机器学习导论”2017年课程表

爆款 | Medium上6900个赞的AI学习路线图，让你快速上手机器学习

Quora十大机器学习作者与Facebook十大机器学习、数据科学群组

TensorFlow下构建高性能神经网络模型的最佳实践