《棋战顺序基本手艺》专题
 
残局库
 
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