计算机下棋小史

2017 年 12 月 11 日 图灵教育 尼克

这篇文章早先原创发表在乌镇智库（ID：wuzhen-institute），编辑配图非常精彩，直接转载过来，《人工智能简史》一书中收入了第 6 章《计算机下棋：机定胜人，人定胜天》。

拿破仑下棋竟然输给了木头人？

1769年，德国发明家兼外交家沃尔夫冈·肯佩伦（Wolfgang von Kempelen）男爵准备造一台机械的下棋装置，一年后机器完工，取名“土耳其人”（The Turk），那时大家就把这玩意叫作“自动机”（automaton）。肯佩伦把这台机器展示给奥匈帝国的掌权者玛丽娅·特蕾西娅（奥国女大公、匈国女王），于是它就成为娱乐欧洲各皇室的保留节目。

称为“土耳其人”是因为这个装置的后面坐着一个土耳其装束的木头人。1804年，男爵死后，“土耳其人”被转卖给德国发明家约翰·马泽尔（Johann Nepomuk Maelzel），1809年马泽尔把它展示给拿破仑，并和这位不可一世的欧洲征服者对弈一局。

肯佩伦制造的、号称能自动下棋的“土耳其人”，其实是个骗局。（南方周末资料图）

拿破仑执白棋先手，但最后“土耳其人”大胜，拿破仑恼羞成怒，把棋盘上的棋子全胡撸到地上。有好事者把拿破仑和“土耳其人”的对战棋谱记录在案，确实艺不如“机”。陆续和“土耳其人”接触过的名人还有本杰明·富兰克林、爱伦·坡、数学家查尔斯·巴贝奇。

“土耳其人”在欧洲巡演了几十年，最后被人发现是个彻头彻尾的假货：那个装置里总是有个活人，而且是个下棋高手。肯佩伦只是发明了个魔术而已。那时的水平，想造台会下棋的机器，门儿都没有。

1827年，“土耳其人”到美国巡演时，请了美国当时的顶级高手施伦伯杰（Schlumberger）藏匿其中。在巴尔的摩的一次表演中，两个孩子发现施伦伯杰频繁出入后台，把这个秘密透露给了报界。见过这台机器的高人如富兰克林和巴贝奇一开始就猜这是魔术而不是科技。但当时还是很多人愿意相信“土耳其人”真会下棋。

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

图灵

图灵编写了第一个下棋程序

下棋一直就是人类智能的挑战，自然也成了人工智能的标志之一。二战没结束，图灵就研究计算机下棋，他1947年编了第一个下棋程序，可惜那时计算机的时间（简称“机时”）很宝贵，轮不到他上机，地主家也没余粮——图灵也不能保证机时。

但即使后来拿到机时，那机器和程序的水平也很有限。唐米歇（Donald Michie）是图灵的追随者，1950年试着在纸上模拟程序，和图灵对弈，但这实在不是办法。图灵在曼彻斯特大学的同事迪特里希·普林茨（Dietrich Prinz）接着图灵的思路，在1951年写了一个残局程序，能在离将死还有两步的情况下，找到最优解。这个问题也被称为“两步将死”（mate-in-two）问题。

跳棋：人类第一次在棋盘上被打败

1951年，图灵的朋友克里斯托弗·斯特拉切（Christopher Strachey）在曼彻斯特Mark-1上写了第一款跳棋程序。图灵在1952年曾与之对弈一局，轻松取胜。1956年IBM的亚瑟·撒米尔（Arthur Samuel）写了第二个跳棋程序，这款程序的特点是自学习，这也是最早的机器学习程序之一，后来不断改进，曾经赢过盲人跳棋大师。

1980年代末，最强的跳棋程序一直就是加拿大阿尔伯塔大学的Chinook，作者是现任阿尔伯塔大学理学院院长的计算机系教授强纳森·舍佛（Jonathan Schaeffer）。数学家丁斯利（Marion Tinsley）自1950年代起就一直是跳棋的人类冠军。丁斯利对跳棋理论研究很深，对舍佛团队也很支持，但美国、英国和加拿大的跳棋协会一直拒绝Chinook参赛。

1992年，跳棋程序Chinook(奇努克)挑战跳棋高手马里恩·廷斯利(Marion Tinsley)，当时，跳棋程序还是不敌人类。

为了和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的对弈就形成了博弈树。树的增长是指数式的，当树很深时，树的规模会变得不可控。

达特茅斯会议的组织者之一麦卡锡首先提出α-β剪枝术以控制树的增长。纽厄尔、司马贺和肖（NSS，Newell, Simon and Shaw）在他们著名的定理证明程序之后，又做了下棋程序。

他们首先实现了α-β剪枝术。他们的程序是在一台Johnniac上实现的。原始的minimax算法是在博弈树被全部画出后再静态地计算评估函数，而α-β剪枝术则采取边画树边计算评估函数的动态方法。当评估函数的值超越给定的上界和下界时，树的搜索过程就停止，这样大大减少了树的规模。平均而言，同样资源限制下，α-β剪枝术要比原始minimax算法搜索的树深度多一倍，也就是说，可以比minimax向前看的步数多一倍。

第一个可以走完全局的下棋程序，每步要想8分钟

IBM 704

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

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

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

当时MIT的程序员格林布拉特（Richard Greenblatt)也在改进Kotok的程序，格林布拉特本人还是成绩不错的棋手。他在PDP-6上实现了程序MacHack VI。1966年，一直批评人工智能的哲学家德雷福斯也和MacHack对弈过一局，并且输给MacHack，这倒没有改变德雷福斯对待人工智能的态度。

1967年MacHack参加象棋锦标赛，并累计积分1400，这相当于不错的高中生水平。这个程序用了16K内存，后来PDP的厂家DEC把它预装到所有PDP系列的机器中。MacHack也是Internet前身ARPAnet上最早的网上游戏。当时给格林布拉特帮忙的志愿者中有个人叫克柔可（Stephen Crocker），他后来成为Internet前身ARPAnet的重要人物，并创办了互联网标准化组织IETF且写了第一个标准化文本RFC。

为了打败下棋程序，苏联人发明了“众包”方式

司马贺

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

1971年，当年击败Kotok-McCarthy的苏联小组改进了他们的程序，新程序名叫KAISSA（象棋女神）。KAISSA和传奇大师鲍里斯·斯帕斯基（Boris Spassky）赛了两局，一负一和，这个战绩惊动了棋界。1972年KAISSA接受了《共青团真理报》的挑战：KAISSA将和读者们下两盘，《共青团真理报》从读者寄来的各种走法中挑出推荐最多的。这其实就是“众包”概念的雏形。

最终，KAISSA还是一负一和。但1972年鲍里斯·斯帕斯基却又输给美国怪人鲍比·菲舍尔（Bobby Fischer），这是美国第一次在国际象棋领域战胜苏联，尼克松稍晚在会见勃列日涅夫时送了对手一副袖珍国际象棋，成心恶心人家。

苏联神秘的下棋程序打败美国的“冠军选手”CHESS

1970年开始，美国计算机学会（ACM）每年的年会都在晚餐时举行计算机象棋比赛，作为娱乐节目。CHESS连着四年都是冠军。第二届时，纽厄尔的学生汉斯·柏林纳（Berliner）参加了，取得第二名，这鼓舞了纽厄尔，他决定把柏林纳留校，专职在卡内基梅隆研究计算机做计算机象棋。

纽厄尔

柏林纳本人也是国际象棋高手，曾赢得美国通讯赛冠军，他留校后，并没有走教学制（tenure track），而是走了研究口——卡内基梅隆的研究制教员也分三级，研究员（Research Scientist）对应助理教授，高级研究员（Senior Research Scientist）对应副教授，而首席研究员（Principal Research Scientist）对应正教授。后面几年的比赛，都有纽厄尔的学生参加，成绩不错。

1974年，在瑞典斯德哥尔摩召开的“国际信息联合会大会”（IFIP）为了找点乐子，效仿美国计算机学会年会的做法，举行了第一届世界计算机象棋锦标赛。锦标赛的组织者是刚从哥伦比亚大学转往加拿大麦吉尔大学的牛伯恩（Monty Newborn）。

除了计算机下棋，牛伯恩的另一兴趣是机器定理证明，他写过两款定理证明程序，参加各种定理证明比赛，尽管他的下棋程序和定理证明程序在比赛中并没有出色表现，但他写的下棋和定理证明的书却很有意思。

第一次锦标赛，除了美国和加拿大的几位高手外，还邀请了欧洲的几个团队，当然要包括苏联神秘的KAISSA。KAISSA击败了在ACM年会拿了四次冠军的CHESS，赢得头筹，报了两年前斯帕斯基输给菲舍尔的一箭之仇。勃列日涅夫倒是没把当年那副袖珍棋送还给已经下台的尼克松，不知算是小气还是大度。

1980年代最厉害的两个电脑棋手

贝尔实验室总部

进入1980年代，又出了新一茬象棋程序。当时最厉害的两个电脑棋手，一个是跑在超级计算机克雷上的Blitz，另一个则是贝尔实验室的专用机器Belle。

Belle的发明人之一汤普森（Ken Thompson）那可是了不起的人物，在计算机界无人不晓。他最杰出的成绩是发明了UNIX操作系统（现在苹果操作系统，波音747的飞行系统和安卓手机操作系统也都是Unix的变种）和C语言，1999年被克林顿授予“国家技术奖章”。他在计算机下棋上的贡献多少被略视了。在1982年的北美计算机象棋锦标赛上，Belle击败了Blitz。

Belle是第一个取得“大师”称号的计算机棋手。1982年在去苏联比赛的路上，Belle被美国政府在肯尼迪机场海关没收，理由是企图向敌对国家输送先进武器，Belle的终端里确实有当时对苏联禁运的超大规模集成电路。拖了小一年功夫，最后汤普森等破费了600大洋罚款，才赎回Belle，但比赛耽误了。

进入八十年代，机器之间的比赛此起彼伏，但机器和人之间仍然有着不可逾越的鸿沟。1980年，天才爱德华·弗里德金专为计算机下棋建立了弗里德金奖金，奖有三等，头等奖是10万美金，奖给第一款能赢现任世界冠军的下棋机器。

《“深蓝”揭秘：追寻人工智能圣杯之旅》,许峰雄著，上海科技教育出版社，2005。（南方周末资料图）

“深蓝”，像上帝般下象棋

1980年代中期，卡内基梅隆大学的柏林纳开始用专用硬件来做下棋机，他的成果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）仍然不认为机器有智能。

强化学习，靠AlphaGo发扬光大的AI技术

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

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

思路和求圆的面积类似，随机模拟对弈双方走棋。当走棋的次数很多时，就可算出下棋点的概率，然后挑概率最大的地方落子。谷歌的AlphaGo首次引用了强化学习（Reinforcement Learning），使得机器和自己对弈学习。强化学习的发明者是巴托（Andy Barto）和他的学生萨顿（Richard Sutton）。

说来话长，冯诺依曼在普林斯顿设计计算机的主要助手是伯克思（Arthur Bucks），伯克思培养了第一个计算机博士霍兰德（John Holland）。霍兰德发明了遗传算法。伯克思的另一个更有名的学生是Codd（因发明关系数据库而获图灵奖）。

霍兰德的大弟子就是巴托，巴托被神人阿比卜（Michael Arbib）招到麻省大学计算机系，在那里培养了自己的第一个博士生萨顿，在经历了人工智能的此起彼伏后，萨顿现在阿尔伯特大学任教。正是他和已经转向围棋研究的舍佛的碰撞，萌生了把强化学习应用到围棋的想法。在神经网络的低潮期，巴托和萨顿利用他们所在的麻省大学计算机系和GTE实验室资助了一帮同仁，其中就有后来成大气的麦克·乔丹。

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