斗神狂飙 2008-6-28 09:50
电脑国际象棋简史
[font=楷体_GB2312][size=5][b]第一台会下棋的机器[/b][/size][/font] 在[font=Times New Roman]1769[/font]年，匈牙利工程师巴朗·沃尔夫冈·凡·坎比林[font=Times New Roman](Baron Wolfgang von Kempelen)[/font]为奥地利皇后做了一台会下国际象棋的机器来消遣。这是一个外形呆板的机械装置，不过它的出色棋力来自有一名象棋高手巧妙地藏在机器里的。所以这台会下棋的“机器”是个冒牌货。[font=Times New Roman]([/font]如图[font=Times New Roman])[/font] [align=center][/align]
[align=center][/align][img=217,215]http://www.elephantbase.net/computer/history1.jpg[/img]
[font=楷体_GB2312][size=5][/size][/font]
[font=楷体_GB2312][size=5][b]图灵的“纸上机器”[/b][/size][/font]
[table][tr][td][img=125,170]http://www.elephantbase.net/computer/history2.jpg[/img][/td][td] 第一个棋弈程序写于电脑被真正发明之前，这是一个非常有趣的事实。它是由一名想象力丰富的人所编写的，他知道可编程电脑即将出现，一旦发明出来，就有下棋的能力。这位先生就是阿伦·图灵[font=Times New Roman](Alan Turing)[/font]，有史以来最伟大的数学家之一。图灵的伟大成就是领导专家小组破译了纳粹德国的“谜”密码，因此对第二次世界大战的决定性结束作出了贡献。他对国际象棋非常感兴趣，不过他尽管智力超群并且下了很大工夫在学棋上，他还是一个蹩脚的棋手。战争结束不久，他就写下了能够让机器下棋的指令。由于当时还没有一台机器能够执行这些指令，于是他就自己执行，充当一个“人类[font=Times New Roman]CPU[/font]”，每走一步需要半个多小时[color=#000080]【译注：所谓“自己执行”，即图灵根据他所写的算法去运算，严格根据运算得出的结果去走棋】[/color]。这里有一局棋，图灵的“纸上机器”输给了同事： [/td][/tr][/table][align=center]图灵的“纸上机器”——[font=Times New Roman]Alick Glennie[/font] [/align][align=center]曼彻斯特 [font=Times New Roman]1952[/font] [/align][align=center] [/align][font=Times New Roman]1.e4 e5 2.Nc3 Nf6 3.d4 Bb4 4.Nf3 d6 5.Bd2 Nc6 6.d5 Nd4 7.h4 Bg4 8.a4 Nxf3+ 9.gxf3 Bh5 10.Bb5+ c6 11.dxc6 0-0 12.cxb7 Rb8 13.Ba6 Qa5 14.Qe2 Nd7 15.Rg1 Nc5 16.Rg5 Bg6 17.Bb5 Nxb7 18.0-0-0 Nc5 19.Bc6 Rfc8 20.Bd5 Bxc3 21.Bxc3 Qxa4 22.Kd2? [22.h5 [/font]本可得象[font=Times New Roman]] 22...Ne6 23.Rg4 Nd4? [23...Rxb2! 24.Bxb2 Rxc2+][/font] [font=Times New Roman]24.Qd3 Nb5[/font] [font=Times New Roman]25.Bb3 Qa6 26.Bc4 Bh5 27.Rg3 Qa4 28.Bxb5 Qxb5 29.Qxd6 Rd8 0-1.[/font] [font=楷体_GB2312][size=5][b]申朗的策略[/b][/size][/font] 贝尔实验室的克劳迪·申朗[font=Times New Roman](Claude Shannon)[/font]是和图灵同时代的另一位伟大的数学家，他一直在探索教电脑下棋。他认识到问题在于棋步数量大得可怕，因此把搜索所有棋步的“[font=Times New Roman]A[/font]策略”和剔除某些变化路线的“[font=Times New Roman]B[/font]策略”区分开来。如今我们也区分“强行搜索”和“选择搜索”程序，尽管所有强大的程序或多或少属于前者。 [font=楷体_GB2312][size=5][b]国际象棋代替核弹[/b][/size][/font] 战争期间美国在新墨西哥州的阿拉莫斯建立了一个巨大的实验室，它的主要目的就是发展核武器。要正确执行触发链式反应的内部爆炸需要数量巨大的计算。 [table][tr][td][img=218,192]http://www.elephantbase.net/computer/history3.jpg[/img][/td][td] [font=Times New Roman]1946[/font]年美籍匈牙利数学家约翰·凡·诺依曼[font=Times New Roman](John von Neumann)[/font]被指派设计一台强大的计算机器以加快工作进度的任务。到了[font=Times New Roman]1950[/font]年，一台叫“[font=Times New Roman]MANIAC[/font]一号”的巨型机被交付使用[font=Times New Roman]([/font]图左[font=Times New Roman])[/font]，它内装有数千个电子管和开关，每秒能执行[font=Times New Roman]10,000[/font]条指令。它也可以编程。科学家并不马上用它来设计核弹，而是先试验一下这台机器，而首先做的事情之一就是编写一个下棋的程序。这是一个缩小的[font=Times New Roman]6x6[/font]棋盘，没有象。虽然这么简化了但程序要搜索四层的深度就需要[font=Times New Roman]12[/font]分钟[color=#000080]【译注：四层相当于当前局面双方各两步】[/color]，如果加上象，就需要[font=Times New Roman]3[/font]个小时。 [/td][/tr][/table] [font=Times New Roman]50[/font]年代中期，这台机器下了三局棋。第一局是自己对自己，白胜。第二局是对一位让王后的强棋手，这局棋进行了[font=Times New Roman]10[/font]个小时，结果人类大师胜。第三局机器的对手是一位刚学棋一个星期的的年轻姑娘，结果程序[font=Times New Roman]23[/font]回合得胜。这是在智力博弈中人类首次负于电脑。 [font=楷体_GB2312][size=5][b]国际象棋和数学[/b][/size][/font] 程序下棋遇到的主要难题是所包含的棋步数量实在太多太多了。平均每个局面大约有[font=Times New Roman]40[/font]步符合规则的着法。如果你对每步着法都考虑应着就会遇到[font=Times New Roman]40 x 40 = 1600[/font]个局面。这意味着两层[font=Times New Roman](ply[/font]，一层为半步棋[font=Times New Roman])[/font]之后，单一步棋就会出现[font=Times New Roman]1600[/font]个不同的局面，而两步之后是[font=Times New Roman]250[/font]万个，三步之后是[font=Times New Roman]41[/font]亿个。平均一局棋大约走[font=Times New Roman]40[/font]步，于是所有可能局面就有[font=Times New Roman]10[/font]的[font=Times New Roman]128[/font]次方个，这个数字远远多于已知宇宙世界的原子总数目[font=Times New Roman]([/font]大约[font=Times New Roman]10[/font]的[font=Times New Roman]80[/font]次方[font=Times New Roman])[/font]！ 很显然没有一台电脑或其它机器可以搜索全部可能的着法来下棋，但人类也不行呀？唯一的问题是机器要达到人类的策略水平，需要搜索多深的深度。早期的电脑可以每秒产生和评价大约[font=Times New Roman]500[/font]个局面，或者在比赛中三分钟内对每步计算[font=Times New Roman]90,000[/font]个可能。意思就是它们仅能搜索三层的深度[font=Times New Roman]([/font]即一步半[font=Times New Roman])[/font]，这是很低的水平了，相当于新手。要搜索多一层需要每秒计算大约[font=Times New Roman]15,000[/font]个局面，也就是要快[font=Times New Roman]30[/font]倍。但即使能搜索四层也很浅薄，因此似乎电脑不可能达到大师级水平？ [font=Arial][size=5][b]Alpha-beta[/b][/size][/font][font=楷体_GB2312][size=5][b]算法[/b][/size][/font] 第一个突破出现在[font=Times New Roman]1958[/font]年，匹兹堡大学的三位科学家奈维尔、肖恩和西蒙[font=Times New Roman](Newell, Shaw and Simon)[/font]有重大发现：可以从搜索树中剔除相当大的部分而不影响最后结果，他们把这叫[font=Times New Roman]Alpha-beta[/font]算法。很重要指出的是，这是一个纯数学领域的技巧，独立于任何国际象棋知识而生效。 [align=center][/align]
[align=center][/align][img=318,228]http://www.elephantbase.net/computer/history4.gif[/img]
[align=center][/align][font=Times New Roman]Alpha-Beta[/font]算法示意图[font=Times New Roman]1[/font]
我们很粗略地描述一下[font=Times New Roman]Alpha-beta[/font]算法：比方说电脑已经完成评价一步棋，开始计算第二步棋。一旦单个变化显示返回的值低于第一步棋的值，就可以立即中止这个搜索。我们不需要精确知道第二步棋究竟有多差，程序会明确选择第一步棋。 [align=center][/align][img=397,228]http://www.elephantbase.net/computer/history5.gif[/img]
[align=center][/align][font=Times New Roman]Alpha-Beta[/font]算法示意图[font=Times New Roman]2[/font]
[align=center][/align]
除非另有需要，当只搜索数目的平方根那么多局面时，[font=Times New Roman]Alpha-beta[/font]算法产生的结果和完全搜索是一样的。早期的电脑突然间也能向前看五至六层了，到了[font=Times New Roman]70[/font]年代最快的电脑可以搜索七层，棋力令人瞩目了。但即使使用[font=Times New Roman]Alpha-beta[/font]算法，要搜索深一层还是需要提高[font=Times New Roman]5[/font]倍速度。数目的指数爆发性增长再次赶上程序设计者。 [font=楷体_GB2312][size=5][b]硬件尤物[/b][/size][/font] 电脑科学家肯·汤普森[font=Times New Roman](Ken Thompson[/font]，下图左[font=Times New Roman])[/font]觉得不能等待快[font=Times New Roman]5-25[/font]倍的百万美元级超级电脑来用于提高下棋能力。他和贝尔实验室的同事一起决定建造一台专门用途的机器，使用了价值大约[font=Times New Roman]20,000[/font]美元的几百个芯片。他们把这台机器叫做“尤物”[font=Times New Roman](belle[/font]，下图右[font=Times New Roman])[/font]，它只会下国际象棋。它能够每秒搜索大约[font=Times New Roman]18[/font]万个局面[font=Times New Roman]([/font]而当时的超级电脑只能搜索[font=Times New Roman]5000[/font]个[font=Times New Roman])[/font]。“尤物”在比赛中可以搜索八至九层那么深，因此可以和大师同场竞技。从[font=Times New Roman]1980[/font]年到[font=Times New Roman]1983[/font]年它赢得了世界电脑国际象棋和所有其它电脑竞赛冠军，直到被价钱贵上千倍的克雷[font=Times New Roman]X-MPs[/font]巨型机[font=Times New Roman](Cray X-MPs)[/font]取代为止。 [align=center][table=504][tr][td=1,1,41%][img=183,170]http://www.elephantbase.net/computer/history6.jpg[/img][/td][td=1,1,59%][img=269,170]http://www.elephantbase.net/computer/history7.jpg[/img][/td][/tr][/table][/align][font=楷体_GB2312][size=5][b]下棋的芯片 [/b][/size][/font] [font=Times New Roman]80[/font]年代中期，电脑科学家、卡梅隆大学的汉斯·贝利纳[font=Times New Roman](Hans Berliner[/font]，下图左[font=Times New Roman])[/font]教授接手肯·汤普森放下的工作。贝利纳曾经是世界国际象棋通讯赛冠军，他制造了一台硬件型的机器叫“高技术”[font=Times New Roman](HiTech)[/font]，他和他的研究生一起研究可拔插芯片。装有[font=Times New Roman]64[/font]个并行芯片的“高技术”差点赢得了[font=Times New Roman]1986[/font]年的世界电脑国际象棋冠军[font=Times New Roman]([/font]冠军是克雷[font=Times New Roman])[/font]。随后贝利纳的几个学生包括华人许锋雄等自行研究叫“芯测”的机器，后来则是“深思”[font=Times New Roman](Deep Thought)[/font]。它只花[font=Times New Roman]5000[/font]美元但每秒搜索[font=Times New Roman]50[/font]万个局面。许锋雄[font=Times New Roman]([/font]下图右[font=Times New Roman])[/font]等后来加入了[font=Times New Roman]IBM[/font]，和其他人合作制造了[font=Times New Roman]IBM[/font]现在的“深蓝”[font=Times New Roman](Deep Blue)[/font]。 [align=center][table=457][tr][td=1,1,54%][img=223,170]http://www.elephantbase.net/computer/history8.jpg[/img][/td][td=1,1,46%][img=182,170]http://www.elephantbase.net/computer/history9.jpg[/img][/td][/tr][/table][/align][font=楷体_GB2312][size=5][b]深蓝[/b][/size][/font] 加里·卡斯帕罗夫在费城和纽约面对的这台电脑包括一个装备大量专门用以进行高速运算芯片的[font=Times New Roman]IBMSP/2[/font]服务器，每个芯片每秒能处理[font=Times New Roman]2-3[/font]百万个局面。使用超过[font=Times New Roman]200[/font]个这种芯片，整个程序的速度达到了每秒处理[font=Times New Roman]2[/font]亿个局面。 棋弈机器每秒能处理[font=Times New Roman]2[/font]亿个局面意味着什么？肯·汤普森，“尤物”之父[font=Times New Roman]([/font]也是[font=Times New Roman]Unix[/font]和[font=Times New Roman]C[/font]语言之父[font=Times New Roman])[/font]，在[font=Times New Roman]80[/font]年代对搜索深度和棋力提高之间的关系做了非常有意义的试验。他让“尤物”自己跟自己下，但只有一方的搜索深度不断增加，平均每增加一个搜索深度可大约换算成[font=Times New Roman]200[/font]个国际象棋等级[font=Times New Roman]Elo[/font]分。于是，“尤物”搜索四层其水平大约是[font=Times New Roman]1230[/font]分，搜索到九层它的水平达到了[font=Times New Roman]2328[/font]分。延伸这条曲线，到了顶端会变平缓，可以计算出搜索深度达到十四层时，就达到了世界冠军的程度即[font=Times New Roman]2800[/font]分。[font=Times New Roman]([/font]如下图，横坐标是搜索层数，纵坐标是国际等级分。上部横线是卡斯帕罗夫的分数作参考，[font=Times New Roman]A[/font]线表示对电脑水平的乐观估计，[font=Times New Roman]B[/font]线表示悲观估计，[font=Times New Roman]C[/font]线表示现实估计[font=Times New Roman])[/font] [align=center][/align]
[align=center][/align][img=348,250]http://www.elephantbase.net/computer/history10.jpg[/img]
[align=center][/align]搜索深度和棋力关系曲线图
专家的结论是：要与人类世界冠军争夺冠军，必须做一台每秒运算[font=Times New Roman]10[/font]亿次的电脑[font=Times New Roman]([/font]搜索到十四层的深度[font=Times New Roman])[/font]。深蓝接近了，但还达不到。[color=#000080]【译注：注意这里搜索到十四层的深度，应该是指规定比赛分配时间内对所有回合而言。否则对一步棋不限制时间地搜索，或者对一些简单局面的搜索，要达到十四层对当今众多高速电脑来说实在不是难事。】[/color] 当然，程序的质量也扮演重要角色。今天的顶级个人电脑程序象[font=Times New Roman]Fritz[/font]和[font=Times New Roman]Junior[/font]可以达到并超过每秒处理[font=Times New Roman]50[/font]万个局面。它们事实上已经超过[font=Times New Roman]2600[/font]分的水平，可以对抗除世界前[font=Times New Roman]100[/font]名棋手之外的任何人。在快棋战里人类只有大约前十几位可以胜任，而在超快棋里大概只有两、三名人类棋手能过关。[color=#000080]【译注：也可见，每升高等级而要求的运算速度的提高绝不是仅仅直线式的，而是指数式的。所以每秒计算[/color][font=Times New Roman][color=#000080]50[/color][/font][color=#000080]万次就达到[/color][font=Times New Roman][color=#000080]2600[/color][/font][color=#000080]分的特级大师水平，但要达到[/color][font=Times New Roman][color=#000080]2800[/color][/font][color=#000080]分，根据上面估算则需要每秒计算[/color][font=Times New Roman][color=#000080]10[/color][/font][color=#000080]亿次之多。】[/color] [font=楷体_GB2312][size=5][b]挑战所有开局 [/b][/size][/font] 电脑棋力的一个重要方面是下棋时使用广阔的开局库。多少代人类大师的知识积累和经验可以轻易地储存在硬盘上并且在开局阶段采用。即使是个人电脑程序也懂得几千万个开局局面，并且对这些局面的每一个都有完全的统计[font=Times New Roman]([/font]比如出现过那些着法、用哪些着法胜过、使用过的人有多少，等等[font=Times New Roman])[/font]。程序经常是连走[font=Times New Roman]15[/font]到[font=Times New Roman]20[/font]步之后才第一次需要计算。如果没有从这些人类的开局知识精华中受益，程序将实力大减。 当电脑从数目庞大的、从国际象棋历史积累下来的开局知识中取得坚实优势之时，它们也从对局的另一端搜索中受益。 [font=楷体_GB2312][size=5][b]残局数据库[/b][/size][/font] 这又是那位影响力到处有的肯·汤普森充当了研究先锋。他在[font=Times New Roman]80[/font]年代就开始生成和储存棋盘上剩四至五子的所有符合规则的残局。一个典型的五子残局，比如王双象对王单马，包含总数[font=Times New Roman]121[/font]万个局面。加上一只移动不连续的兵，这个数字增加到[font=Times New Roman]335[/font]万。汤普森编写程序产生所有符合规则的局面并计算出每个残局可能的强制变化。他还以一种方式把结果压缩，使得一张标准的[font=Times New Roman]CD-ROM[/font]能存放大约[font=Times New Roman]20[/font]个残局。[color=#000080]【译注：原文没有提另一位对残局数据库的发展作出重大贡献的[/color][font=Times New Roman][color=#000080]Nalimov[/color][/font][color=#000080]。】[/color] 电脑使用这些残局数据库，可以把每个残局走得绝对完美，就象上帝一样。对于棋盘出现子力及数目符合的任何局面，电脑可以立刻知道该胜、该和还是该负，并且知道要多少步。它经常宣布[font=Times New Roman]15[/font]步棋之后取胜或将死，而执输棋那一种颜色的则能够最优化地防守[color=#000080]【即在必然被将死前每一步防守都尽力最优化】[/color]。深蓝使用了汤普森的残局数据库，而象[font=Times New Roman]Fritz[/font]这样的个人电脑程序也把它们贯彻在搜索树中。这些对棋力有什么影响还有待观察。有些五子的残局极之困难甚至对于人类来说难以掌握，但这些五子残局对于汤普森正在努力的六子残局来说只是小巫见大巫，在某些六子局面里，要取胜不得不进行超过[font=Times New Roman]200[/font]步的计算[color=#000080]【译注：当然这是在纯电脑国际象棋领域来说，实际上人类走残局，经验和知识比重很大，有很多棋根本不用考虑就知道该怎么样走。但电脑却是“一丝不苟”地全部去算。所以，从数字上比意义还不大】[/color]。自然硬件技术的发展是有利于电脑的，汤普森的六子残局，每个包含[font=Times New Roman]80[/font]到[font=Times New Roman]200[/font]亿个局面，刚好能够压缩进一张[font=Times New Roman]DVD[/font]。[color=#000080]【译注：高端应用情况不得知，而普遍应用于个人电脑程序的[/color][font=Times New Roman][color=#000080]Nalimov[/color][/font][color=#000080]残局数据库，全部四子残局大约占[/color][font=Times New Roman][color=#000080]30MB[/color][/font][color=#000080]储存，全部五子残局需要[/color][font=Times New Roman][color=#000080]7GB[/color][/font][color=#000080]，至于六子残局，目前可见的只是一些比较简单局面而且一只兵也没有的，因为兵会升变，复杂性巨增，如果加上则相当时期内一般电脑的硬盘难以承受，别忘了增长不是直线而是指数式的。】[/color] 好在，局面数量更大得不可思议的七子残局，离产生依然很遥远。更好在的是，对局的两端即开局和残局，永不可能接在一起。是啊，假如看到一台电脑走了 [font=Times New Roman]1.e4 [/font]然后宣布[font=Times New Roman]40[/font]步棋之内将死，这就太难以让人接受了。但是电脑在比赛中稳定战胜人类世界冠军大概只是时间问题，若干年或若干十年之后…… [color=#000080]【译注：[/color][font=Times New Roman][color=#000080]1997[/color][/font][color=#000080]年深蓝在“回敬赛”中战胜棋王卡斯帕罗夫，但那次的场外不明朗因素太多，结果未必有说服力，何况注意到两次比赛总成绩其实还是卡帕罗夫以[/color][font=Times New Roman][color=#000080]6.5-5.5[/color][/font][color=#000080]战胜深蓝。[/color][font=Times New Roman][color=#000080]2002[/color][/font][color=#000080]年[/color][font=Times New Roman][color=#000080]10[/color][/font][color=#000080]月的克拉姆尼克对[/color][font=Times New Roman][color=#000080]Deep Fritz[/color][/font][color=#000080]人机大战，不明朗因素又有点倾向于克拉姆尼克，以至舆论认为电脑机会不大，且到时看。卡斯帕罗夫本人当初认为电脑真正稳定战胜人类世界冠军要到[/color][font=Times New Roman][color=#000080]2010[/color][/font][color=#000080]年，汤普森则认为可能要到[/color][font=Times New Roman][color=#000080]2018[/color][/font][color=#000080]年。有趣的是包括贝利纳、许锋雄等人在上世纪[/color][font=Times New Roman][color=#000080]90[/color][/font][color=#000080]年代初认为电脑在[/color][font=Times New Roman][color=#000080]1994[/color][/font][color=#000080]年就可以达到这点的。】[/color] [align=center][/align][img=320,260]http://www.elephantbase.net/computer/history11.jpg[/img]
[align=center][/align]汤普森和卡斯帕罗夫