《对弈程序基本技术》专题

　

国际象棋程序剖析

　

T.A. Marsland */ 文

* 阿尔伯达大学计算机科学系

　

一、简介

　

　　从理论上说，让机器下国际象棋是一个简单的游戏，只要每一步都考虑各种可能的着法，以及每种着法的后续变化，如此下去直到将死或和棋。但是实际操作中，这种策略是不可行的，因为需要考虑的每种着法加起来会是天文数字。

　　不管人类还是机器去下棋，都有一整套下棋的理论，人类好几百年前就开始下棋，在近二百年里有很多理论资料，而机器下棋只有五十多年的历史，在机器下棋的诸多理论中，最著名的属Claude Shannon在1949-50年提出的两个完全对立的策略——用蛮力考虑所有着法的策略(A策略)，以及靠知识来选择其中一部分着法的策略(B策略)。尽管早在Shannon以前，就有一些电子机械可以下比国际象棋简单的棋类，然而Shannon的理论却是现代电脑象棋发展的基础。

　

　　如今的象棋程序把棋局看成树状结构，每个局面表示成棋局树中的一个结点，每个着法代表它的一个分枝(一个结点和深一个结点的连接)。这样，树就由双方不同层面上的所有着法组成(树的一个层面用“层”(Ply)这个术语表示，代表一方走的一步棋)。

　　现在通常的策略是，把树由浅至深分为三个阶段，第一阶段用蛮力搜索(Shannon的A策略)，第二阶段用选择性搜索(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种着法，就现在的技术而言，一般程序在中局阶段能完全考虑7到10层的变化(有个程序设计师声称选择性地搜索能达到40层！)。

　　“选择性延伸”(Selective Extension)是对一些关键着法作更深入的探索，每个程序设计师对这些着法都有自己的界定——可以是防御杀棋的着法，或是为避免失子而作的反击。选择性延伸不能和“单步延伸”(Singular Extension)混淆起来，后者是对最好的一步着法进行的更深层次的检查，来验证这个着法是否仍旧是最好的。从某种意义上说它对主要变例进行了短的延伸，是一种很花时间但很有意义的方法。

　

　　而用得最广泛的做法是“空着启发”(Null-Move Heuristic)，即假设一方连走两步，如果产生的结果更糟的话，后面那步变化就应该抛弃掉。由于水平线效应，一些看不到的不可避免的失子，通过这种方法能看到。很多向前裁剪方法起不到很好的效果，但空着向前裁剪往往是很有效的。

　

三、置换表

　

　　置换表的作用如同缓冲存储器，用来记录前面搜索过的局面，这些局面通常在迭代加深的早期搜索过。之所以称为“置换表”(Transposition Table)，是因为当着法次序发生置换时会有相同的局面。置换表中存储的信息除了局面以外，还有局面的评分，它的最佳着法，以及前一次搜索的深度。

　　“评分”指的是在搜索树的顶端结点(搜索能够到达的水平)对局面进行的评价，这个评价通常包括了静态搜索，来消除由吃子等着法引起的局面的不确定性，包括考虑兵的升变等。

　　在残局的搜索中，置换表的作用发挥得更为明显，每个局面只有很少的着法需要考虑，其他着法都因为置换的发生而不必再去搜索。

　　置换表并不增加代码的长度和复杂性，为置换表分配空间是小事一桩。置换表的每个局面一般需要约10个字节，通常程序使用可以记录32K到1M个局面的置换表。1993年超级电脑(Supercomputer)程序自称他们使用了1G个局面的置换表，而对于程序员来说这完全取决于存储器的容量。

　

四、程序的性能及其测评方法

　

　　尽管各种程序基本方法是一样的，但是在相同硬件条件下，它们的表现有很大程度的差异，一定程度上这体现了程序设计师对程序所作的投入。

　　比如说，尽管每个程序都有开局库，但开局库是没有哪本书规定的，每个程序小组都在开发自己的开局库。现在开局库的大小从10,000个局面到500,000个局面不等(也有程序试验过1.7M个局面的开局库)。

　　相反，只有少数人使用Ken Tompson制作在CD-ROM上的5子到6子的残局库，一方面原因是目前数据的读取非常缓慢，另一方面原因是大部分棋局都会在用到这些残局库之前结束(程序设计师们在利用时间的问题上，可能考虑得比较现实吧)。

　

　　在运行速度的层面上，当今的程序在单处理器上每秒钟可以分析3,000到500,000个局面。在相同机器上程序速度的差别是巨大的，这当然有很多解释，用汇编语言写的程序能有比较快的速度，用同一语言来写的程序，用不同的编译器也会导致速度的不同。

　　其中更多的因素在于蛮力搜索、选择性搜索和静态搜索这三个阶段所占的比例。选择性搜索阶段需要额外的时间，因为它还判断哪些着法需要搜索，而在这个慢速、以知识为基础的阶段中，诸多程序在速度上的差别是非常明显的。

　　另一个影响搜索速度和强度的因素，是程序使用的置换表的大小。

　

　　尽管很多象棋程序非常相似，它们的棋力差别仍旧可能非常大。测试棋力是很复杂的过程，由于在正式比赛中程序仍然是可调节的，因此“瑞典排名表”(Swedish Rating List)的制作小组提出了一个传统的方案——所有的商业程序都连续自动地进行对决，得到几百场比赛的胜负结果，并从这些结果中计算出ELO等级分，即美国和其他地方棋手们通用的等级分。

　　美国棋手的平均等级分从1500开始，专家的分数在2000-2200，大师在2200-2400。世界排名300以内的特级大师，等级分则更高。在第八届世界电脑象棋锦标赛中，大多数程序的等级分在2100-2500。现在瑞典排名表刊登在每期的《国际电脑象棋协会杂志》(International Computer Chess Association Journal)上。

　

五、展望

　

　　如今顶极的电脑可以挑战特级大师了，尤其是在快棋赛中，单机要比多处理器的并行系统更有优势。单机之所以快，是因为它们不必通过网络来传输着法，而由10到100个处理器组成的多处理器系统，则在两小时内完成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. Marsland和J. Schaeffer主编，Springer-Verlag出版社，1990年；

　　5. 电脑象棋进展(Advances in Computer Chess)，一至七卷，从1977到1994年由多人主编，由多个出版社出版。

　

　　出处：http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html

　　译者：象棋百科全书网 (webmaster@xqbase.com)

　　类型：全译

上一篇　其他策略——策略和技巧

下一篇

返　回　象棋百科全书——计算机博弈

www.xqbase.com