《对弈程序基本技术》专题
 
国际象棋程序剖析
 
T.A. Marsland */
* 阿尔伯达大学计算机科学系
 
一、简介
 
  从理论上说,让机器下国际象棋是一个简单的游戏,只要每一步都考虑各种可能的着法,以及每种着法的后续变化,如此下去直到将死或和棋。但是实际操作中,这种策略是不可行的,因为需要考虑的每种着法加起来会是天文数字。
  不管人类还是机器去下棋,都有一整套下棋的理论,人类好几百年前就开始下棋,在近二百年里有很多理论资料,而机器下棋只有五十多年的历史,在机器下棋的诸多理论中,最著名的属Claude Shannon1949-50年提出的两个完全对立的策略——用蛮力考虑所有着法的策略(A策略),以及靠知识来选择其中一部分着法的策略(B策略)。尽管早在Shannon以前,就有一些电子机械可以下比国际象棋简单的棋类,然而Shannon的理论却是现代电脑象棋发展的基础。
 
  如今的象棋程序把棋局看成树状结构,每个局面表示成棋局树中的一个结点,每个着法代表它的一个分枝(一个结点和深一个结点的连接)。这样,树就由双方不同层面上的所有着法组成(树的一个层面用“层”(Ply)这个术语表示,代表一方走的一步棋)
  现在通常的策略是,把树由浅至深分为三个阶段,第一阶段用蛮力搜索(ShannonA策略),第二阶段用选择性搜索(B策略),第三阶段用称为“静态搜索”(Quiescence Search)的策略,来处理最后变化非常剧烈的局面,在最后一个阶段里,程序只评价吃子着法,兵升变的潜力,将军产生的后果,以及一些强制性着法。所有的程序都使用相同的算法——深度优先的Alpha-Beta算法,而不同之处在于每个阶段选择什么样的深度。
  通常搜索的深度不是固定的,而是根据当前搜索到的着法在小范围内变动,例如某个结点是将军的局面,那么它的分枝数很少,这个区域内搜索应当加深一些。策略上有非常多的选择,使得程序使用相同模型的时,他们的走棋风格和搜索速度会有显著的差别。
 
二、树状搜索
 
  人类下棋时,往往分析一小部分着法并作展开,相比选择着法而言,机器更愿意考虑得完备,所以需要发展一套逐步求精的技术。“迭代加深”(Iterative Deepening)这一技术取代了固定的深度,让机器一次次做更深层的搜索(先是搜索N层,然后搜索N + 1层,N + 2层,等等),直到按计划分配的时间用完为止,这样就可以让机器在有限的时间内找出最好的着法。诸如反驳表和置换表等技术,在与迭代加深结合起来后,可以对着法重新排序,使得下一次迭代时“主要变化”(Principal Variation)(上一次找到的最好着法)优先考虑。
  另一个排序着法的技术就是记录一些“杀手”着法,这些着法要优先试探,杀手着法就是在搜索树的其他位置能产生截断或裁剪的着法。杀手着法通常是吃子的着法,因此可以简单地认为,吃子的着法应该在其他着法之前考虑。在很多程序中,这个技术被拓展为“历史启发表”(History Heuristic Table),通常是64x64的数组,每个元素存放了该着法引起裁剪的次数。
 
  排序着法可以大幅度提高深度优先Alpha-Beta搜索的效率,此外还有三个算法也起到同样作用——Pearl的侦察(Scout)算法以及相关的负值侦察(NegaScout)和主要变例搜索(Principal Variation Search,简称PVS)方法,它们具有同一个思想:当主要变例找到时,可以先去验证其他着法是否都不如这个着法好,如果验证下来不是这样,那么它们必须重新搜索(因为它们是更好的着法,必须做完全的搜索)
  另一个能减少搜索量的技术称为“期望搜索”(Aspiration Search),根据当前局面估计一个范围(通常正负半个兵),用这样一个窗口进行搜索。尽管期望搜索并不那么有效,但是用它的人还是很多的,因为它比主要变例搜索更容易理解。
 
  深层次的搜索到底能提高多少精确度,这是很难衡量的。任意局面其搜索树的大小有很大的差异,很多残局每方有约8种着法,而复杂的中局里每方可能有多达80种着法,就现在的技术而言,一般程序在中局阶段能完全考虑710层的变化(有个程序设计师声称选择性地搜索能达到40层!)
  “选择性延伸”(Selective Extension)是对一些关键着法作更深入的探索,每个程序设计师对这些着法都有自己的界定——可以是防御杀棋的着法,或是为避免失子而作的反击。选择性延伸不能和“单步延伸”(Singular Extension)混淆起来,后者是对最好的一步着法进行的更深层次的检查,来验证这个着法是否仍旧是最好的。从某种意义上说它对主要变例进行了短的延伸,是一种很花时间但很有意义的方法。
 
  而用得最广泛的做法是“空着启发”(Null-Move Heuristic),即假设一方连走两步,如果产生的结果更糟的话,后面那步变化就应该抛弃掉。由于水平线效应,一些看不到的不可避免的失子,通过这种方法能看到。很多向前裁剪方法起不到很好的效果,但空着向前裁剪往往是很有效的。
 
三、置换表
 
  置换表的作用如同缓冲存储器,用来记录前面搜索过的局面,这些局面通常在迭代加深的早期搜索过。之所以称为“置换表”(Transposition Table),是因为当着法次序发生置换时会有相同的局面。置换表中存储的信息除了局面以外,还有局面的评分,它的最佳着法,以及前一次搜索的深度。
  “评分”指的是在搜索树的顶端结点(搜索能够到达的水平)对局面进行的评价,这个评价通常包括了静态搜索,来消除由吃子等着法引起的局面的不确定性,包括考虑兵的升变等。
  在残局的搜索中,置换表的作用发挥得更为明显,每个局面只有很少的着法需要考虑,其他着法都因为置换的发生而不必再去搜索。
  置换表并不增加代码的长度和复杂性,为置换表分配空间是小事一桩。置换表的每个局面一般需要约10个字节,通常程序使用可以记录32K1M个局面的置换表。1993年超级电脑(Supercomputer)程序自称他们使用了1G个局面的置换表,而对于程序员来说这完全取决于存储器的容量。
 
四、程序的性能及其测评方法
 
  尽管各种程序基本方法是一样的,但是在相同硬件条件下,它们的表现有很大程度的差异,一定程度上这体现了程序设计师对程序所作的投入。
  比如说,尽管每个程序都有开局库,但开局库是没有哪本书规定的,每个程序小组都在开发自己的开局库。现在开局库的大小从10,000个局面到500,000个局面不等(也有程序试验过1.7M个局面的开局库)
  相反,只有少数人使用Ken Tompson制作在CD-ROM上的5子到6子的残局库,一方面原因是目前数据的读取非常缓慢,另一方面原因是大部分棋局都会在用到这些残局库之前结束(程序设计师们在利用时间的问题上,可能考虑得比较现实吧)
 
  在运行速度的层面上,当今的程序在单处理器上每秒钟可以分析3,000500,000个局面。在相同机器上程序速度的差别是巨大的,这当然有很多解释,用汇编语言写的程序能有比较快的速度,用同一语言来写的程序,用不同的编译器也会导致速度的不同。
  其中更多的因素在于蛮力搜索、选择性搜索和静态搜索这三个阶段所占的比例。选择性搜索阶段需要额外的时间,因为它还判断哪些着法需要搜索,而在这个慢速、以知识为基础的阶段中,诸多程序在速度上的差别是非常明显的。
  另一个影响搜索速度和强度的因素,是程序使用的置换表的大小。
 
  尽管很多象棋程序非常相似,它们的棋力差别仍旧可能非常大。测试棋力是很复杂的过程,由于在正式比赛中程序仍然是可调节的,因此“瑞典排名表”(Swedish Rating List)的制作小组提出了一个传统的方案——所有的商业程序都连续自动地进行对决,得到几百场比赛的胜负结果,并从这些结果中计算出ELO等级分,即美国和其他地方棋手们通用的等级分。
  美国棋手的平均等级分从1500开始,专家的分数在2000-2200,大师在2200-2400。世界排名300以内的特级大师,等级分则更高。在第八届世界电脑象棋锦标赛中,大多数程序的等级分在2100-2500。现在瑞典排名表刊登在每期的《国际电脑象棋协会杂志》(International Computer Chess Association Journal)上。
 
五、展望
 
  如今顶极的电脑可以挑战特级大师了,尤其是在快棋赛中,单机要比多处理器的并行系统更有优势。单机之所以快,是因为它们不必通过网络来传输着法,而由10100个处理器组成的多处理器系统,则在两小时内完成40步的标准赛制中表现得更好。不久我们将会有由1000个高性能处理器组成的系统,到那个时候电脑毫无疑问能比人类棋手算得更远,这将多少能弥补电脑的不足——不具备人类棋手所擅长的战略构思。
  人类棋手对于局势的简化和基本形势的判断方面都具有高超技巧,他们也善于在对手身上找到弱点,除非局面是无法挽回的。尽管人类棋手有这些优势,我们一直以来都预测说,机器在5年内能击败人类,现在这个目标正越来越近。要实现这个目标可能需要花上十多年,但是最终肯定会实现的。
 
《国际象棋程序剖析》参考资料
 
  1. 《电脑象棋概论》(Computer Chess Compendium)D.N.L. Levy著,Springer-Verlag出版社,1988年;
  2. 《电脑象棋与搜索》(Computer Chess and Search)T.A. Marsland文,《人工智能百科全书》(Encyclopedia of Artificial Intelligence)一书的224-241页,S. Shapiro主编,J. Wiley & Sons出版社,1992年第二版;
  3. ICCA(国际电脑象棋协会)杂志》(International Computer Chess Association Journal),自1983年以来每年四期,ICCA编辑部([荷兰马斯特里赫特]林堡大学(University of Limburg)计算机系,P.O. Box 616, 6200 MD Maastricht, The Netherlands)出版;
  4. 电脑、象棋与认知(Computers, Chess and Cognition)T.A. MarslandJ. Schaeffer主编,Springer-Verlag出版社,1990年;
  5. 电脑象棋进展(Advances in Computer Chess),一至七卷,从19771994年由多人主编,由多个出版社出版。
 
  出处:http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 其他策略——策略和技巧
  • 下一篇
  • 返 回 象棋百科全书——计算机博弈
  • www.xqbase.com