按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
娜赵蠹捌淞轿煌轮っ髁耍绻窍拗朴糜谄媾己牡缏飞疃龋敲吹缏房矶鹊睦┱箍煊谌魏味嘞钍健�1985年，美国斯坦福大学的安德鲁。姚在这方面取得了更惊人的研究成果，他证明了电路的宽度不仅以超多项式的方式扩展，而且还以指数的方式扩展，这表明这种问题虽然受到人为的限制，但也有内在的困难。
姚的成果很快地传遍了数学界。赛普泽这样说道：“每个人都认为这个结果很满意，但也是非常复杂的。”姚的方法为他人铺平了道路，好几个研究人员很快地对他的结果做了改进。美国电话电报公司贝尔实验室数学科学部主任罗纳德。格雷厄姆说：“这很像开车的头4分钟路程，一旦有人学会它，那么人人都可以学会它。”
1985年8月，美国麻省理工学院计算机学科研究生约翰。哈斯特德采用了姚的基本理论，但是简化了他的论据。哈斯特德说道：“在工作过程中，我获得了比较有力的结果。（在这种有限制的问题中）我们所知道如何设计的最小电路并不比我在理论上曾经证明它们应有的规模大出很多。”后来的证明都表明：数学家们实际上知道如何设计出并不比他们在理论上所推断的最佳电路差很多的电路。对于这些有限制的问题来说，不是数学上的无知，而是问题的本身排除了快速的解法。
苏联莫斯科大学的两位数学家阿。拉兹波洛夫和阿。安德烈耶夫在不限制电路深度但却限制所进行的运算方面取得了很大的成功。拉兹波洛夫又证明了如果不允许用“非”门的话，则用于人群问题的电路规模的增长将快于任何多项式的增长。而且，数学家们还在这里对这一结果做了改进，它表明电路必须是按指数方式增大。安德烈耶夫通过禁止用“非”门还能够证明另一类问题也需要大规模电路。
这些成就使这一领域乐观起来，虽然还没有人知道怎样才能减少对电路的限制并证明在无限制的情况下，旅行推销员的问题的确很难。“还有很长的路程要走，”赛普泽这样说道，“6年以前，我曾与人打过赌，我希望他还记住，将在2000年得出证明。我仍然信心十足，还有12年多的时间。”格雷厄姆还抱有更大的希望：“在以后3年内得到证明也不会让我吃惊。”
尽管人们普遍乐观，但在综合性理论方面（数学的一个分支学科，它表述了问题的难度）的研究人员，以他们的直觉已经知道他们会失败的。1985年冬天，美国麻省理工学院的数学研究生戴维。巴林顿曾证明，计算机能够运算的某些原始表示法会比该领域中任何人所能设想的更有功效。这种原始表示法不包含“与”门、“或”门和“非”门，但却包含一个分支门，它也有两根输出引线。当分支门受到触发时，如果输入信号具有一定的指定值，则分支门就会沿两根引线之一送出一个信号；对于所有其他输入信号，分支门沿另一根引线送出一个信号。换句话说，分支门能够处理计算机程序中的语句，诸如“如果x=5，转向步骤4；对于所有其他x，转向步骤7”。
巴林顿又证明了，全部由门层次不超过5层的分支门构成的电路，可以解所谓的多数问题：在一串的0和1中，1是不是多数？综合性理论学家普遍地（并且错误地）认为分支门限制于任何固定高度，不可能求解多数问题，更不用说严苛的五层限制了。
巴林顿说道：“我的证明很简单，但它令人惊奇，因为他们总是认为我所试图证明的都是假的。”巴林顿的结果也许没有多少实际用途——他又说：“除了它可以让我在一所好大学获得一个教师职位之外。”而且它还可以说服数学家们不要在复杂的综合性理论领域中如此自信。
________① 如果你一定要知道的话，NP表示非决定性的多项式，而plete一词则意味着这些问题是该类问题中最难的。
第十章 计算机——未来的象棋之王到此为止，我们所注意的大部分是计算机科学中的理论问题，计算机和人在原则上能进行哪些类型的计算。我们已经讨论的限制都是无条件的。如果综合性理论学家能够证明他们的推测是真实的，那么旅行推销员问题就不可能找到有效的解法。这既不是因为数学家的问题，也不是计算机缺少适当的运算工具；而是根本没有这种工具，将来也决不会有。
大多数的数学家和计算机科学家都不会遇到理论上难以超越的限制。他们所面临的障碍都是自我设置的，而且都是可以超越的，至少在原理上是可以超越的。一个主要的障碍——在数学之外的许多工作中也很突出——就是这样一种倾向：稳妥的做法是照搬被普遍接受的他人的解题方法，即使这些方法不是那么圆满。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂来，否则就会招来他人的嘲笑。本章内，让我们看看汉斯。伯利纳的开拓性工作，他制造了一台能够下好国际象棋的计算机。下一章，我们则将探讨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棋步具有最大的数值，这个棋步不仅可以进兵到第四横线，而且还可以提高后、王前象和王前马的机动性。早在第三步棋时，纸上下棋机走了一步软着的兵出击，但格伦尼并没有乘机利用它。在第二十九步棋时，由于纸上下棋机的求值函数示出格伦尼没有立即有效的捉子应步，因此它贪婪地用后吃掉一兵。
纸上下棋机的程序忽视一个简单然而可以压车的棋步，该棋步可以用下棋机的后看住对方的王，使得后可以强行