国际象棋顺序设想(一):引言
 
François Dominic Laramée/
 
  这是国际象棋顺序设想连载的第一局部,本连载共有六局部,他们不但单是重点一定象棋【译注:以后如不稀奇指出,都指国际象棋】的,还能够运用到其余益智类游戏中。
  在野生智能领域中,专业人士工具棋停止了少量行之有用的研讨,这其中就有计算机匹敌卡斯帕罗夫等天下冠军的竞赛。象棋在野生智能上的职位,就相即是果蝇在遗传学上的职位,无足轻重。我的连载将着重引见野生智能的顺序设想艺术,这其中包孕“深蓝”(Deep Blue)等著名顺序。
  我的连载从20004月最先,每月一次,到10月完毕的时刻,我会用Java写一个简朴的顺序来完成棋战。到时刻你们能够从我的网站上随意下载,耐性地等吧。
 
信息完整的游戏
 
  象棋是“信息完整”的游戏,由于游戏双方面临的局势是统一个局势,任何一方所掌握的棋子及其职位的信息是一样的。除了象棋之外,西洋跳棋(Checkers)、围棋(Go)、五子棋(Go-Moku)、西洋双陆棋(Backgammon)、是非棋(Othello)【也有称Reversi的,可译为“翻棋”】可等也属于这一领域。然则纸牌游戏却不是,由于你不知道对手手上的牌是甚么【在中国的棋类游戏中,陆站棋(起源于欧洲)和四国大战棋也不是】
  我的连载中将说到种种算法,大少数算法对一切的信息完整的游戏都是有用的,只是细节上有所分歧而已。很显著,不论棋盘、着法、职位等重点要点有那些,搜索算法就是搜索算法,它不会由于游戏划定礼貌而改动。
 
咱们要求甚么?
 
  能下棋的计算机软件最少要包孕以下组件:
 
  1. 棋盘的透露表现要领,即局势在存储器中的存储要领,顺序是依据它来剖析局势的;
  2. 掌握划定礼貌,即甚么样的着法是恰当的,若是顺序连分歧适的着法都不能检测出来,那末对手就能够够应用这类着法来诈骗顺序;
  3. 找出一符恰当着法的算法,这样顺序就能够够从这些着法中找到最好的,而不是随意找一种着法;
  4. 对照要领,包孕对照着法的要领和对照局势的要领,这样顺序就能够够选择最好的着法;
  5. 用户界面。
 
  本连载将触及上述除了用户界面之外的一切内容,用户界面在一切二维棋类游戏中都是差不多的,这里就不作引见了。接上去将对上述几个局部作逐一引见,而且引出许多主要的观点。
 
棋盘的透露表现要领
 
  在早期的顺序设想历程当中,存储器长短常有限的(很多若干顺序只用8K或更少的存储器),以是最简朴、最节约的透露表现要领就是最有用的要领。一个模范的国际象棋棋盘能够用一个8x8的数组透露表现,棋盘上的每一个格子用一个字节透露表现——空的格子用0,黑方的王用1,等等。
  现在,象棋顺序能够在64位盘算机上运转了,细心设想的“位棋盘”透露表现降生了。在60年月前期,位棋盘在苏联降生,一个位棋盘由一个64位的字【“字”是盘算机中一次运算所触及的存储单元,我以为事先还没有字长为64位的盘算机,以是一个位棋盘应当由多个较短的字来组成,如88位的字或416位的字,纵使是现在的小我私家计算机上,一个位棋盘也必需由两个32位的字组成】来透露表现局势中的某个状态,一位象征一个格子。譬喻,一个位棋盘能透露表现“一切被黑兵占有的格子”,也许“处于e3格的后能够走的格子”,也许“被黑马进击的白子所处的格子”,等等。位棋盘用途普遍,而且具有很快的运算速率,由于局势剖析时要做少量的逻辑运算【就是“与或非”运算,也称布尔代数】,而一个位棋盘的运算只要求一次支配就能够够了。
  这局部内容将在连载的第二局部作详细引见。
 
着法的发生
 
  所谓棋类游戏的划定礼貌,指的就是某一方能够走哪些着法。某些游戏很随意纰漏就找到恰当着法,譬喻在井字棋中Tic-Tac-Toe,在3x3的棋盘上轮替占格子,先在统一条线(横线、纵线或斜线)上占有3枚棋子者失利】,一切时刻的格子都是恰当着法。然则在象棋中,状况就很多若干庞大了,每一个棋子都有它特定的着法,譬喻兵吃子时走斜线,而不吃子时走纵线,又譬喻把王走到被将军的格子是不允许的,另有诸如“吃过路兵”【法语en passant、兵的升变、王车易位等着法只需在稀奇场所才是恰当的。
  现实上在象棋顺序设想中,着法的发生以前被证实为最庞大和最费时的事。侥幸的是,着法的发生有一些预处置责罚的窍门,我还会引见一些数据组织,它们能显著提升着法发生的速率。
  这局部内容将在连载的第三局部作详细引见。
 
搜索窍门
 
  关于盘算机来说,剖断一个着法是好的或坏的,并非件随意纰漏的事。剖断着法优劣的最好设施,就是看它们的后续效果,只需推演以后一系列的着法,才气一定看那步是好的。在确保不出毛病的条件下,咱们要想象对手会走出最好的应着。这一基来源根基理称为“最小-最大”搜索算法,它是一切象棋顺序的根蒂基本。
  不幸的是,“最小-最大”法的运算量是O(bn)【数学上指它和bn是一个数目级的】b(分支因子)指匀称每步的恰当着法【有研讨注解,在国际象棋中这个值约为38,中国象棋则更多些,为42(这是中国象棋顺序“七星巨匠”的作者赵德志的研讨效果)n(深度)指思索的步数(一回合有两步)。以是当步数增长时,运算量以若干级数迅速增长,若是要思索得更深一些,就必需用越发恰当的算法。其中,迭代加深的Alpha-Beta搜索、NegaScout搜索和MTD(f)搜索是最基本的算法,这些会在连载的第四局部引见。除此之外,还要依托数据组织和启示式算法的资助,启示式算法是增强棋力的算法,譬喻置换表(Transposition Tables)、历史启示和将杀启示(History/Killer Heuristic)等。
  在象棋顺序设想中,其余一个头痛的问题是“水平线效应”(Horizon Effect),它首先由Hans Berliner提出。假定你的顺序的搜索深度是8步,而且顺序算出对手会在第六步捉死你的后。依照顺序自身的想象,它会献出象来减慢后的捉死(假定这样做可以让后在第10步才被捉死),由于顺序只能发现8步。从顺序的角度看,后是被“保住”了,由于在它的搜索局限内后没有被捉死,但现实上却多丢了一个象。从这个案例能够看出,要把顺序的事情重心放置到位,并非一件简朴的事项【意义是,某些转变没有需要搜索得太深,而重点的转变要求更深条理的搜索】,若是把每条转变都搜索到统一深度,那末效果是自投罗网。许多手艺是用来战胜水平线效应,在连载的第五局部关于低级搜索的论述中,将要引见静态搜索(Quiescence Search)和深蓝(Deep Blue)的单步延长(Singular Extensions)
 
评定局势
 
  最终,顺序必需有一个预计局势(占优或处于优势)的要领。局势预计要领完整取决于划定礼貌(即子的走法)——在象棋中,“子力平衡”(Material Balance)是主导重点要点,由于一个异常小的兵的抢先就能够够足以确保优势一方取得胜利【而在中国象棋中,多一个兵算不了甚么,这足以证实本节的看法——局势预计要领完整取决于划定礼貌】,而在五子棋中却没甚么滋扰,在是非棋里,依据子力上的数值剖析局势则完整会成为误导,你能够一直处于抢先状态,但最终几步局势却翻了盘。
  竖立有用的局势评价要领,这经常会成为顺序设想中的难点和中心。连载的第六局部将详细论述著名象棋顺序的局势评价要领,其中包孕Chess 4.5Cray BlitzBelle(尤物)
 
结论
 
  咱们以前找到了完成拼版的所要求的碎片,现在是最先着手做的时刻了。下个月我将引见最经常使用的棋盘透露表现要领,敬请留意。
 
  François Dominic Laramée20004
 
  原文:http://www.gamedev.net/reference/programming/features/chess1/
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 棋弈软件根蒂基本——残局库对引擎棋力的负面滋扰
  • 下一篇 国际象棋顺序设想():数据组织
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com