主题：阿基米德的报复 by 保罗?霍夫曼　 -- foundera

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

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

　　大多数的数学家和计算机科学家都不会遇到理论上难以超越的限制。他们所面临的障碍都是自我设置的，而且都是可以超越的，至少在原理上是可以超越的。一个主要的障碍――在数学之外的许多工作中也很突出――就是这样一种倾向：稳妥的做法是照搬被普遍接受的他人的解题方法，即使这些方法不是那么圆满。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂来，否则就会招来他人的嘲笑。本章内，让我们看看汉斯?伯利纳的开拓性工作，他制造了一台能够下好国际象棋的计算机。下一章，我们则将探讨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个国标象棋棋位，才能看清博弈的结局。

　　在国际象棋比赛中，计算机也和人一样，不允许进行无限期的思考；40步棋大约只能给定120分钟，每步棋平均3分钟。即使计算机减小了胃口，仅探索出后续几步棋所有可能的棋步，数学上也是不允许的。在只走两着棋之后，即每方各走一步棋之后，可能的棋势数就会超过1，000。而走了4着棋之后，就可能有超过100万可能的棋势。

　　计算机不仅生成所有这些棋势，而且还要求出它们的值。计算机是通过数值加权的方法来相当粗略地达到上述目的，诸如考虑实力（即各方的子与兵的数量与特点）、机动性、中心方格与纵列的控制、兵的结构、王的安全性、等等。比方说，在3分钟结束时，无论走什么棋步都要使对手的潜在的最大增益降至最低的程度；这种策略，是从有关竞赛的数学理论借鉴而来的，它设想对方可看出你所看出的一切，力求确保自身的利益。

　　如果不是发现了a－β算法，全方位搜索法即使只局限于几着棋的深度，也是不实用的。a－β算法是一种巧妙的求值方法，可以让计算机无需求出每种可能棋势的值就能选择它所要走的棋步。然而令人惊奇的是，所选择的棋步正是计算机考虑了每一种续步后所要走的同一步棋。这怎么可能呢？

　　假设计算机首先在一定范围内探索称之为A的某一特定棋步的所有后续棋步。设想两方都走最佳的弈法，计算机给A定的极小极大值比方说为1。（在这种方案中，正值相当于计算机所具有的优势，而负值相当于计算机所处的劣势。优势值为1，表示比对手多一兵，其他条件都相同。）现在，计算机开始对另一个叫做B的可选棋步求值，B是特别愚蠢的一步棋，表示将后置于可以立即被对手的弱兵捉住的方格中。如果计算机现在分析对手的正常应着棋步――以兵捉后，并排除掉一种微小的可能性，即为了一次锐不可挡的进攻而英勇牺牲了后，那么，计算机将定这个棋势的数值为-9，它表示其对手已具有强大的优势。

　　现代的计算机国际象棋靠的是极小极大值法：所走的棋步应使对手的可能最大增益降至最小程度。假设计算机可选择的棋步为A和B。它看出了对手对A的最佳反应是走一步棋a（图中的数目表示按照计算机的观点所产生的棋势的优劣程度如何）。这时计算机又考虑棋步B，并看出了对手将应以d，从而能保证时B取得比对A更好的结果。这时计算机有足够理由选择A，而对手反应e或f的结果是什么都无关紧要。

　　计算机不需要考虑所有其他应着棋步的结果，其中也包括对手不能吃后，因为计算机已能识别对手的走棋路线是确保它自己对B步棋的应步能优于对A步棋的应步。因此，计算机根据自己的观点，知道走A步棋比走B步棋更为可取。

　　要有效地执行a－β算法，计算机必须按顺序考虑各种棋步：在上述例子中，它必须先检验A，再检验B，并且在分析B时，必须先检验捉后的棋步，再考虑其他的应步。审查各种棋步的顺序取决于各种不同的探试法或一般经验。

　　例如，捉子探试法指令程序对那些涉及捉子的各种棋步给予最优先考虑。（这样捉子成为一着好棋的机会将更多一些，特别是如果被捉的子未受到保护时。这种方法还能帮助计算机减轻负担，对机器大有稗益。而棋盘上少了一个子，计算机考虑的应着棋步也就相应减少。）

　　杀子探试法始终监视着对手的哪一步棋被杀或被驳倒（一种特殊的棋步）。当计算机仔细考虑了另一步棋时，首先要研究杀方的反应。现举一特殊例子。计算机发现它所考虑的捉对方车的一步已被对手弈出将军棋步所驳倒，在仔细考虑替代的棋步时，它将首先决定是否要走避免被将军的棋步。换句话说，杀子探试法可用来识别并监视这种威胁，这里所指的是能立即将军的致命威胁。另一次探试优先考虑那些能将军的棋步，从而应了一句古老的格言：“常将，就能将死。”简单地说，这时计算机的做法就有些更像人了。

　　在全方位搜索法中，要是采用渐进地深入考虑所有的续步，而不是每次一步地充分考虑这些续步，那么就能做到省时省事。从棋盘上的某种棋势着手，首先分析所有可能的续步，然后分析某一特定的棋步，根据目前所进行的搜索，就能看到最佳的一步棋。再从这步棋开始，对其余的所有续步进行有效的分析，一直到两着棋的深度，并且再次找到其中最佳的一步棋。这种过程叫做迭代深化法，它不断重复下去，直到达到所期望的深度时为止。

　　有一种表记录了计算机已经求出值的棋势、对这些棋势所给定的数值、以及迄今已搜索到的最佳一步棋，通过这个表就可以提高全方位搜索法的有效性。在全方位搜索法中，各种棋势都往往会不止一次地出现，只要程序设计好，查找所求的数值的时间自然比重新计算的时间少，因此，这种表在节省时间方面是很有用的。

　　在70年代，美国西北大学的斯莱特和阿特金已能够利用变最大为最小求值法、a－β算法、捉子探试法与杀子探试法、迭代深化法和已经检验过的棋势表等各种方法成功地用国际象棋3．0程序的后来版本进行工作，而且，它也像图灵的纸上下棋机一样，深入地搜索了下国际象棋的战术棋路，直到走到走不动的棋势为止。这就是国际象棋4．7程序，它下国际象棋的能力略低于国际象棋大师的水平。

　　1981年，全方位搜索程序Belle由美国电话电报公司贝尔实验室的肯?汤姆森和乔?康登共同开发出来，它已成为第一部达到国际象棋大师级水平的计算机，进入全美国际象棋比赛最高棋手1％的行列。Belle程序的成功应归功于专为进行国际象棋运算而定制的硬件。华盛顿的官员显然很重视Belle程序。1981年，当汤姆森和康登试图携带Belle程序去苏联莫斯科参加国际象棋表演比赛时，联邦局人员拘捕了他们。里根当局担心该程序会泄露军事秘密。而汤姆森却坚持认为，Belle程序所知道的事情只是如何去下国际象棋。汤姆森告诉新闻界说：“在军事上可以使用Belle程序的惟一方式就是可以把它从飞机中扔出，也许你可以以此杀死某一个人。”这些日子，华盛顿已不大注意了，因为Belle程序的等级已滑落在国际象棋大师的水平之下，然而它仍然可以探索平均8着棋的深度，每秒钟分析120，000种棋势，弈出比较难对付的国际象棋。

　　当斯莱特、阿特金、汤姆森、康登及其他人应用全方位搜索法进行工作时，伯利纳却集中精力于求值函数上。伯利纳回忆说：“当时我正考虑德格鲁特关于国际象棋大师怎样弈棋的著名的研究――他们如何观察弈至一半的棋局变化，然后如何转向考虑别的方面，再如何回到考虑最初的棋局变化。看来那是正确的。至少那是我所考虑的如何下棋的方法。”另一方面，现有的计算机下国际象棋的程序，不会在变化中来回移动。它们随着特定的变化到达一定的深度，给最后的棋势求出数值，再转到另一种变化。

　　伯利纳接着说：“给定某一具体值的困难在于你不能出错。你可以弈出牺牲两子兵，以换取具有极强攻击力的棋势。如果你使用类似α-β的算法，你就能够弈出最后一种棋势，对此你必须赋值；要么为换取攻势值得抛弃两兵子，要么就不值得。无论你持哪种看法，都会在一定时间内出现错误。更确切地说，‘我还不能肯定。我已经丢掉两兵但拥有强攻势。也许实际上我可以将死王或者赢回的多于两兵，而我也许只是丢了两兵’，所以你先摆出问题，再进一步深入研究，看你能否解决它。”

　　“对于这类问题以及如何把计算机程序编写得更深入，我思考得很多。一个晚上，我忽然有一灵感：对于一种棋势，可以给定一个值，为什么不能以一系列的值取而代之？”

　　一系列值中最高值意味着棋势处于最佳状态，而最低值则相当于可能出现最坏的情况，计算机程序要对一系列值而不是对单一值进行比较，而且当这些值的范围太宽时，它还可以比较深入地考虑棋势，以便把最高值和最低值都包括进去。伯利纳说道：“这种想法是遗漏的组成要素。它是许多不可思议的事物之一，这类事在科学上隔一段时间就发生一次。你提出某一方案，那么突然间，一切都迎刃而解了。”使用系列值的想法已经成为众所周知的B*算法（发音为“B-星”），而且伯利纳还把它列为他的诀窍。

　　1975年，当伯利纳完成计算机国际象棋博士论义时，他决定为计算机编写下15子棋的程序，这种棋是他最近向新岳父学习的。他发现15子棋对研究求值法是一个很吸引人的领域，因为在这种棋中进行搜索，不会让你探索得太深。在典型的15子棋棋势中，约有400多种可能性（21组掷骰点数和每组点数的约20种走棋法），与之相比，在典型的国际象棋棋势中，则“仅有”38种可能性。

　　在15子棋的计算机程序BKG中，伯利纳没有沿用人工智能中按规则求值的一般做法，他注意到“在医疗诊断体系中，也许还有一种惯例，比如说，如果有一位患者，他有这样那样的疾病，而且其年龄已超过6周岁，那么可以给他以如此这般的治疗。可是忽然间来了一位患同样病的患者，但他的年龄仅为5周岁9个月，按照惯例，不能对他进行那种治疗。当然，那是错误的。因为你真正需要考虑的不是黑白分明的年龄截止点，而是由于某种原因需要考虑诸如年龄、体重以及一般健康情况等因素的平缓函数。在上述特定病例中，可以开出降低剂量的药方”。

　　“当你首次设计智能系统时，这几项考虑已不很重要了。它们远不及把基本信息输进计算机中那么重要。但是，如果你想与最佳的人竞争，那么你就不能按照一套完全不灵活的规则去工作。”

　　当然，伯利纳想以他的15子棋计算机程序与人类最佳棋手博奔，因此他没有认真地考虑较为惯用的方法，摈弃了把棋势分为几种类型而且每类都有不同求值函数的通则。相反，他却依赖数学上的单一复杂函数，这个函数包括大约50个不同的变量，与具有不同程度重要性的特定部分相一致，其重要性取决于博弈阶段。每个变量都由一个数值来替代，来衡量存在于已知棋势中相应特点的重要程度。这样一来每个数都是加权的：它们都乘以另一个数，这个数称为系数，用以表示对该点的特点所给予的注意力有多大（或多小）。随着博弈进程的变化，这些系数也平缓地变化着。

　　这种成功的方法叫做SNAC法（带有应用系数的非线性平缓函数法）。在SNAC法提出后，只有几个月的时间，BKG程序就击败了人类15子棋冠军选手，这显然表明SNAC法是成功的。虽然BKG程序有一些掷骰子般的幸运，而且也曾有过少量较小的错误，但它还是一个强劲的棋手。

　　伯利纳根据他在计算机15子棋上获得的成功，知道找到一种平缓变化的函数对国际象棋上的有效求值法也是很关键的。在这一点上，惯用的一种方法也与通则有关。考虑一下王的棋势。当博弈到中盘时，你想把王躲藏在角落里，那里很可能少受骚扰。求值函数可以对王的实际位置与角落之间的棋盘方格进行计数；这个数愈大时，你的处境也愈坏。然而，在弈至残局时，那时只剩下几个子，将死的危险性甚微，于是王应该处于棋盘的中央，它在那里还可以起着很强的战子作用。所以在残局时，求值函数可以对王的实际位置与中央之间的间隔数进行计数。如果你采用了如下通则：BKG程序在与人类的世界15子棋冠军卢吉?维拉对弈时赢得了胜利

　　BKG程序在与维拉比赛的第一局中，掷出一个 4点和一个2点。这时，BKG程序（黑方）具有优势，但不得不留下一个暴露棋子。它走了9-5步和9-7步，在7点处，留有一个暴露棋子，它可能受到13组掷骰点数的攻击。从表面上看，好像走5-1步和4-2步比较安全，在5点处留下一个暴露棋子，它只可能受到11组掷骰点数的攻击，但这却是糟糕的走法，因为它在9点处会留下两子，当它们必须走步时，就有可能成为后来的暴露棋子。

　　“当棋盘上还有一定数目的子和兵时，棋局就是中盘，而当其只有很少几个子时，则是残局”，那么，你几乎要患精神分裂症了。

　　伯利纳接着说道：“你当然不想这样，棋势是连续性的――中盘是逐步转为残局的。由于残局的逐渐接近，你不再那么执意要让王走到角落，而是容许王缓慢地移到棋盘的中部。每当人人都承认残局终于来到时，王应该靠近棋盘的中央，而不是藏在角落里。”达到这一目的的方法是需要有一种缓慢变化的求值函数，而在中盘与残局之间不应有任意的差别，而且两者也不应有不同的求值函数。

　　BKG程序在与维拉最后一局的比赛中，如图所示，掷出一个5点和一个1点。这时，BKG程序走出了引起轰动的13-8步和3-2步。如果BKG程序的暴露棋子中任何一子受到进攻，那么它将有更多的时间去组成棋步，以阻止对方的棋子前进。反之，如果它们未受攻击，那么就能够在本方棋盘中形成据点，使维拉的棋子更难于回到本方的棋盘中，然后再逃脱掉。

　　的信息而工作，太阳牌计算机是Hitech程序的国际象棋的知识源。

　　Hitech程序的成功秘诀在于它能更好地思考（由于Oracle程序）以及比呆板的对手快50％的求值速度（因为它可以同时对一步以上的棋步顺序求值）。Hitech程序执行全方位搜索法，平均每秒可以观察惊人的175，000种不同棋势，换句话说，每步棋3分钟内可以均摊到3，000万种棋势分析。伯利纳说道：“毫无疑问，人们要考虑3，000万种棋势需要花去他们一生的时间。”

　　Hitech程序的速度及其智力水平已使它成为世界上最高级的国际象棋程序，优于几乎全部的苏联人棋手。伯利纳认为， Hitech程序或其新一代程序在1990年的国际象棋对弈中击败人类棋王的可能性有50％。为了达到这一目的，它计划把更多的知识输进Oracle程序，并使Hitech程序试用选择搜索法，或许还得用B*算法。

　　Hitech程序下国际象棋能下得多好？就此而言，任何一种计算机在某项智能活动中究竟能有多好？伯利纳说道：“我认为，我们将会发现，在输入计算机的一些信息开始与另一些信息相抵触之前，你能输入计算机的信息量是有限度的。”某些研究工作者试图借助于一种信任系统，来消除这种可能性。计算机对相抵触的信息不大注意，因为它的来源不可靠。

　　伯利纳接着说道：“但是我不认为信任系统就是答案。我认为，我们需要制造一种学习机，把它摆在架子上，观看录像带，并从基础学起。开始，可能学得很慢。也许要花20年时间，才能达到成年人的理解水平，那也就很好了。如果所得到的成果是有价值的，那么学习机本身也是值得的。然而，我不会屏息不语。学习机最终必定会出现，不是在80年代，或许是在90年代。”

_______

①也可以译为国际双陆棋