《国际象棋译文苑》文摘

开局库、哈希表

Aaron Tay

　

　　C1. 什么叫开局库(opening book)

　　就象人们记住开局谱着一样，棋弈程序使用一个数据库，里面储存了开局谱着和局面，于是当对局（开局）中的棋步在开局库中能找到时，它就可以立即取出来走，不用计算。无庸多说，这对于程序节省思考时间有重大帮助。但另一方面，如果开局库本身不好或部分不好，程序也可能被盲目引到劣势的局面甚至很快失利。多数Winboard引擎都可使用开局库，它们绝大部分都是和程序本身分离的独立文件(典型的是以.bk为后缀)，也有少部分是内建在程序里面。【译注：但不同的程序尤其商业性的又有不同的规矩。比如Fritz等的是.ctg后缀；有些是.bok或.book后缀；另外有些程序的开局库下载下来后甚至还要手动更改后缀才能工作！不一而足】

　

　　C2. 什么叫开局学习？(book learning)

　　概念简单，但形式很多样。总的来说，就是使程序从总是导致劣势(失败)的那些重复的开局变化中“吸取经验教训并自行改正”的功能设置。目前还不是很多Winboard引擎有这项功能，只有一些较高的比如Crafty，它不但把结果写入到开局库相关文件，甚至产生一个学习文档反映它究竟“学到了些什么”，使你能与别人交换和引入这些“所学成就”。

　

　　C3. 如何使用开局库？

　　不同引擎不同，但一般都是把开局库文件放在和棋弈引擎文件同一目录下，而且通常还另有一个设置文件(可能是.ini后缀，也可能别的，比如crafty的是.rc，ruffian是.cfg后缀)，在设置文件里把“开局库”(opening book，或者类似这样的表达)设为ON就可以。【译注：当然有些作者喜欢用ON/OFF，有些喜欢用1/0或其它，随他们高兴的】

　

　　C4. 能令所有引擎使用统一的开局库吗？

　　在Fritz等中，可注意到不同的引擎可以使用统一的开局库。但对于Winboard引擎，目前还没有统一的开局库格式，因此不同的引擎有不同格式的开局库。想达到题目要求，有些变通办法，但目前在通用性方面还很欠缺。需等待Winboard的下一个新版协议出来，引入“开局引擎”(book engine)的概念才有通用性。

　　【译注：把C5-C11点转到别的译文或省略；以后不再特别说明】

　

　　C12. 什么叫置换/哈希表(Transposition/Hash tables)

　　当棋弈引擎开始对一个局面进行分析时，它经常是“试验”以不同次序去走但到达同样局面的棋，程序于是把这样的局面以及对局面的评价值保存在内存中，一旦碰到以别的走棋次序但到达同样局面的变化时，换句话说，当计算“另一个”变化但到达的局面其实之前已经出现过时，程序就省下了再次估值的时间了。想详细一点了解，看Dann Corbit在“Winboard论坛”中的发言：

　　哈希表是一种加快搜索的数据结构，它本身的原理模型要一点数学或程序设计基础去理解。(不是想搞棋弈引擎写作的可以不管)

　　哈希表用在棋弈程序中，作用很大。举例，计算如何走棋时，我可能先走马后走车，也可能先走车后走马，假如对手各自相对应的应着不变，那么不同次序走完两步棋后到达的局面是一模一样的。

　　如果我已经对局面进行了计算估计，那很好。如果我对已经计算过了的局面还要再次计算估计那就不好了，如果让电脑这样做，会占用它很多时间的。

　　哈希表的用途就是在这种情况下迅速查找之前已经完成了的工作(已经计算过的估值)。我可以把一个估值加上一个“索引”(hash key)保存在表中，这样做的目的是制造一个“唯一的标识”，而执行过程是很快的。我对当前局面产生一个“索引”，然后看这个索引在表中是否已经有保存了。假如是有，就看表中的值是多少。表中的估值足够深入因此我不需要再次计算了吗？如果是这样，那么我就只需把值从表中取出来，而不用又再来一次计算。这大大节省了时间。

　　哈希表是一种非特殊的数据结构，因此很容易就可作为棋弈程序的其它用途。它对程序的执行速度提高是非常大的，我们认为哈希表是好程序的一个相当必要的功能。

　　根据程序的不同，这种表的类型有多种。首先有残局库哈希表[原注：其实叫做缓存更准确些]，根据Yace的设计者Dieter Buerssner的解释，它是“和磁盘缓存类似的工作原理，避免过多磁盘存取动作，所以在残局后段提高程序的速度。”

　　有些棋弈程序[例如Goliath]除了残局库哈希表之外只有一个主哈希表，而其它[比如Crafty]在主表之外还使用兵结构哈希表。有个棋弈程序Bringer则除了残局库表之外还有三个，分别是兵、估值和局面哈希表。

　

　　C13. 那我应该给哈希表分配多少内存空间？

　　为哈希表分配更多内存空间一般来说提高棋的质量。对于时限较长的对局以及你的CPU较快，哈希表很快被充满，所以设得大些有帮助。但是，如果对局时限很短，设过大的空间非但没有帮助，反而可能降低棋力，因为存在过多的存取动作。即使这些不利没有发生，对于某些引擎(比如某些版本的Crafty，和Chessmaster8000)，它们每走一步棋都清除哈希表，这样对于大型的哈希表来说甚至导致几秒钟的延迟(打了补丁的Chessmaster8000和Chessmaster9000没有这个问题)。如果是下很快的对局，这当然不利。【译注：严格来说Chessmaster8000/9000不能说是“引擎”，而应是“软件”，或“程序”也行。但作者假定读者应该对这些基本概念了解清楚了，就没那么严格】

　　那么多大才是过大呢？

　　为chessbase写作的史蒂夫·洛佩兹，他推荐的计算公式是：2xCPU速度(以Mhz数计算)x对局每步平均秒数，得出结果然后除以1000换算成以M数标识的大小，就是你该为哈希表分配的内存空间大小。举例，如果你让引擎走5分钟40步的快棋，使用的CPU速度是 1 Ghz(即1000Mhz)，根据公式应该为哈希表分配的内存空间数是＝2x1000x(5x60/40)=15000 K，除以1000换算就是15M。

　　但问题接着来了，这样为每种不同引擎算出的哈希表大小都是相同的，而没有考虑不同引擎每秒钟搜索的速度【哪怕它们水平相近，搜索速度也可能相差很大的】。引擎的搜索以每秒计算多少个“节点”(Node)来衡量。

　　写作Chessmaster的约翰·梅里诺提出另一条公式，哈希表大小＝2x引擎每秒搜索节点数(NPS)x每步平均秒数。

　　尽管这只是他们为Chessmaster而推荐的，但似乎也能很好适应多数引擎，因为这样直接把已搜索节点数与因此而需要的哈希表大小一起衡量。不过，这依然是个粗略建议，我发现它通常比上一个公式得出的结果低，但不清楚是否这才更准确。【译注：但如果按上两个公式计算，结果都比默认的偏小甚至偏小很多。另外这也与下面的简便设置方法有矛盾，所以只作参考】

　　另外，如果你不是让引擎对战引擎，你大可以把哈希表设为你的内存最多一半。剩下的是留给Windows操作系统使用，剩下的不能过小，以免系统本身不够用而出现频繁硬盘存取。如果你让引擎对战引擎，就把它们的哈希表大小之和设为内存的一半。但我必须说明，这是对低内存用户的限制，比方少于256M内存的用户。Windows本身使用的内存资源数都有限定的了，所以如果你拥有大内存，就不必遵守“50%”规则。比方你有512M内存，大概可以设置到总数420M。

　　而如果有同时两种以上哈希表还加上残局库哈希表，那么每种哈希表要分别分配多少内存更难确定。我认为没有绝对的捷径，要通过对不同的引擎一次次的试验和总结经验后确定。

　　我们必须注意到，不同的引擎是不一样的。有些引擎甚至硬性规定了固定大小的哈希表，不能更改。其它的，很多都允许修改大小而且分配可能的任意数值都行。而Crafty则介于两者之间，它允许修改哈希表的大小，但只能是以整数值递增(减)。

　

　　出处：Aaron's Winboard and Chess Engines FAQ

　　译者：michael

　　类型：节译