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

　

残局库

　

Martin Fierz */ 文

* 瑞士Windisch应用科学学院(Aargau学院)

　

简介

　

　　残局库在很多棋类游戏中扮演着非常重要的角色，例如九人Morris，Awari和西洋跳棋(Checkers)(其中九人Morris已经完全可解了，这要归功于残局库的使用)。在其他棋类中，残局库就不那么重要了(例如国际象棋)，而某些棋类制作残局库是不现实的(如连四子棋、黑白棋和围棋)。你是否已经发现这些棋类的差异了？通常只有在盘面上棋子数量很少的情况下，残局库才能实现。适用残局库有个确切的棋子数量的界限，它取决于棋类的复杂性。有些棋类随着对局的进行，棋子数量是减少的，那么残局库就是可行的；而有些棋类的棋子数量是增加的或者不变的，那么残局库就是无法计算的(除非棋类异常简单)，无论如何残局库取决于具体的棋类。例如在国际象棋中，有多达6子的残局库(王车兵对王车兵等)，而这种残局(包括其他不超过6子的残局)在实战中不是经常出现的，因此残局库对棋力的影响并不是很大。而在(盎格鲁-萨克森式的)西洋跳棋里，有多达8子的残局库，而10子的残局库也已经在计算了，这就意味着在有吃必吃的规则下，很多棋局会很快走到有残局库的局面中，因此残局库使得西洋跳棋的棋力有了很大的提高。要让某种棋类完全可解，通常总是要借助于残局库的——从起始局面开始向前搜索，结合残局库，就能解出这盘棋。Gasser用这种办法解决了九人Morris，而Chinook(最著名的西洋跳棋程序)的小组正在用这个方法解西洋棋。

　

残局库的不同类型

　

　　残局库有不同的类型，而它们都可以知道残局库中某个特定的局面是赢棋、是输棋还是和棋。如果这就是残局库包含的所有信息，就称为“胜负和”(WLD)残局库；如果知道多少步以后棋局会结束，就称为“杀棋步数”(DTM，Distance-to-Mate)残局库；如果只知道多少步以后会转换为另一种类型的局面，就称为“转换步数”(DTC，Distance-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)的索引。有间隙的索引往往更简单，因为构造一个有间隙的索引函数要比无间隙的索引函数简单得多。后退式分析需要的存储器跟索引号的最大值成正比，因此如果构造了一个M比N大得多的索引函数，那么你会浪费很多存储器。

　　一旦有了索引函数，后退式分析算法就只要做以下几件事：

　

　　(1) 初始化：生成两个长度都为N的数组，分别存放结果(WIN/LOSS/DRAW，代表胜负和)和DTC。把所有的结果都设成UNKNOWN(代表未知)，所有的DTC计数器都设成0。你会发现，你需要4个数来表示结果，因此数组的数据类型是4个值的数(即2位)。当然，还有些根本不存在的局面，你需要自行处理。

　　(2) 杀棋遍历：逐一检查每个局面是否是杀棋局面，如果是的，就把这个局面的结果设成LOSS，表示即将走的一方输了。如果棋类允许“逼和”的存在，也必须作逼和的检查，并赋值为DRAW。把每个UNKNOWN局面的DTC计数器加1。

　　(3) 对每个UNKNOWN的局面，生成所有后续局面并看它们都有哪些结果。只要其中有一个后续局面是LOSS，就把这个局面设成WIN。如果所有后续局面都是WIN，就把这个局面设成LOSS。如果你遍历了所有局面但没有一个局面能设WIN或LOSS的，就跳到第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，白车在a2”【8/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位，而整个局面需要用大量存储器来描述。如果你存储整个局面，你就会浪费大量的存储器。用了索引函数以后，你就能够简单地用一个数字来代表局面了，你不需要把结果和索引数字都记下来，而只需要以索引数字为数组的指标，只在数组中存储结果。那么如何才能找到符合上述性质的索引函数呢？看上去这是个很吓人的工作，实际上用简单的方法来构造索引函数是可行的。对于棋子各不相同的残局(例如白王、白车和黑王)，就非常简单，把格子标号为0到63，就可以写下这样的公式：

　

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;

　

　　剩下来的问题就是由车的具体位置来计算“组合的车的索引”了，它是0到64 × 63 / 2 - 1之间的数。用r₁和r₂表示两个车的位置，并且r₁ < r₂(这样就等同于除以2了!)。我们有：

　

combinedindex = bicoef(r1, 1) + bicoef(r2, 2);

　

　　这里bicoef(x, y)代表x和y(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的磁盘空间。如果你需要在1GB的RAM的计算机上使用这个残局库，你就必须对它进行压缩。压缩这类残局库的标准方法是“行程编码”(RLE，Run-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