阿基米德的报复-第15章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
伯利纳回忆说：“一些人往往刚上大学不久，就会遇到麻烦，我就是其中之一。本来，我曾是一名物理学的优等生，但是不知怎么一来，我走上了岔道。我一边打工，一边上学，终于攒够了钱来付学费，可以不再打工。这是一个关键性的错误，忽然间我有了很多时间，因此除了下国际象棋之外，我还打桥牌。很快地，我就成为华盛顿市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程序的惟一方式就是可以把它从飞机中扔出，也许你可以以此杀死某一�
