《国际象棋译文苑》文摘
 
计算机国际象棋简史
 
Frederic Friedel/
 
第一台会下棋的机械
 
  在1769年,匈牙利项目师巴朗·沃尔夫冈·凡·坎比林(Baron Wolfgang von Kempelen)为奥天时皇后做了一台会下国际象棋的机械来消遣。这是一个形状机器的机械装配,不外它的精彩棋力来自有一位象棋妙手神奇地藏在机械里的。以是这台会下棋的“机械”是个冒牌货。(如图)
 
 
图灵的“纸上机械”
  第一个棋弈顺序写于计算机被真正发现之前,这是一个异常有趣的现实。它是由一位想象力雄厚的人所编写的,他知道可编程计算机即将显现,一旦发现出来,就有下棋的才气。这位师长西席就是阿伦·图灵(Alan Turing),有史以来最伟大的数学家之一。图灵的伟大结果是指导专业人士小组破译了纳粹德国的“谜”密码,因而对第二次天下大战的注定性完毕作出了孝敬。他对国际象棋异常感兴味,不外他只管智力超群而且下了很大时间在学棋上,他照样一个糟糕的棋手。战争完毕不久,他就写下了能够让机械下棋的指令。由于事先还没有一台机械能够执行这些指令,因而他就自身执行,充任一个“人类CPU”,每走一步要求半个多小时【译注:所谓“自身执行”,即图灵依据他所写的算法去运算,严厉依据运算得出的效果去走棋】。这里有一局棋,图灵的“纸上机械”输给了同事:
图灵的“纸上机械”——Alick Glennie
曼彻斯特 1952
 
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 本可得象] 22...Ne6 23.Rg4 Nd4? [23...Rxb2! 24.Bxb2 Rxc2+] 24.Qd3 Nb5 25.Bb3 Qa6 26.Bc4 Bh5 27.Rg3 Qa4 28.Bxb5 Qxb5 29.Qxd6 Rd8 0-1.
 
申朗的战略
 
  贝尔执行室的克劳迪·申朗(Claude Shannon)是和图灵同时期的其余一位伟大的数学家,他一直在探讨教计算机下棋。他熟悉到问题在于棋步数目大得恐怖,因而把搜索一切棋步的“A战略”和剔除某些转变线路的“B战略”区离开来。现在咱们也区分“强行搜索”和“选择搜索”顺序,只管一切壮大的顺序或多或少属于前者。
 
国际象棋替代核弹
 
  战争时期美国在新墨西哥州的阿拉莫斯竖立了一个伟大的执行室,它的主要目的就是生长核武器。要准确执行触发链式回响反映的外部爆炸要求数目伟大的盘算。
  1946年美籍匈牙利数学家约翰·凡·诺依曼(John von Neumann)被指派设想一台壮大的盘算机械以加速事情进度的义务。到了1950年,一台叫“MANIAC一号”的巨型机被托付运用(图左),它内装有数千个电子管和开关,每秒能执行10,000条指令。它也能够编程。专业研究人员其实不立时用它来设想核弹,而是先调研一下这台机械,而首先做的事项之一就是编写一个下棋的顺序。这是一个增加的6x6棋盘,没有象。虽然这么简化了但顺序要搜索四层的深度就要求12分钟【译注:四层相即是以后局势双方各两步】,若是加上象,就要求3个小时。
  50年月中期,这台机械下了三局棋。第一局是自身对自身,白胜。第二局是对一位让王后的强棋手,这局棋停止了10个小时,效果人类巨匠胜。第三局机械的对手是一位刚学棋一个星期的的年轻女人,效果顺序23回合失利。这是在智力博弈中人类首次负于计算机。
 
国际象棋和数学
 
  顺序下棋遇到的主要难题是所包罗的棋步数目真实太多太多了。匀称每一个局势约莫有40步相符划定礼貌的着法。若是你对每步着法都斟酌应着就会遇到40 x 40 = 1600个局势。这意味着两层(ply,一层为半步棋)以后,单调步棋就会显现1600个分歧的局势,而两步以后是250万个,三步以后是41亿个。匀称一局棋约莫走40步,因而一切能够局势就有10128次方个,这个数字远远多于已知宇宙天下的原子总数目(约莫1080次方)
  很显著没有一台计算机或其余机械能够搜索悉数能够的着法来下棋,但人类也不可呀?唯一的问题是机械要到达人类的战略水平,要求搜索多深的深度。早期的计算机能够每秒发生和评定约莫500个局势,也许在竞赛中三分钟内对每步盘算90,000个能够。意义就是它们仅能搜索三层的深度(即一步半),这是很低的水平了,相即是新手。要搜索多一层要求每秒盘算约莫15,000个局势,也就是要快30倍。但纵然能搜索四层也很浅陋,因而似乎计算机不能够到达巨匠级水平?
 
Alpha-beta算法
 
  第一个突破显现在1958年,匹兹堡大学的三位专业研究人员奈维尔、肖恩和西蒙(Newell, Shaw and Simon)有严重发现:能够从搜索树中剔除相等大的局部而不滋扰最终结果,他们把这叫Alpha-beta算法。很主要指出的是,这是一个纯数学领域的窍门,自力于任何国际象棋知识而失效。
 
Alpha-Beta算法示希图1
 
  咱们很大略地形貌一下Alpha-beta算法:譬喻说计算机以前完成评定一步棋,最先盘算第二步棋。一旦单个转变显现前往的值缺乏第一步棋的值,就能够够马上中缀这个搜索。咱们不要求准确知道第二步棋终究有多差,顺序会晓畅选择第一步棋。
 
Alpha-Beta算法示希图2
 
  除非尚有要求,当只搜索数目的平方根那末多局势时,Alpha-beta算法发生的效果和完整搜索是一样的。早期的计算机倏忽间也能向前看五至六层了,到了70年月最快的计算机能够搜索七层,棋力使人注视了。但纵然运用Alpha-beta算法,要搜索深一层照样要求提升5倍速率。数目的指数发作性增长再次遇上顺序设想者。
 
硬件尤物
 
  计算机专业研究人员肯·汤普森(Ken Thompson,下图左)以为不能守候快5-25倍的百万美圆级超级计算机来用于提升下棋才气。他和贝尔执行室的同事一同注定做作一台专程用途的机械,运用了价值约莫20,000美圆的几百个芯片。他们把这台机械叫做“尤物”(belle,下图右),它只会下国际象棋。它能够每秒搜索约莫18万个局势(而事先的超级计算机只能搜索5000)。“尤物”在竞赛中能够搜索八至九层那末深,因而能够和巨匠同场竞技。从1980年到1983年它赢得了天下计算机国际象棋和一切其余计算机竞赛冠军,直到被价钱贵上千倍的克雷X-MPs巨型机(Cray X-MPs)庖代为止。
下棋的芯片
 
  80年月中期,计算机专业研究人员、卡梅隆大学的汉斯·贝利纳(Hans Berliner,下图左)专业人士接手肯·汤普森放下的事情。贝利纳以前是天下国际象棋通讯赛冠军,他制造了一台硬件型的机械叫“妙手艺”(HiTech),他和他的研讨生一同研讨可拔插芯片。装有64个并行芯片的“妙手艺”差点赢得了1986年的天下计算机国际象棋冠军(冠军是克雷)。随后贝利纳的几个师长西席包孕华人许锋雄等自己研讨叫“芯测”的机械,厥后则是“寻思”(Deep Thought)。它只花5000美圆但每秒搜索50万个局势。许锋雄(下图右)等厥后加入了IBM,和其他人协作制造了IBM现在的“深蓝”(Deep Blue)
深蓝
 
  加里·卡斯帕罗夫在费城和纽约面临的这台计算机包孕一个装备少量专程用以停止快速运算芯片的IBMSP/2效劳器,每一个芯片每秒能处置责罚2-3百万个局势。运用凌驾200个这类芯片,悉数顺序的速率到达了每秒处置责罚2亿个局势。
  棋弈机械每秒能处置责罚2亿个局势意味着甚么?肯·汤普森,“尤物”之父(也是UnixC言语之父),在80年月对搜索深度和棋力提升之间的相干做了异常有意义的调研。他让“尤物”自身跟自身下,但只需一方的搜索深度络续增长,匀称每增长一个搜索深度可约莫换算成200个国际象棋品级Elo分。因而,“尤物”搜索四层其水平约莫是1230分,搜索到九层它的水平到达了2328分。延长这条曲线,到了顶端会变陡峭,能够盘算出搜索深度到达十四层时,就到达了天下冠军的水平即2800分。(以下图,横坐标是搜索层数,纵坐标是国际品级分。上部横线是卡斯帕罗夫的分数作参考,A线透露表现对计算机水平的消极预计,B线透露表现消极预计,C线透露表现现实预计)
 
搜索深度和棋力相干曲线图
 
  专业人士的结论是:要与人类天下冠军争取冠军,必需做一台每秒运算10亿次的计算机(搜索到十四层的深度)。深蓝靠近了,但还达不到。【译注:注重这里搜索到十四层的深度,应当是指划定竞赛分配时刻内对一切回合而言。否则对一步棋不限制时刻地搜索,也许对一些简朴局势的搜索,要到达十四层对现今众多快速计算机来说真实不是难事。】
  固然,顺序的质量也饰演主要脚色。明天的顶级小我私家计算机顺序象FritzJunior能够到达并凌驾每秒处置责罚50万个局势。它们现实上以前凌驾2600分的水平,能够匹敌除天下前100名棋手之外的任何人。在快棋战里人类只需约莫前十几位能够胜任,而在超快棋里也许只需两、三明星类棋手能过关。【译注:也可见,每下降品级而要求的运算速率的提升绝不是仅仅直线式的,而是指数式的。以是每秒盘算50万次就到达2600分的特级巨匠水平,但要到达2800分,依据下面预算则要求每秒盘算10亿次之多。】
 
应战一切残局
 
  计算机棋力的一个主要方面是下棋时运用辽阔的残局库。若干代人类巨匠的知识累积和心得能够随意纰漏地贮存在硬盘上而且在残局阶段使用。纵然是小我私家计算机顺序也晓得几万万个残局局势,而且对这些局势的每一个都有完整的统计(例如显现过那些着法、用哪些着法胜过、运用过的人有若干,等等)。顺序经常是连走1520步以后才第一主要求盘算。若是没有从这些人类的残局知识英华中受益,顺序将实力大减。
  当计算机从数目重大的、从国际象棋历史累积上去的残局知识中取得结实优势之时,它们也从对局的其余一端搜索中受益。
 
残局数据库
 
  这又是那位滋扰力随处有的肯·汤普森充任了研讨先锋。他在80年月就最先天生和贮存棋盘上剩四至五子的一切相符划定礼貌的残局。一个模范的五子残局,例如王双象对王单马,包罗总数121万个局势。加上一只移动纷歧连的兵,这个数字增长到335万。汤普森编写顺序发生一切相符划定礼貌的局势并盘算出每一个残局能够的自愿转变。他还以一种体式格局把效果收缩,使得一张规范的CD-ROM能存缩小约20个残局。【译注:原文没有提其余一位对残局数据库的生长作出严重孝敬的Nalimov。】
  计算机运用这些残局数据库,能够把每一个残局走得一定完善,就象天主一样。关于棋盘显现子力及数目相符的任何局势,计算机能够马上知道该胜、该和照样该负,而且知道要若干步。它经常宣布15步棋以后取胜或将死,而执输棋那一种颜色的则能够最优化地戍守【即在一定被将死前每一步戍守都努力最优化】。深蓝运用了汤普森的残局数据库,而象Fritz这样的小我私家计算机顺序也把它们贯彻在搜索树中。这些对棋力有甚么滋扰另有待调查。很多若干五子的残局极之难题以至关于人类来说难以掌握,但这些五子残局关于汤普森正在勤奋的六子残局来说只是小巫见大巫,在某些六子局势里,要取胜不得一直止凌驾200步的盘算【译注:固然这是在纯计算机国际象棋领域来说,现实上人类走残局,心得和知识比重很大,有许多棋基础不用斟酌就知道该怎样走。但计算机却是“马马虎虎”地悉数去算。以是,从数字上比意义还不大】。自然硬件手艺的生长是便于计算机的,汤普森的六子残局,每一个包罗80200亿个局势,恰好能够收缩进一张DVD【译注:高端运用状况不得知,而普遍运用于小我私家计算机顺序的Nalimov残局数据库,悉数四子残局约莫占30MB贮存,悉数五子残局要求7GB,至于六子残局,现在可见的只是一些对照简朴局势而且一只兵也没有的,由于兵会升变,庞大性巨增,若是加上则相等时期内一样寻常计算机的硬盘难以蒙受,别忘了增长不是直线而是指数式的。】
  幸亏,局势数目更大得难以想象的七子残局,离发生依然很悠远。更幸亏的是,对局的两头即残局和残局,永不能够接在一同。是啊,如果发现一台计算机走了 1.e4 然后宣布40步棋之内将死,这就太难以让人收受接管了。然则计算机在竞赛中稳固战胜人类天下冠军也许只是时刻问题,若干年或若干十年以后……
  【译注:1997年深蓝在“回敬赛”中战胜棋王卡斯帕罗夫,但那次的场外不阴暗重点要点太多,效果一定有压服力,况且注重到两次竞赛总结果事实上照样卡帕罗夫以6.5-5.5战胜深蓝。200210月的克拉姆尼克对Deep Fritz人机大战,不阴暗重点要点又有点倾向于克拉姆尼克,以致言论以为计算机时机不大,且到时看。卡斯帕罗夫自己现在以为计算机真正稳固战胜人类天下冠军要到2010年,汤普森则以为能够要到2018年。有趣的是包孕贝利纳、许锋雄等人在上世纪90年月初以为计算机在1994年就能够够到达这点的。】
 
汤普森和卡斯帕罗夫
 
  出处:ChessBase网站的专栏
  译者:michael
  类型:略有删省
  • 上一篇
  • 下一篇 人机大战:魅力无限
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com