解剖大象的眼睛——中国象棋程序设计探索(三)：搜索和置换表.htm

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

  face="Times New Roman">Alpha-Beta</FONT>搜索，红色的代码就是超出边界的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索了。如果不使用置换表，那么这种改动和原来没有区别，但是在置换表的作用下，情况就会有微妙的变化。探索置换表的形式<FONT 
  face="Times New Roman">(</FONT>是否超出边界<FONT 
  face="Times New Roman">)</FONT>应该与<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的形式保持一致： 
  <DD>　 
  <DD>int ProbeHash(int Alpha, int Beta, int Depth) { 
  <DD>　…… 
  <DD>　if (Hash.Flag == HASH_BETA) { 
  <DD>　　if (Hash.Value &gt;= Beta) { 
  <DD><FONT color=#0000ff>　　　// return Beta;</FONT> 
  <DD><FONT color=#ff0000>　　　return Hash.Value;</FONT> 
  <DD>　　} 
  <DD>　} else if (Hash.Flag == HASH_ALPHA) { 
  <DD>　　if (Hash.Value &lt;= Alpha) { 
  <DD><FONT color=#0000ff>　　　// return Alpha;</FONT> 
  <DD><FONT color=#ff0000>　　　return Hash.Value;</FONT> 
  <DD>　　} 
  <DD>　} else if (Hash.Flag == HASH_PV) { 
  <DD><FONT color=#0000ff>　　// if (Hash.Value &gt;= Beta) return Beta;</FONT> 
  <DD><FONT color=#0000ff>　　// if (Hash.Value &lt;= Alpha) return Alpha;</FONT> 
  <DD>　　return Hash.Value; 
  <DD>　} 
  <DD>} 
  <DT>　 
  <DT>　　同样的问题出现在记录置换表时： 
  <DD>　 
  <DD>int AlphaBeta(int Alpha, int Beta, int Depth) { 
  <DD>　…… 
  <DD>　while (……) { 
  <DD>　　…… 
  <DD>　　if (Value &gt;= Beta) { 
  <DD><FONT color=#0000ff>　　　// RecordHash(Beta, HASH_BETA, Depth);</FONT> 
  <DD><FONT color=#ff0000>　　　RecordHash(Value, HASH_BETA, Depth);</FONT> 
  <DD>　　　return ……; 
  <DD>　　} 
  <DD>　　…… 
  <DD>　} 
  <DD><FONT color=#0000ff>　// RecordHash(Alpha, HashFlag, Depth);</FONT> 
  <DD><FONT color=#ff0000>　RecordHash(Best, HashFlag, Depth);</FONT> 
  <DD>　return ……; 
  <DD>} 
  <DT>　 
  <DT>　　在带置换表的<FONT face="Times New Roman">Alpha-Beta</FONT>搜索中，到底超出边界<FONT 
  face="Times New Roman">(Fail-Soft)</FONT>和不超出边界<FONT 
  face="Times New Roman">(Fail-Hard)</FONT>哪个效率更高，到现在为止还很难有定论。从上面的代码中可以看出，采用超出边界算法时，置换表的边界变窄了，即<FONT 
  face="Times New Roman">Beta</FONT>结点的可能值从<FONT face="Times New Roman">(Beta, 
  MATE_VALUE</FONT>缩小为<FONT face="Times New Roman">(Value, 
  MATE_VALUE)</FONT>，本来低于<FONT 
  face="Times New Roman">Beta</FONT>才会命中的结点，现在只要低于<FONT 
  face="Times New Roman">Value</FONT>就能命中了。但是很多试验表明，某些局面在使用了超出边界算法时，搜索的结点数反而增加了。因为置换现象会产生搜索的不稳定性，置换表命中率高也会导致不稳定性的增强，搜索的结点数增加就是其中一个表现。 

  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>3.3 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>胜利局面的特殊处理</STRONG></FONT> 
  <DT>　 
  <DT>　　胜利局面就是程序能搜索到的有杀局的局面，它具有特殊的分值——最大值减去“根结点”到“将死结点”的步数<FONT 
  face="Times New Roman">(</FONT>简称杀棋步数或<FONT 
  face="Times New Roman">DTM)</FONT>。而当这个数值记录到置换表的时候，就必须转化为最大值减去“当前结点”到“将死结点”的步数。 

  <DT>　　除此以外杀局还有一个显著的特点——对一个局面进行某一深度的搜索后，如果已经证明它是杀局，那么就不必进行更深层次的搜索了。利用这点，可以改进探索置换表的程序，提高置换表的命中率，从而提高搜索效率： 

  <DD>　 
  <DD>const int WIN_VALUE = MATE_VALUE - 100; 
  <DD>　 
  <DD>int ProbeHash(int Alpha, int Beta, int Depth) { 
  <DD>　…… 
  <DD>　MateNode = false; 
  <DD>　if (Hash.Value &gt; WIN_VALUE) { 
  <DD>　　Hash.Value -= Ply; 
  <DD>　　MateNode = true; 
  <DD>　} else if (Hash.Value &lt; -WIN_VALUE) { 
  <DD>　　Hash.Value += Ply; 
  <DD>　　MateNode = true; 
  <DD>　} 
  <DD>　if (MateNode || Hash.Depth &gt; Depth) { 
  <DD>　　…… 
  <DD>　} 
  <DD>} 
  <DT>　 
  <DT>　　这样做似乎在中局阶段并不能起到很好的效果，但是在处理杀局和残局时，搜索的结点数大幅度降低了，<FONT 
  face="Times New Roman">ElephantEye</FONT>在使用了这种方法以后，杀局和残局的处理能力有了很大的提高。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>3.4 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>长将禁手局面的特殊处理</STRONG></FONT> 
  <DT>　 
  <DT>　　由于单方面长将不变作负的规则，从表面上看，如果发生这种情况就应该，给予<FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">MATE_VALUE</FONT>的值，再根据杀棋步数作调整。但是由于长将判负并不是对某个单纯局面的评分，而是跟路径有关的，所以使用置换表时就会产生非常严重的后果，这也是搜索不稳定性的一个来源。简而言之，即同一局面由于形成路径不同而有不同的分值。 

  <DT><FONT 
  size=3>　　最简单的解决办法就是不要把“利用</FONT>长将判负策略搜索到的局面”记录到置换表中，为此把长将判负的局面定为<FONT 
  face="Times New Roman">BAN_VALUE</FONT>，定义为<FONT 
  face="Times New Roman">MATE_VALUE </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 50</FONT>，再根据杀棋步数作调整。考虑到搜索层数通常不会超过<FONT 
  face="Times New Roman">50</FONT>层，因此如果某个局面分值在<FONT 
  face="Times New Roman">WIN_VALUE(</FONT>即<FONT 
  face="Times New Roman">MATE_VALUE </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 100)</FONT>和<FONT 
  face="Times New Roman">BAN_VALUE</FONT>之间，那么这个局面就是<FONT 
  size=3>“利用</FONT>长将判负策略搜索到的局面”，不记录到置换表中。根据这个思路，代码就应该写成： 
  <DD>　 
  <DD>const int BAN_VALUE = MATE_VALUE - 50; 
  <DD>　 
  <DD>void RecordHash(int HashFlag, int Value, int Depth) { 
  <DD>　if (Value &gt; WIN_VALUE) { 
  <DD>　　if (Ply &gt; 0 &amp;&amp; Value &lt;= BAN_VALUE) { 
  <DD>　　　return; 
  <DD>　　} 
  <DD>　　Value += Ply; 
  <DD>　} else if (Value &lt; -WIN_VALUE) { 
  <DD>　　if (Ply &gt; 0 &amp;&amp; Value &gt;= -BAN_VALUE) { 
  <DD>　　　return; 
  <DD>　　} 
  <DD>　　Value -= Ply; 
  <DD>　} 
  <DD>　…… 
  <DD>} 
  <DT>　 
  <DT>　　之所以允许<FONT face="Times New Roman">Ply == 
  0</FONT>的结点写入置换表，是因为这样的结点是根结点，<FONT 
  face="Times New Roman">ElephantEye</FONT>需要依靠它来获得最佳着法。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>3.5</STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG> 置换表的覆盖策略</STRONG></FONT> 
  <DT>　 
  <DT>　　置换表的覆盖策略通常有两种：深度优先和始终覆盖。<FONT 
  face="Times New Roman">ElephantEye</FONT>以前几个版本只用了深度优先的策略，因此代码并不复杂，并且在搜索时间不太长的情况下，这种策略非常有效。但当置换表接近填满的时候，把深度优先和始终覆盖两种策略结合起来，效果就会很明显了。那么如何把这两种覆盖策略结合起来呢？<FONT 
  face="Times New Roman">ElephantEye</FONT>参考了中国象棋程序“纵马奔流”的做法，采用双层结构的置换表。 
  <DT>　　简单地说，双层置换表的第一层使用了深度优先策略，第二层使用了始终覆盖策略。记录置换表时，如果第一层没能覆盖<FONT 
  face="Times New Roman">(</FONT>因为深度太浅<FONT 
  face="Times New Roman">)</FONT>，那么覆盖第二层；读取置换表时，如果第一层没有命中，那么读取第二层。当然，“纵马奔流”还作了新的尝试，当第一层置换表被覆盖时<FONT 
  face="Times New Roman">(</FONT>由于深度足够<FONT 
  face="Times New Roman">)</FONT>，原来被覆盖的表项就保存到第二层。换句话说，无论深度如何，写入置换表的深度总会和第一层比较，深的留在第一层，浅的被放入第二层。 

  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>就使用这个策略，并且用两个变量<FONT 
  face="Times New Roman">dwHitFirst</FONT>和<FONT 
  face="Times New Roman">dwHitSecond</FONT>来分别说明第一层和第二层置换表的命中结点数。当搜索结点数不多时，第一层命中结点数占绝大多数，但随着搜索深度的增长，搜索结点数不断上升，此时第二层命中结点数多了起来，直到和第一层差不多，这就说明第二层置换表对搜索效率的提高起到了作用。 
  </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_struct.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>二<FONT 
face="Times New Roman">)</FONT>：棋盘结构和着法生成器</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_heuristic.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>