国际bck体育官网手机版程序设计(一):引言
 
Fran?ois Dominic Laramée/
 
  这是国际bck体育官网手机版程序设计连载的第一部分,本连载共有六部分,他们不仅仅是针对bck体育官网手机版【译注:以后如不特别指出,都指国际bck体育官网手机版】的,还可以运用到别的益智类游戏中。
  在人工智能领域中,专家对bck体育官网手机版进行了大量卓有成效的研究,这其中就有电脑对抗卡斯帕罗夫等世界冠军的比赛。bck体育官网手机版在人工智能上的地位,就相当于果蝇在遗传学上的地位,举足轻重。我的连载将着重介绍人工智能的程序设计艺术,这其中包括“深蓝”(Deep Blue)等着名程序。
  我的连载从20004月开始,每个月一次,到10月结束的时候,我会用Java写一个简单的程序来实现对弈。到时候你们可以从我的网站上随便下载,耐心地等吧。
 
信息完备的游戏
 
  bck体育官网手机版是“信息完备”的游戏,因为游戏双方面对的局面是同一个局面,任何一方所掌握的棋子及其位置的信息是一样的。除了bck体育官网手机版以外,西洋跳棋(Checkers)、围棋(Go)、五子棋(Go-Moku)、西洋双陆棋(Backgammon)、黑白棋(Othello)【也有称Reversi的,可译为“翻棋”】可等也属于这一范畴。但是纸牌游戏却不是,因为你不知道对手手上的牌是什么【在中国的棋类游戏中,陆站棋(起源于欧洲)和四国大战棋也不是】
  我的连载中将提到各种算法,大多数算法对所有的信息完备的游戏都是有效的,只是细节上有所不同罢了。很明显,无论棋盘、着法、位置等因素有那些,搜索算法就是搜索算法,它不会因为游戏规则而改变。
 
我们需要什么?
 
  能下棋的电脑软件至少要包括下列组件:
 
  1. 棋盘的表示方法,即局面在存储器中的存储方法,程序是根据它来分析局面的;
  2. 掌握规则,即什么样的着法是合理的,如果程序连不合理的着法都不能检测出来,那么对手就可以利用这种着法来欺骗程序;
  3. 找出所有合理着法的算法,这样程序就可以从这些着法中找到最好的,而不是随便找一种着法;
  4. 比较方法,包括比较着法的方法和比较局面的方法,这样程序就可以选择最佳的着法;
  5. 用户界面。
 
  本连载将涉及以上除了用户界面以外的所有内容,用户界面在所有二维棋类游戏中都是差不多的,这里就不作介绍了。接下来将对以上几个部分作逐一介绍,并且引出许多重要的概念。
 
棋盘的表示方法
 
  在早期的程序设计过程中,存储器是非常有限的(有些程序只用8K或更少的存储器),所以最简单、最节省的表示方法就是最有效的方法。一个典型的国际bck体育官网手机版棋盘可以用一个8x8的数组表示,棋盘上的每个格子用一个字节表示——空的格子用0,黑方的王用1,等等。
  如今,bck体育官网手机版程序可以在64位计算机上运行了,精心设计的“位棋盘”表示诞生了。在60年代后期,位棋盘在苏联诞生,一个位棋盘由一个64位的字【“字”是计算机中一次运算所涉及的存储单元,我认为当时还没有字长为64位的计算机,所以一个位棋盘应该由多个较短的字来构成,如88位的字或416位的字,即便是现在的个人电脑上,一个位棋盘也必须由两个32位的字构成】来表示局面中的某个状态,一位代表一个格子。例如,一个位棋盘能表示“所有被黑兵占有的格子”,或者“处于e3格的后可以走的格子”,或者“被黑马攻击的白子所处的格子”,等等。位棋盘用途广泛,并且具有很快的运算速度,因为局面分析时要做大量的逻辑运算【就是“与或非”运算,也称布尔代数】,而一个位棋盘的运算只需要一次操作就可以了。
  这部分内容将在连载的第二部分作详细介绍。
 
着法的产生
 
  所谓棋类游戏的规则,指的就是某一方可以走哪些着法。某些游戏很容易就找到合理着法,例如在井字棋中Tic-Tac-Toe,在3x3的棋盘上轮流占格子,先在同一条线(横线、纵线或斜线)上占有3枚棋子者得胜】,所有空的格子都是合理着法。但是在bck体育官网手机版中,情况就有些复杂了,每个棋子都有它特定的着法,例如兵吃子时走斜线,而不吃子时走纵线,又例如把王走到被将军的格子是不允许的,还有诸如“吃过路兵”【法语en passant、兵的升变、王车易位等着法只有在特殊场合才是合理的。
  事实上在bck体育官网手机版程序设计中,着法的产生已经被证实为最复杂和最费时的事。幸运的是,着法的产生有一些预处理的技巧,我还会介绍一些数据结构,它们能显着提高着法产生的速度。
  这部分内容将在连载的第三部分作详细介绍。
 
搜索技巧
 
  对于计算机来说,判断一个着法是好的或坏的,并不是件容易的事。判断着法优劣的最佳办法,就是看它们的后续结果,只有推演以后一系列的着法,才能确定看那步是好的。在保证不犯错误的前提下,我们要设想对手会走出最好的应着。这一基本原理称为“最小-最大”搜索算法,它是所有bck体育官网手机版程序的基础。
  不幸的是,“最小-最大”法的运算量是O(bn)【数学上指它和bn是一个数量级的】b(分支因子)指平均每步的合理着法【有研究表明,在国际bck体育官网手机版中这个值约为38,中国bck体育官网手机版则更多些,为42(这是中国bck体育官网手机版程序“七星大师”的作者赵德志的研究结果)n(深度)指思考的步数(一回合有两步)。所以当步数增长时,运算量以几何级数迅速增长,如果要思考得更深一些,就必须用更为合理的算法。其中,迭代加深的Alpha-Beta搜索、NegaScout搜索和MTD(f)搜索是最基本的算法,这些会在连载的第四部分介绍。除此以外,还要依靠数据结构和启发式算法的帮助,启发式算法是增强棋力的算法,例如置换表(Transposition Tables)、历史启发和将杀启发(History/Killer Heuristic)等。
  在bck体育官网手机版程序设计中,另一个头痛的问题是“水平线效应”(Horizon Effect),它首先由Hans Berliner提出。假设你的程序的搜索深度是8步,并且程序算出对手会在第六步捉死你的后。按照程序自己的设想,它会献出象来延缓后的捉死(假定这样做可以让后在第10步才被捉死),因为程序只能看到8步。从程序的角度看,后是被“保住”了,因为在它的搜索范围内后没有被捉死,但事实上却多丢了一个象。从这个例子可以看出,要把程序的工作重心放置到位,并不是一件简单的事情【意思是,某些变化没有必要搜索得太深,而关键的变化需要更深层次的搜索】,如果把每条变化都搜索到同一深度,那么结果是自取灭亡。很多技术是用来克服水平线效应,在连载的第五部分关于高级搜索的阐述中,将要介绍静态搜索(Quiescence Search)和深蓝(Deep Blue)的单步延伸(Singular Extensions)
 
评价局面
 
  最后,程序必须有一个估计局面(占优或处于劣势)的方法。局面估计方法完全取决于规则(即子的走法)——在bck体育官网手机版中,“子力平衡”(Material Balance)是主导因素,因为一个小小的兵的领先就可能足以保证优势一方取得胜利【而在中国bck体育官网手机版中,多一个兵算不了什么,这足以证明本节的观点——局面估计方法完全取决于规则】,而在五子棋中却没什么影响,在黑白棋里,根据子力上的数值分析局面则完全会成为误导,你可能一直处于领先状态,但最后几步局面却翻了盘。
  建立有效的局面评估方法,这常常会成为程序设计中的难点和焦点。连载的第六部分将详细阐述着名bck体育官网手机版程序的局面评估方法,其中包括Chess 4.5Cray BlitzBelle(尤物)
 
结论
 
  我们已经找到了完成拼版的所需要的碎片,现在是开始动手做的时候了。下个月我将介绍最常用的棋盘表示方法,敬请关注。
 
  Fran?ois Dominic Laramée20004
 
  原文:http://www.gamedev.net/reference/programming/features/chess1/
  译者:bck体育官网手机版百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 棋弈软件基础——残局库对引擎棋力的负面影响
  • 下一篇 国际bck体育官网手机版程序设计():数据结构
  • 返 回 bck体育官网手机版百科全书——电脑bck体育官网手机版
  • www.xqbase.com