《对弈程序基本技术》专题
 
残局库
 
Martin Fierz */
* 瑞士Windisch应用科学学院(Aargau学院)
 
简介
 
  残局库在很多棋类游戏中扮演着非常重要的角色,例如九人MorrisAwari和西洋跳棋(Checkers)(其中九人Morris已经完全可解了,这要归功于残局库的使用)。在其他棋类中,残局库就不那么重要了(例如国际象棋),而某些棋类制作残局库是不现实的(如连四子棋、黑白棋和围棋)。你是否已经发现这些棋类的差异了?通常只有在盘面上棋子数量很少的情况下,残局库才能实现。适用残局库有个确切的棋子数量的界限,它取决于棋类的复杂性。有些棋类随着对局的进行,棋子数量是减少的,那么残局库就是可行的;而有些棋类的棋子数量是增加的或者不变的,那么残局库就是无法计算的(除非棋类异常简单),无论如何残局库取决于具体的棋类。例如在国际象棋中,有多达6子的残局库(王车兵对王车兵等),而这种残局(包括其他不超过6子的残局)在实战中不是经常出现的,因此残局库对棋力的影响并不是很大。而在(盎格鲁-萨克森式的)西洋跳棋里,有多达8子的残局库,而10子的残局库也已经在计算了,这就意味着在有吃必吃的规则下,很多棋局会很快走到有残局库的局面中,因此残局库使得西洋跳棋的棋力有了很大的提高。要让某种棋类完全可解,通常总是要借助于残局库的——从起始局面开始向前搜索,结合残局库,就能解出这盘棋。Gasser用这种办法解决了九人Morris,而Chinook(最著名的西洋跳棋程序)的小组正在用这个方法解西洋棋。
 
残局库的不同类型
 
  残局库有不同的类型,而它们都可以知道残局库中某个特定的局面是赢棋、是输棋还是和棋。如果这就是残局库包含的所有信息,就称为“胜负和”(WLD)残局库;如果知道多少步以后棋局会结束,就称为“杀棋步数”(DTMDistance-to-Mate)残局库;如果只知道多少步以后会转换为另一种类型的局面,就称为“转换步数”(DTCDistance-to-Conversion)残局库。WLD残局库有个问题,即便程序处于胜利局面,也未必能赢下棋局。尽管残局库知道某个局面已经是胜利局面,并且知道走哪步能继续保持胜利局面,但是保持胜利局面的着法可能会距离杀棋更远,而程序又不知道该选择哪步保持胜利局面的着法。【译注:更具体的说明请参阅《胜利局面中的强制过程》一文。】DTM残局库显然在这个方面做得比较好,因为你只要选择DTM(转换步数)最少的那个保持胜利局面的着法。DTC残局库也能够在胜利局面下走出取得胜利的着法,但程序走的步数可能会比必要的步数多。至今还有人使用WLD残局库,你可能很怀疑。原因很简单,储存胜负和的信息只需要很小的空间,如果残局库比计算机的存储器大得多(通常如此),那么残局库有很多部分可以放入存储器。从磁盘上读取残局库不是一个好的选择,因为磁盘跟存储器比起来慢得多。
 
残局库的生成
 
  残局库的生成是一个相对比较简单的过程,尽管有很多细节,但这不影响生成过程的理解。残局库生成的基本算法称为“后退式分析”(Retrograde Analysis),它是由Ken Thompson发明的(至少是首先使用的)。以下就是整个过程:
  以我们要生成“王车对王”的残局为例,你要从“索引函数”(Index Function)开始,每个可能的王车对王局面都有一个数字。索引函数必须能倒过来映射到以数字x为代表的局面。理想情况下,索引函数会把所有N个合理的王车对王局面映射为0, 1, ..., N - 1。如果是这种情况,我们称之为“无间隙”(Gapless)的索引。一般情况下,索引函数把所有合理局面编号为0, 1, ..., M - 1,而M > N,我们称其为“有间隙”(Gapped)的索引。有间隙的索引往往更简单,因为构造一个有间隙的索引函数要比无间隙的索引函数简单得多。后退式分析需要的存储器跟索引号的最大值成正比,因此如果构造了一个MN大得多的索引函数,那么你会浪费很多存储器。
  一旦有了索引函数,后退式分析算法就只要做以下几件事:
 
  (1) 初始化:生成两个长度都为N的数组,分别存放结果(WIN/LOSS/DRAW,代表胜负和)DTC。把所有的结果都设成UNKNOWN(代表未知),所有的DTC计数器都设成0。你会发现,你需要4个数来表示结果,因此数组的数据类型是4个值的数(2)。当然,还有些根本不存在的局面,你需要自行处理。
  (2) 杀棋遍历:逐一检查每个局面是否是杀棋局面,如果是的,就把这个局面的结果设成LOSS,表示即将走的一方输了。如果棋类允许“逼和”的存在,也必须作逼和的检查,并赋值为DRAW。把每个UNKNOWN局面的DTC计数器加1
  (3) 对每个UNKNOWN的局面,生成所有后续局面并看它们都有哪些结果。只要其中有一个后续局面是LOSS,就把这个局面设成WIN。如果所有后续局面都是WIN,就把这个局面设成LOSS。如果你遍历了所有局面但没有一个局面能设WINLOSS的,就跳到第5步。
  (4) 把每个UNKNOWN局面的DTC计数器加1,并回到第3步。
  (5) 把每个UNKNOWN局面设成DRAW,算法就结束了。
 
  这个算法显然是确保完成的。在第3步里当吃子发生时,你就要读取少一个子的残局库。很明显,没有王车对王的残局库,你无法独立地生成王车对王马的残局库。如果你只要生成WLD残局库,就可以不要DTC计数器。如果你需要生成DTM残局库,你就需要在局面转换时传递DTM值。以上算法有很多优化方案,但是我不想展开讨论,最基本的算法已经非常简单明了了,为什么再舍弃它呢?
  明白了整个算法后,你就知道为什么叫做“后退式”了——该算法总是从已知局面(杀棋或能转换为低级别的残局库局面)向后找,按照上述算法的第3和第4步,每次遍历就后退半步。我们拿一个局面举例说明,白王在g3,黑王在h1,白车在a2,黑先走8/8/8/8/8/6K1/R7/7k b - - 0 1。在遍历杀棋局面时,按照上述算法找到白王在g3,白车在a1,黑王在g1,黑先走8/8/8/8/8/6K1/8/R5k1 b - - 0 1,这个局面是杀棋,所以把它设为LOSS。在我们要讨论的这个局面中,根本不能检查到什么。在主循环的第一次遍历中,会为“白王在g3,黑王在g1,白车在a28/8/8/8/8/6K1/R7/6k1 w - - 0 1产生所有着法,发现走了Rb2-b1后就是LOSS局面,根据规则这个局面就设为WIN。下一步,为黑王在h1的局面8/8/8/8/8/6K1/R7/7k b - - 0 1找后续局面,发现所有的后续局面都是WIN局面(这个局面的后续局面只有一个)。最后把这个局面设成LOSS,就得到了正确的结果。
 
索引函数
 
  索引函数对这个算法非常重要,你无法存储整个局面并对他们设定结果,因为结果只需要2位,而整个局面需要用大量存储器来描述。如果你存储整个局面,你就会浪费大量的存储器。用了索引函数以后,你就能够简单地用一个数字来代表局面了,你不需要把结果和索引数字都记下来,而只需要以索引数字为数组的指标,只在数组中存储结果。那么如何才能找到符合上述性质的索引函数呢?看上去这是个很吓人的工作,实际上用简单的方法来构造索引函数是可行的。对于棋子各不相同的残局(例如白王、白车和黑王),就非常简单,把格子标号为063,就可以写下这样的公式:
 
index = wK_index + 64 * wR_index + 64 * 64 * bK_index;
 
  这个函数完成了局面到数字的转换,并且它是可逆的(wK_index = index % 64, wR_index = (index / 64) % 64,等等),但是它会产生一些不合理局面(例如几个子在同一个格子上,或两个王紧挨着)。这个函数也没有利用棋盘的对称性。这些细节问题是完全可以解决的,但是在这里我不想多说了。那么如果棋盘上有多于一个的相同棋子,例如王双车对王,怎么办呢?我们照样写:
 
index = wK_index + 64 * wR1_index + 64 * 64 * wR2_index + 64 * 64 * 64 * bK_index;
 
  这样当然很管用,但是非常愚笨,因为1号车在x格而2号车在y格,情况跟2号车在x格而1号车在y格是一样的。这样我们的索引就比必要的数多了一倍!为了解决这个问题,我们用组合公式来表示2个相同的子在64个位置上的情况:在数学课上你肯定学过用N = 64 × 63 / 2来做。因此我们可以写成:
 
index = wK_index + 64 * combinedindex + 64 * N * bK_index;
 
  剩下来的问题就是由车的具体位置来计算“组合的车的索引”了,它是064 × 63 / 2 - 1之间的数。用r1r2表示两个车的位置,并且r1 < r2(这样就等同于除以2!)。我们有:
 
combinedindex = bicoef(r1, 1) + bicoef(r2, 2);
 
  这里bicoef(x, y)代表xy(x > y)的二项式系数,即x! × y! / (x - y)!,任意数量的棋子都可以由这个组合索引公式产生。它的逆公式有点复杂,如果是k个子在n个格子上的组合索引,我们就必须用顺序搜索的办法来分析它的组成:因为组合索引的最后一项总是最大的,所以我们要依次计算i = n - 1, n - 2, ...bicoef(i, k),直到比组合索引数小为止。一旦找到了i,我们就知道它在第i格上,然后在组合索引上减去bicoef(i, k)。然后我们依次计算j = i - 1, i - 2, ...bicoef(j, k - 1),因为我们已经在建立索引函数的时候知道j < i了。
 
压缩
 
  当你开始生成残局库时,你一定会马上意识到你要建立的残局库是非常庞大的。例如,8子的西洋跳棋残局库如果没有压缩,就需要大约40GB的磁盘空间。如果你需要在1GBRAM的计算机上使用这个残局库,你就必须对它进行压缩。压缩这类残局库的标准方法是“行程编码”(RLERun-Length Encoding):当你在查找后退式分析所产生的数组时,它看上去会是这样的:
 
....WWWBWWLLDBDBDDDWLBLLLWWBDDD...
 
  这里WLDB代表胜负和坏,坏的意思是局面不合理,使用有间隙的索引,或者不走棋的一方被将军了,这种情况就会发生。要对此进行压缩,我们首先注意到对坏的标志可以任意处理,因为它们没有用,因此我们将它们设定为最方便压缩的值:
 
....WWWWWWLLDDDDDDDWLLLLLWWDDDD...
 
  行程编码存储的就是一对对数值和长度,上面的例子就转换为:
 
(W,6) (L,2) (D,7) (W,1) (L,5) (W,2) (D,4)
 
  如果行程非常长(我没有耐心来造一个行程非常长的例子),那么这种压缩的效果就非常好。8子的西洋跳棋残局库可以压缩到大约4GB,压缩因子是10
 
在搜索中读取数据库
 
  压缩完残局库以后,你必须写一个飞跃式(on-the-fly)的解压缩程序,根据局面找到结果。或许这还不够,如果残局库大到超过你的RAM,你就必须为自己的残局库写一个存储器管理程序。你不会指望Windows(或其他操作系统)来帮你管理残局库,因为你自己写的程序是高效的。管理残局库的通常做法是把压缩的残局库分成一个个几千字节的块(Chunks),如果你需要知道某个局面的结果,就一次读取整个块。从磁盘读取1字节或1千字节是没有差别的,速度只取决于磁盘的寻找时间,而跟传输速度无关。一次读取整个块,就把很多相似的局面装入存储器,这些局面可能是你以后要用到的。一般来说,你会用“最近最少用到”(Least-Recently-Used)的策略,来决定在装入一个块的时候哪个块应该被覆盖掉。即便你用了块,由于磁盘比起存储器来说实在太慢,你无法对所有局面都去查找残局库。通常你只会在第x层以外去读取磁盘上的残局库局面,而在x层以内你只会在存储器中查找这些局面。
 
  原文:http://www.fierz.ch/strategy3.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 其他策略——后台思考
  • 下一篇 其他策略——开局库
  • 返 回 象棋百科全书——电脑象棋
  • www.xqbase.com