基本搜索方法——置换表.htm

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

  <DD>　phashe-&gt;best = BestMove(); 
  <DD>　phashe-&gt;val = val; 
  <DD>　phashe-&gt;hashf = hashf; 
  <DD>　phashe-&gt;depth = depth; 
  <DD>} 
  <DD>　 
  <DT>　　你所看到的代码，并不像航天科学一样准确，而是很可能有错误的，而且细节上的问题我还没有讨论。如果你的程序中有错误，或许就是很严重的错误。 
  <DT><FONT color=#0000ff>　　【以上代码有个速度上的瓶颈，即“</FONT><FONT face="Times New Roman" 
  color=#0000ff>ZobristKey() % TableSize()</FONT><FONT 
  color=#0000ff>”这个表达式。由于“电脑一做除法就成了傻瓜”，所以“</FONT><FONT face="Times New Roman" 
  color=#0000ff>TableSize</FONT><FONT color=#0000ff>”最好是一个</FONT><FONT 
  face="Times New Roman" color=#0000ff>2<SUP><EM>n</EM></SUP></FONT><FONT 
  color=#0000ff>的常量，只有当除数是</FONT><FONT face="Times New Roman" 
  color=#0000ff>2<SUP><EM>n</EM></SUP></FONT><FONT 
  color=#0000ff>时除法才可以由右移指令取代。最好的方法是设一个“</FONT><FONT face="Times New Roman" 
  color=#0000ff>TableSizeMask</FONT><FONT color=#0000ff>”的变量：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>int TableSizeMask = TableSize() - 1;</FONT> 
  <DD><FONT color=#0000ff>HASHE *phashe = &amp;hash_table[ZobristKey() &amp; 
  TableSizeMask];</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　而这里“</FONT><FONT face="Times New Roman" 
  color=#0000ff>TableSize()</FONT><FONT color=#0000ff>”也必须是</FONT><FONT 
  face="Times New Roman" color=#0000ff>2<SUP><EM>n</EM></SUP></FONT><FONT 
  color=#0000ff>。正是这个道理，在很多可以设定置换表大小的国际象棋程序中，允许的设定值总是呈倍数增长的，要么是</FONT><FONT 
  face="Times New Roman" color=#0000ff>3M</FONT><FONT 
  color=#0000ff>、</FONT><FONT face="Times New Roman" 
  color=#0000ff>6M</FONT><FONT color=#0000ff>、</FONT><FONT 
  face="Times New Roman" color=#0000ff>12M</FONT><FONT 
  color=#0000ff>、</FONT><FONT face="Times New Roman" 
  color=#0000ff>24M</FONT><FONT color=#0000ff>等等</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>如果每个散列项有</FONT><FONT face="Times New Roman" 
  color=#0000ff>12</FONT><FONT color=#0000ff>字节</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>，要么是</FONT><FONT face="Times New Roman" 
  color=#0000ff>4M</FONT><FONT color=#0000ff>、</FONT><FONT 
  face="Times New Roman" color=#0000ff>8M</FONT><FONT 
  color=#0000ff>、</FONT><FONT face="Times New Roman" 
  color=#0000ff>16M</FONT><FONT color=#0000ff>、</FONT><FONT 
  face="Times New Roman" color=#0000ff>32M</FONT><FONT 
  color=#0000ff>等等</FONT><FONT face="Times New Roman" 
  color=#0000ff>(</FONT><FONT color=#0000ff>如果每个散列项有</FONT><FONT 
  face="Times New Roman" color=#0000ff>16</FONT><FONT 
  color=#0000ff>字节</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　 
  <DT><A name=replacement></A><FONT face=楷体_GB2312 
  size=5><STRONG>替换策略</STRONG></FONT> 
  <DT>　 
  <DT>　　最主要的细节就包括，什么时候该覆盖散列项。在上面的例子中，我用了“始终替换”的策略，即简单地覆盖已经存在的值。这或许不是最好的策略，事实上已经有大量的工作试图找出哪个策略是最好的。 

  <DT>　　另一个策略是“同样深度或更深时替换”。除非新局面的深度大于或等于散列表中已经有的值，否则已经存在的结点将被保留。 
  <DT>　　还有很多试验的余地。<FONT face="Times New Roman">1994</FONT>年我在<FONT 
  face="Times New Roman">Usenet(</FONT>新闻组网络系统<FONT 
  face="Times New Roman">)</FONT>的新闻组<FONT 
  face="Times New Roman">rec.games.chess(</FONT>如今是<FONT 
  face="Times New Roman">rec.games.chess.computer)</FONT>上问了这个问题，得到了<FONT 
  face="Times New Roman">Ken Thompson</FONT>的答复。 
  <DT>　　他的回答是使用两个散列表。一个使用“始终替换”策略，另一个使用“同样深度或更深时替换”。当你做试探时，两个散列表都去试探，如果其中一个可以产生截断，那就可以了。如果两者都不能产生截断，那么你可能至少得到一个最佳着法，实际上更多的可能是得到两个不同的着法，两者都应该首先<FONT 
  face="Times New Roman">(</FONT>或第二个<FONT face="Times New Roman">)</FONT>尝试。 
  <DT>　　记录的时候，你只要简单地根据替换策略来执行。 
  <DT>　　如果你使用“同样深度或更深时替换”的策略，那么你的散列表可能最终会被过期的但很深的结点所占满。解决方案就是每次你走棋时都清除散列表，或者在散列项中加入“顺序”这个域，从而使这个策略变成变成“同样深度，或更深，或原来是旧的搜索，才替换”。 

  <DT>　　我在我的程序<FONT face="Times New Roman">Ferret</FONT>中使用了<FONT 
  face="Times New Roman">Thompson</FONT>的策略，并且运行得很好。另一个程序<FONT 
  face="Times New Roman">Gerbil</FONT>也使用这个策略，你可以去看它的源代码。 
  <DT><FONT color=#0000ff>　　【根据译者研究的结果，只用“深度优先覆盖”策略</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>即“同样深度或更深时替换”</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT 
  color=#0000ff>，效果会比“始终替换”好得多，而代码则并不复杂，只有醒目的部分是新增的：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>void RecordHash(int depth, int val, int hashf) 
  {</FONT> 
  <DD><FONT color=#0000ff>　HASHE *phashe = &amp;hash_table[ZobristKey() &amp; 
  (TableSize() - 1)];</FONT> 
  <DD><FONT color=#ff0000>　if (phashe-&gt;hashf != hashfEMPTY &amp;&amp; 
  phashe-&gt;depth &gt; depth) {</FONT> 
  <DD><FONT color=#ff0000>　　return;</FONT> 
  <DD><FONT color=#ff0000>　}</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;key = ZobristKey();</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;best = BestMove();</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;val = val;</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;hashf = hashf;</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;depth = depth;</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　如果使用这个代码，那么每走一步以前都必须把散列表中所有的标志项置为“</FONT><FONT 
  face="Times New Roman" color=#0000ff>hashfEMPTY</FONT><FONT 
  color=#0000ff>”。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>不稳定性的问题</STRONG></FONT> 
  <DT>　 
  <DT>　　当你用置换表时，如果你允许搜索过程根据散列项来截断，那就会产生另一个问题，你的搜索会受“<A 
  href="http://www.elephantbase.net/computer/advanced_instability.htm" 
  target=_blank>不稳定性</A>”的捆扰。 
  <DT>　　不稳定性至少是由以下因素引起的： 
  <DT>　　<FONT face="Times New Roman">1. </FONT>你可能在做<FONT 
  face="Times New Roman">6</FONT>层的搜索，但是如果你在散列项中得到<FONT 
  face="Times New Roman">10</FONT>层搜索的结果，就可能根据这个值来截断。在后来的搜索中，这个散列项被覆盖了，因此你在这个结点上得到了两个不同的值。 

  <DT>　　<FONT face="Times New Roman">2. 
  Zobrist</FONT>键值无法记录到达结点的线路，这个结点上不是每条线路都有相同结果的。如果某条线路遇到重复局面，那么散列项的值就会跟路线有关。因为重复局面会导致和局的分值，或者至少不一样的分值。 

  <DT>　　就我所知，还没有什么办法能处理这些问题。 
  <DT><FONT color=#0000ff>　　【另外，如果搜索过程中找到杀棋，那么评价值会接近“</FONT><FONT 
  face="Times New Roman" color=#0000ff>INFINITY</FONT><FONT 
  color=#0000ff>”或“</FONT><FONT face=Symbol color=#0000ff>-</FONT><FONT 
  face="Times New Roman" color=#0000ff>INFINITY</FONT><FONT 
  color=#0000ff>”，此时记录散列表时不能简单地记录这些评价值，在后面介绍的“</FONT><A 
  href="http://www.elephantbase.net/computer/other_winning.htm" 
  target=_blank><FONT color=#0000ff>胜利局面</FONT></A><FONT 
  color=#0000ff>”的处理中，会谈到这个问题。】</FONT> 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/hashing.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/hashing.htm</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:[e-mail]"><FONT 
  face="Times New Roman">[e-mail]</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译加译注 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/search_iterative.htm">基本搜索方法——迭代加深</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/advanced_intro1.htm">高级搜索方法——简介<FONT 
face="Times New Roman">(</FONT>一<FONT face="Times New Roman">)</FONT></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>