第十章 计算机——未来的象棋之王

到此为止，我们所注意的大部分是计算机科学中的理论问题，计算机和人在原则上能进行哪些类型的计算。我们已经讨论的限制都是无条件的。如果综合性理论学家能够证明他们的推测是真实的，那么旅行推销员问题就不可能找到有效的解法。这既不是因为数学家的问题，也不是计算机缺少适当的运算工具；而是根本没有这种工具，将来也决不会有。

大多数的数学家和计算机科学家都不会遇到理论上难以超越的限制。他们所面临的障碍都是自我设置的，而且都是可以超越的，至少在原理上是可以超越的。一个主要的障碍——在数学之外的许多工作中也很突出——就是这样一种倾向：稳妥的做法是照搬被普遍接受的他人的解题方法，即使这些方法不是那么圆满。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂来，否则就会招来他人的嘲笑。本章内，让我们看看汉斯·伯利纳的开拓性工作，他制造了一台能够下好国际象棋的计算机。下一章，我们则将探讨W．丹尼尔·希利斯的工作，他试图用他自己的改革性设计取代曾很好地为电子计算机服务了40年的基本体系结构。

汉斯·伯利纳是美国匹兹堡市卡内基-梅隆大学计算机学科的研究人员，他本人态度文雅，还很想跻身于世界佼佼者行列。他曾经有过这样的荣誉，现在也想为他的计算机成果赢得同样的荣誉。1968年，他曾以42步一盘棋的卓越成绩击败了苏联足智多谋的国际象棋策略家J．埃斯特林，成为国际象棋通信比赛的世界冠军，为此他曾扑在棋盘上琢磨战术整整500小时。1979年，他又设计了称为BKG（15子棋）9．8的计算机程序，并在蒙特卡洛城举行的大做广告的15子棋①比赛中，以7－1的压倒比分击败了世界15子棋冠军意大利的卢吉·维拉。伯利纳也和他自豪的父亲一样，他很高兴，BKG9．8程序已成为第一台能在任何棋盘上或纸牌游戏比赛中击败人类世界冠军的机器。

现在，BKG9．8程序已被搁置起来，世界15子棋联合会已禁止在正式比赛中应用计算机，但是，由伯利纳和他的研究生卡尔·埃贝林设计的一种称为Hitech（高科技）的新计算机程序却在另一种棋盘竞赛场所中保持了计算机的荣誉。1985年10月，Hitech程序赢得了北美计算机国标象棋的冠军称号。这项成功与其他一连串击败人类天才的胜利一起，完全证明了Hitech程序在下国际象棋方面优于任何其他计算机，也优于参加美国国际象棋协会认可的各种比赛的30，000名高明棋手（“思维”人）的99％。

现在，伯利纳已注视着弗雷德金奖金，这项10万美元的奖金将给能击败人类世界冠军的第一台计算机的设计师。Hitech程序目前要击败人类世界冠军力量尚不足。但就伯利纳的顽强性格、教育情况与比赛纪录来看，其程序的前途是不可低估的。

若按年月顺序来看，伯利纳早先热爱国际象棋，而后才爱他的计算机。他1929年出生于德国， 8岁时随父母迁居美国，定居在首都华盛顿。他发现那里的学校的要求比德国松得多，因此他寻求课堂外的挑战。在1942年的夏令营时，他看到了一些年轻人在下国际象棋，就向他们请教比赛规则。伯利纳回忆说：“甚至就在第一天，已有些棋手成为我的手下败将，情况就是这样。我从此着了迷。”

两年以后，他是他所在地区国际象棋俱乐部的冠军，并且保住华盛顿地区最佳国际象棋俱乐部冠军的称号。伯利纳说道：“我父母从不鼓励我。他们警告我说，如果我把时间都花在下棋上，我将没有什么前途。如果没有人告诉我，谁知道我将成为什么样的人？”不过在短期内，伯利纳未控制自己的棋瘾。到了1949年，他终于赢得了人人盼望的华盛顿市国际象棋冠军称号，那时他刚刚20岁，这是个破纪录的年龄。

同年，美国数学家克劳德·香农发表了一篇颇有影响的论文，他在论文中概括地论述了如何编制计算机下国际象棋的程序。当时电子计算机刚刚问世，但是，下国际象棋已被作为在新生的人工智能领域中的一个重要的目标。它与其他智力游戏不同，国际象棋引起人们的兴趣是因为在控制的条件下，通过让计算机与人类选手对阵就可以精确判断出计算机在国际象棋上的能力。参加比赛的棋手都有数字的等级，这是根据他们与其他等级对手比赛时的成绩如何而定的。计算机也要取得等级，以反映它与人的等级棋手比赛所获得的成绩。

当计算机科学的先驱们努力把香农的想法付诸实践时，年轻的伯利纳正集中精力于下国际象棋。1954年，他是这个国家中最佳的12名棋手之一，并保持了12年。50年代初期，他阅读有关计算机下棋的第一批研究成果。他回忆说：“他们的把戏在我看来是相当可笑的。”

英国数学界杰出人物艾伦·马西森·图灵也是计算机的开拓者之一，他是人工智能方面有创造性的思想家（已在第八章中论述过），而且，惮精竭虑地穷究数学领域的奥秘。他还是一名国际象棋手，和爱因斯坦一样，即使算不上精通，也至少乐此不疲；也许由于他认为国际象棋是少数几种他未掌握的智力活动之一，因此他毕生热爱这项活动。不管情况如何，他至少撰写了6页有关以机械方式下国际象棋的配方性棋步，这实际上是一种计算机程序。虽然他还没有花费精力把下国际象棋的方法译成编码输入计算机，但他曾用这些配方棋步于1952年与阿利克·格伦尼对弈。阿利克·格伦尼是英国曼彻斯特大学的一名学生，他也是很有才能的计算机程序设计者，但却是一名不大高明的木材推销员。图灵的纸上下棋机（所以这么叫它是因为它还只是在纸张上存在）在那次对弈中失败了，但毕竟是首次用任意一种理想化的或者可以实现的计算机下棋。

图灵的配方是给每个棋子以数量价值，像国际象棋教科书所定级的那样，以便大体上反映各棋子的相对实力：王1，000，后10，车5，象3．5、马3和兵1。在选择棋步时，都是接着走所有后续棋步，包括捉子在内，一直走到两方既不能吃子也不能给予将死的静止棋势时为止。对于每种静止棋势，两方的相对实力是把棋子的数值加在一起进行计算的，并把计算机的棋子数值看成正数，把对方的棋子数值看成负数。选择导致静止状况的棋步，在这种状态中，机器能使其相对实力增加到最大限度。

图灵的估值方案是能够找到求胜的棋步的，但是在静态情况下则无法使用。例如，它不能判别白方的头一步如何走，因为在比赛开始时，在其20个可能的棋步（16个进兵步和4个上马步）中，没有一步棋捉子或者可能捉子，因此这20个静止棋势都是同样0值的相对实力，显然，要用该方案判断是很荒谬的。

图灵还用加权的方法来克服这个问题，在静态棋位中考虑诸如机动性与王的安全性等因素。例如对兵来说，走兵越过自己的布阵之后，每横线增加0．2，如果受到别的子而不是本方兵的保卫，则另加0．3，如果不受到保卫，则要另减0．3。对于车、象、马和后来说，如果走它们能走的法定棋步，则每走一步棋都增加其数值的平方根，如果这些棋步中至少有一步棋可以捉子，则另加1点。而且，要是车、象、或马（不包括后）受到保卫，得到保卫一次另外奖给1点，两次或两次似上另外奖给2点。如果王得到车的保卫，则加0．3，如果与车保持均势，则加0．2，要是以车保王未来仍能出现，则加0．1。

图灵也考虑王的安全性。在他的估值方案中，王所要损失的点数取决于它易于受到攻击的程度。图灵设想王是另一个后，并计算这个后的机动性，用此来量度其受到攻击的程度。此外，图灵还给攻对方王棋的棋步增加0．5，给立即能将对方王棋的威胁性棋步增加1。

在静态情况下，纸上下棋机将按照其求值函数、最大的机动性、本方王的安全性以及对方王的易受攻击性来决定棋步。在1952年与格伦厄博弈时，纸上下棋机以P－K4开局，即走王前兵两步，在20个可能棋步中，P－K4棋步具有最大的数值，这个棋步不仅可以进兵到第四横线，而且还可以提高后、王前象和王前马的机动性。早在第三步棋时，纸上下棋机走了一步软着的兵出击，但格伦尼并没有乘机利用它。在第二十九步棋时，由于纸上下棋机的求值函数示出格伦尼没有立即有效的捉子应步，因此它贪婪地用后吃掉一兵。

纸上下棋机的程序忽视一个简单然而可以压车的棋步，该棋步可以用下棋机的后看住对方的王，使得后可以强行捉子。最后，图灵这个安乐死控制论的倡导者，代表纸上下棋机主动认负。

纸上下棋机尽管非常原始，仍然有一些独到之处。例如，它认为，只有在没有任何捉子的可能时，实力的研究才有重要性。在棋盘上的某一棋位中，你可能缺少后，这种情况通常是很糟的，但只要是该你走子，你仍有机会，你可能捉住对方的后。你大概不需要一个估值的过程，它只不过统计出棋子的相对实力，却没有把可能的捉子考虑进去。

当图灵把诸如机动性与王的安全性等国际象棋知识的一些方面包括在求值函数之内时，他的思路是正确的。在与格伦尼博弈时，纸上下棋机的棋输掉了是由于这些知识还不够充分。它不能辨别在特定的棋局中的内在的危险性：王与后在同一纵列上。

伯利纳和其他国际象棋大师，甚至许多很不熟练的棋手都把这种棋局和不计其数的其他棋局牢记在他们脑子里。研究证明，人类国际象棋大师对棋局和棋位都有非凡的记忆力，而且这种优异的记忆力不一定会转移到与国际象棋无关的事物上。站在人的水准上，伯利纳觉得，他在棋盘上所享受到的成功的喜悦没有延续到教室中，至少在最初时没有。

伯利纳回忆说：“一些人往往刚上大学不久，就会遇到麻烦，我就是其中之一。本来，我曾是一名物理学的优等生，但是不知怎么一来，我走上了岔道。我一边打工，一边上学，终于攒够了钱来付学费，可以不再打工。这是一个关键性的错误，忽然间我有了很多时间，因此除了下国际象棋之外，我还打桥牌。很快地，我就成为华盛顿市15名最佳桥牌手之一。一切都砸了锅。”

伯利纳服完兵役后，想返回学校。他接着回忆说：“我未能完成物理学学业，因为我的平均学分太低，因此我转修心理学。看来这是个广阔的研究领域，因为全是些有兴趣的事。”伯利纳是从物理学转来的，他期望能把事实归纳成理论，但是他失望地发现，情况恰好不是那样。

1954年，伯利纳结婚了，在家庭生活与新工作之余，几乎没有时间打桥牌，不过他还是想方设法继续下国际象棋。他接着说道：“我在美国海军研究实验室从事称为人类工程的工作。那是非常严肃的工作，牵涉到心理学与物理学，与设备的设计有关。那是在1955年，当时计算机刚刚问世，实验室里也造出一部。我曾修过一门程序设计课程，大概编写过20行有关加数的程序，但是除此之外，我没有接触过计算机。”

“因为没有时间旅行去参加国际象棋比赛，我决定参加通信国际象棋活动。这又是另一项重大错误。它无休止地在棋盘上花去我更多的时间。随后的13年内，我参加了许多国际象棋的通信比赛，并且赢得了所有比赛。在世界通信锦标赛中，我必须下16盘棋。我估计，要思考每一步棋，平均需要花去4个小时的时间，一盘棋大约需要走35步，这就意味着，要赢得该比赛冠军，我要投入2，200多小时的时间。接着，我实际上还是放弃了该项比赛。”他考虑为了保持该项冠军还得再花2，200多小时的时间，是很不值的。

1961年，伯利纳进了美国马里兰州贝塞斯达的国际商业机器公司（IBM），成为一名系统分析家，并且主要工作是面向军界。虽然他在那里工作了8年，而且奋力进取，升任了经理，但他仍觉得这项工作得不偿失：“如果你很认真地工作，这是一种可怕的生活。作为一名经理，你必须对上下都要负责任。你有一批人为你工作，但他们的确对工作毫不关心。还有一个家伙来自军界，他其实什么都不懂，还对你指手画脚，或提出一些无理要求。后来又有一个人接替了这个家伙的工作，他根本不知道第一个人想要什么，于是命令改变一切。我开始觉得，我所要做的工作应该是，在我回首往事时，能使我感到骄傲的工作。我希望从事研究工作。”

伯利纳继续进行用计算机远距离下棋的探索，但他看到进展很慢，感到失望。在50年代期间，学者们曾做过乐观的预测，但它与实验室内的成功不相吻合；例如，1957年，美国卡内基-梅隆大学现代诺贝尔荣誉获得者罗伯特·西蒙就曾声称数字计算机将在10年内成为世界的国际象棋冠军。

计算机程序设计的重要性还没有完全得到认识。按照公众的看法，国际象棋大师就像一种人类的计算机：当他选择一步棋时，他在心目中还要探索几百步后续棋，如果我上了王前兵，那么他将同时攻我两车，而后我将捉他的后……都以惊人准确的闪电速度下棋。计算本来是计算机的主要功能，因此它们在国际象棋上似乎应该是天生的冠军。问题在于公众的这种看法是错误的，对于国标象棋大师来说，计算不是惟一的甚至不是成功的主要的秘诀。他们的成功更多地取决于对棋局的判断，而不是研究那些令人头痛的棋步。

荷兰的心理学家安德里安·德格鲁特发现，在典型的棋法中约有38步可能的法定棋步，而国际象棋大师平均只考虑其中的1．76棋步。换句话说，一位象棋大师通常根据自己曾经下过或看到别人曾经下过的成千上万步棋，在他所能判断的两个候选棋步中进行选择，这种选择对实现该棋步的眼下和长远目标有利。美国的一位国际象棋特级大师威廉·隆巴迪老人曾经写道：“在实现目的之后，即取胜的布局转变成为数学上的强力取胜的时刻，计算最为常见。”只要花一两秒钟，就能一眼认出所熟悉的布局，这是象棋大师们在棋赛中具有惊人优势的根本原因。在动态的棋局中，简直没有时间进行预测。

许多早期的计算机程序都只局限于考虑选择候选棋步的数量（尽管它根本就不会是1．76这么小的数）。应用选择搜索方法的问题在于没有人知道如何用计算机语言，更不用说是用英语，来表示用于选择候选棋步的一般失效保险原理。 1966年，由美国麻省理工学院的理查德·格林布拉特研究的早期选择搜索程序MacHack最为成功，它已成为在比赛中击败人类棋手（即使是最弱的一名棋手）的第一部国际象棋计算机。MacHack程序还有幸驳倒了休伯特·德赖弗斯的看法，德赖弗斯是《计算机不能做些什么》一书的作者，他曾靠贬低计算机的能力而出了名。

然而MacHack的功能一般说来还有严重的缺陷。虽然它在下棋时能够胜任持续时间很长的棋局，但它还是易于突然犯下某种可笑的错误，而这种错误多少是由编入该计算机程序的象棋原理造成的。此外，它有时也会对某些巧妙但却显然违背了象棋原理的棋步视而不见。但是它已在比赛中击败了人类棋手，因而是计算机国际象棋的里程碑。

伯利纳回忆说：“我的上帝！当我听到有关MacHack程序取得胜利的消息时，我认为，尽管计算机国际象棋受到如此冷遇，尽管人们做了种种努力却收效甚微，但还是有希望的。我去拜访格林布拉特先生，虽然我还不完全理解计算机真的会按他所希望的去做，但我还是留下了深刻的印象。由于我离了婚，还没有再婚，我又一次有了许多时间，因而我自学计算机程序设计，并花去许多晚上和周末时间编写计算机国际象棋程序。我向美国国际商业机器公司申请让我到该公司在纽约的约克顿海特斯研究机构中从事计算机国际象棋的工作。他们答复说：‘我们不资助这类项目。而且，你还没有博士学位，因此，如果你能做些对公司有益的其他事的话，我们顶多让你稍微做一点这方面的工作。’”

“我认为，要达到我的目的，惟一的途径是获得博士学位，以便进入该公司。我对自己的基本情况很自负。我向几个学校提出了申请，但只有卡内基-梅隆大学接受我。”他在1968年获得世界通信国际象棋比赛冠军的胜利显然有助于他进入该校。

“因此，我是在1969年秋季40岁时成为一名学生的。这对我是多么大的震惊。我觉得我需要学习的东西实在太多了，像自动化理论、各种不同的程序设计语言、多种多样的硬件配置、以及人工智能本身等等。”伯利纳早年在高等学校中不喜欢的许多课程，现在反而都要修读它们。

在卡内基-梅隆大学时，伯利纳继续进行他在国际商业机器公司空余时间内开始的计算机程序设计工作。1970年，在美国纽约市举行的第一届美国计算机国际象棋锦标赛上，一种叫做J．Biit的计算机程序（其英文发音与“正好由于它在那儿”的英文首字母缩写词的发音相近）做出相当不错的表演。J．Biit程序也和MacHack程序一样，用选择搜索法工作。该程序的实力就是它的估值函数，即它所考虑每步棋的实力强弱如何都以数值来权衡，但是由于它是选择性搜索，因此有时甚至都不考虑某种正确棋步，更不用说去走它了。伯利纳说道：“在某些具体情况下，它很有下棋的才华。但是这还不够。在所有不同类型的棋局中，你都必须是始终如一的正确。J．Biit程序还不具备强大的实力，足以成功地应付整盘比赛。”

在第一届美国计算机国际象棋锦标赛上，J，Biit程序败于国际象棋3．0程序，后者是美国西北大学研究生戴维·斯莱特和劳伦斯·阿特金设计的。3．0程序的后来版本执行的不是选择搜索法，而是全方位搜索法：对所有可能的续步进行彻底的分析，一直到规定的某种深度。虽然全方位搜索法总是包含它看到的候选棋步中的正确棋步（因为它看到了所有棋步！），但在选择一步棋时效率却很低。很多时间都浪费在令人吃惊地探索无价值的棋步上，即使是最笨的人类推木式棋手对此也不会给予片刻的考虑。要是计算机能够看清博弈的最后结局，比方说像它能够在三连棋中所做的那样，那么，这些无用的努力将是毫无意义的。

国际象棋的数学可以证明全方位搜索的低效性。在人类国际象棋大师之间的对弈，典型的是对弈了84着棋（1着棋即指定的一方走一步棋）。由于每个棋位平均有38步法定棋步，因此穷举搜索法必须考虑3884个可能的棋位。那是一个庞大的数字：3884大于10132，即1的后面有132个0。宇宙已经存在了大约1018秒，因此，即使让计算机能够工作像宇宙年龄那么长的时间，每秒钟也要分析10114个国标象棋棋位，才能看清博弈的结局。