棋弈软件基础——开局库、哈希表.htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

  <DT>　　根据程序的不同，这种表的类型有多种。首先有残局库哈希表<FONT 
  face="Times New Roman">[</FONT>原注：其实叫做缓存更准确些<FONT 
  face="Times New Roman">]</FONT>，根据<FONT 
  face="Times New Roman">Yace</FONT>的设计者<FONT face="Times New Roman">Dieter 
  Buerssner</FONT>的解释，它是“和磁盘缓存类似的工作原理，避免过多磁盘存取动作，所以在残局后段提高程序的速度。” 
  <DT>　　有些棋弈程序<FONT face="Times New Roman">[</FONT>例如<FONT 
  face="Times New Roman">Goliath]</FONT>除了残局库哈希表之外只有一个主哈希表，而其它<FONT 
  face="Times New Roman">[</FONT>比如<FONT 
  face="Times New Roman">Crafty]</FONT>在主表之外还使用兵结构哈希表。有个棋弈程序<FONT 
  face="Times New Roman">Bringer</FONT>则除了残局库表之外还有三个，分别是兵、估值和局面哈希表。 
  <DT>　 
  <DT>　　<FONT face=Arial><STRONG>C13.</STRONG></FONT><FONT 
  face="Times New Roman"> </FONT><FONT 
  face=黑体><STRONG>那我应该给哈希表分配多少内存空间？</STRONG></FONT> 
  <DT>　　为哈希表分配更多内存空间一般来说提高棋的质量。对于时限较长的对局以及你的<FONT 
  face="Times New Roman">CPU</FONT>较快，哈希表很快被充满，所以设得大些有帮助。但是，如果对局时限很短，设过大的空间非但没有帮助，反而可能降低棋力，因为存在过多的存取动作。即使这些不利没有发生，对于某些引擎<FONT 
  face="Times New Roman">(</FONT>比如某些版本的<FONT 
  face="Times New Roman">Crafty</FONT>，和<FONT 
  face="Times New Roman">Chessmaster8000)</FONT>，它们每走一步棋都清除哈希表，这样对于大型的哈希表来说甚至导致几秒钟的延迟<FONT 
  face="Times New Roman">(</FONT>打了补丁的<FONT 
  face="Times New Roman">Chessmaster8000</FONT>和<FONT 
  face="Times New Roman">Chessmaster9000</FONT>没有这个问题<FONT 
  face="Times New Roman">)</FONT>。如果是下很快的对局，这当然不利。<FONT 
  color=#000080>【译注：严格来说</FONT><FONT face="Times New Roman" 
  color=#000080>Chessmaster8000/9000</FONT><FONT 
  color=#000080>不能说是“引擎”，而应是“软件”，或“程序”也行。但作者假定读者应该对这些基本概念了解清楚了，就没那么严格】</FONT> 
  <DT>　　那么多大才是过大呢？ 
  <DT>　　为<FONT face="Times New Roman">chessbase</FONT>写作的史蒂夫·洛佩兹，他推荐的计算公式是：<FONT 
  face="Times New Roman">2xCPU</FONT>速度<FONT 
  face="Times New Roman">(</FONT>以<FONT 
  face="Times New Roman">Mhz</FONT>数计算<FONT 
  face="Times New Roman">)x</FONT>对局每步平均秒数，得出结果然后除以<FONT 
  face="Times New Roman">1000</FONT>换算成以<FONT 
  face="Times New Roman">M</FONT>数标识的大小，就是你该为哈希表分配的内存空间大小。举例，如果你让引擎走<FONT 
  face="Times New Roman">5</FONT>分钟<FONT 
  face="Times New Roman">40</FONT>步的快棋，使用的<FONT 
  face="Times New Roman">CPU</FONT>速度是 <FONT face="Times New Roman">1 
  Ghz(</FONT>即<FONT 
  face="Times New Roman">1000Mhz)</FONT>，根据公式应该为哈希表分配的内存空间数是＝<FONT 
  face="Times New Roman">2x1000x(5x60/40)=15000 K</FONT>，除以<FONT 
  face="Times New Roman">1000</FONT>换算就是<FONT face="Times New Roman">15M</FONT>。 

  <DT>　　但问题接着来了，这样为每种不同引擎算出的哈希表大小都是相同的，而没有考虑不同引擎每秒钟搜索的速度<FONT 
  color=#000080>【哪怕它们水平相近，搜索速度也可能相差很大的】</FONT>。引擎的搜索以每秒计算多少个“节点”<FONT 
  face="Times New Roman">(Node)</FONT>来衡量。 
  <DT>　　写作<FONT 
  face="Times New Roman">Chessmaster</FONT>的约翰·梅里诺提出另一条公式，哈希表大小＝<FONT 
  face="Times New Roman">2x</FONT>引擎每秒搜索节点数<FONT 
  face="Times New Roman">(NPS)x</FONT>每步平均秒数。 
  <DT>　　尽管这只是他们为<FONT 
  face="Times New Roman">Chessmaster</FONT>而推荐的，但似乎也能很好适应多数引擎，因为这样直接把已搜索节点数与因此而需要的哈希表大小一起衡量。不过，这依然是个粗略建议，我发现它通常比上一个公式得出的结果低，但不清楚是否这才更准确。<FONT 
  color=#000080>【译注：但如果按上两个公式计算，结果都比默认的偏小甚至偏小很多。另外这也与下面的简便设置方法有矛盾，所以只作参考】</FONT> 

  <DT>　　另外，如果你不是让引擎对战引擎，你大可以把哈希表设为你的内存最多一半。剩下的是留给<FONT 
  face="Times New Roman">Windows</FONT>操作系统使用，剩下的不能过小，以免系统本身不够用而出现频繁硬盘存取。如果你让引擎对战引擎，就把它们的哈希表大小之和设为内存的一半。但我必须说明，这是对低内存用户的限制，比方少于<FONT 
  face="Times New Roman">256M</FONT>内存的用户。<FONT 
  face="Times New Roman">Windows</FONT>本身使用的内存资源数都有限定的了，所以如果你拥有大内存，就不必遵守“<FONT 
  face="Times New Roman">50%</FONT>”规则。比方你有<FONT 
  face="Times New Roman">512M</FONT>内存，大概可以设置到总数<FONT 
  face="Times New Roman">420M</FONT>。 
  <DT>　　而如果有同时两种以上哈希表还加上残局库哈希表，那么每种哈希表要分别分配多少内存更难确定。我认为没有绝对的捷径，要通过对不同的引擎一次次的试验和总结经验后确定。 

  <DT>　　我们必须注意到，不同的引擎是不一样的。有些引擎甚至硬性规定了固定大小的哈希表，不能更改。其它的，很多都允许修改大小而且分配可能的任意数值都行。而<FONT 
  face="Times New Roman">Crafty</FONT>则介于两者之间，它允许修改哈希表的大小，但只能是以整数值递增<FONT 
  face="Times New Roman">(</FONT>减<FONT face="Times New Roman">)</FONT>。 
  <DT>　 
  <DT>　　出处：<FONT face="Times New Roman">Aaron's Winboard and Chess Engines 
  FAQ</FONT> 
  <DT>　　译者：<FONT face="Times New Roman">michael</FONT> 
  <DT>　　类型：节译 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/advancedmatch.htm">先进国际象棋</A> 
<LI>下一篇　<A href="http://www.elephantbase.net/computer/egtb.htm">棋弈软件基础——残局库</A> 
<LI>返　回　<A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A> 
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
  <TBODY>
  <TR>
    <TD>
      <P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG 
      height=31 src="棋弈软件基础——开局库、哈希表_files/elephantbase.gif" width=88 
      border=0></A></P></TD></TR>
  <TR>
    <TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial 
      size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>