《国际象棋译文苑》文摘

残局库、哈希表

Aaron Tay
 
  C1. 甚么叫残局库(opening book)
  就象人们记住残局谱着一样,棋弈顺序运用一个数据库,外面贮存了残局谱着和局势,因而当对局(残局)中的棋步在残局库中能找到时,它就能够够马上掏出来走,不用盘算。毋庸多说,这关于顺序节约思索时刻有严重资助。但其余一方面,若是残局库自身欠好或局部欠好,顺序也能够被自觉引到优势的局势以至很快失利。少数Winboard引擎都可运用残局库,它们绝大局部都是和顺序本因素离的自力文件(模范的是以.bk为后缀),也有少局部是内建在顺序外面。【译注:但分歧的顺序稀奇商业性的又有分歧的礼貌。例如Fritz等的是.ctg后缀;很多若干是.bok.book后缀;其余很多若干顺序的残局库下载上去后以至还要手动更改后缀才气事情!所在多有】
 
  C2. 甚么叫残局学习?(book learning)
  观点简朴,但形式许多样。总的来说,就是使顺序从总是致使优势(失利)的那些一次又一次的残局转变中“吸收心得经验并自己纠正”的功用设置。现在还不是许多Winboard引擎有这项功用,只需一些较高的例如Crafty,它不只把效果写入到残局库相关文件,以至发生一个学习文档回响反映它终究“学到了些甚么”,使你能与他人交流和引入这些“所学结果”。
 
  C3. 怎样运用残局库?
  分歧引擎分歧,但一样寻常都是把残局库文件放在和棋弈引擎文件统一目录下,而且一般还尚有一个设置文件(多是.ini后缀,也能够其余,例如crafty的是.rcruffian.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),它们每走一步棋都消灭哈希表,这样关于大型的哈希表来说以至致使几秒钟的延迟(打了补钉的Chessmaster8000Chessmaster9000没有这个问题)。若是是下很快的对局,这固然晦气。【译注:严厉来说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
  类型:节译
  • 上一篇 先进国际象棋
  • 下一篇 棋弈软件根蒂基本——残局库
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com