高级搜索方法——空着裁剪.htm

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

  face="Times New Roman">Campbell</FONT>的《空着启发的试验》<FONT 
  face="Times New Roman">(<EM>Experiments with the Null-Move 
  Heuristic</EM>)</FONT>一文，发表在《电脑、象棋与认知》<FONT 
  face="Times New Roman">(<EM>Computers, Chess and Cognition</EM>)(ISBN 
  0-387-97415-6)</FONT>一书中。 
  <DT>　　这个局面轮到白方走，白的下一步就被将死了，而且无能为力。对这个局面做两层的搜索，毫无疑问：<FONT 
  face="Times New Roman">1. &lt;</FONT>任何着法<FONT face="Times New Roman">&gt; 
  Qg2#</FONT>。 
  <DT>　　如果你在这里试图用空着向前裁剪，那么不幸发生了。我们原来打算做两层的完全搜索，现在要做的是对对方做零层搜索，并试图找到威胁。在零层搜索中，黑方不走子，所以调用“评价”函数，由于白方领先一个车而返回 
  <FONT face="Times New Roman">+5 </FONT>左右。这或许会大于<FONT 
  face="Times New Roman">Beta</FONT>，因此搜索返回<FONT 
  face="Times New Roman">Beta</FONT>。 
  <DT>　　这是我们不希望发生的！搜索应该返回一个很小的值，表示白方被杀。 
  <DT>　　我们这里看到的是一种水平线效应，经常发生在启用空着向前裁剪的时候。没有空着向前裁剪时，白方走了一步没用的着法，然后有足够的搜索深度<FONT 
  face="Times New Roman">(</FONT>在这个例子中只需要一层<FONT 
  face="Times New Roman">)</FONT>让黑杀掉白。用了空着向前裁剪并且用一个足够高的<FONT 
  face="Times New Roman"><EM>R</EM></FONT>值<FONT 
  face="Times New Roman">(</FONT>例如<FONT face="Times New Roman"><EM>R</EM> = 
  2)</FONT>，白方不做任何事情，但是黑方也没有足够深度来看到胜利了。 
  <DT>　　这个例子或许让你感到奇怪，或许它只会在很浅的搜索中才发生，但是有很多例子在足够的搜索深度下仍然会发生这样的事，即用正常的搜索可以看到的棋，用了空着向前裁剪后就被忽视了。实际上，这个黑后在<FONT 
  face="Times New Roman">h3</FONT>格并且黑兵在<FONT 
  face="Times New Roman">f3</FONT>格的棋型，对于国际象棋程序来说都是很危险的。<FONT 
  color=#0000ff>【原作者的意思是，如果程序遇到这种棋型，应该考虑适当延伸搜索深度，或者用更小的</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>R</EM></FONT><FONT 
  color=#0000ff>值做空着裁剪。】</FONT> 
  <DT>　　空着向前裁剪的另一个问题在于它会导致“<A 
  href="http://www.elephantbase.net/computer/advanced_instability.htm" 
  target=_blank>搜索的不稳定性</A>”。空着搜索的成功与否取决于<FONT 
  face="Times New Roman">Beta</FONT>的值。这个结点下次访问时，<FONT 
  face="Times New Roman">Beta</FONT>可能不同，因此搜索会有不同的值，这是很不合理的。你可能在传递窗口<FONT 
  face="Times New Roman">(7, 30)</FONT>时搜索高出边界，但是传递<FONT 
  face="Times New Roman">(7, 50)</FONT>时，却低出边界。 
  <DT>　　在实战中，比起遇到偶然的对策错误，以及搜索不稳定性的增加来说，搜索速度的加快重要得多。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>一些思想</STRONG></FONT> 
  <DT>　 
  <DT>　　尝试调整一个不同于<FONT face="Times New Roman">2</FONT>的<FONT 
  face="Times New Roman"><EM>R</EM></FONT>值，这是非常有趣的事。你可以试试<FONT 
  face="Times New Roman">1</FONT>、<FONT face="Times New Roman">3</FONT>、<FONT 
  face="Times New Roman">4</FONT>或更大的数，或者根据搜索深度、棋盘上的子力等等因素改变。我从来没有得到比直接用<FONT 
  face="Times New Roman"><EM>R</EM> = 
  2</FONT>更好的结果，但是一些研究表明其他值或许会更好，而且有些人至少在搜索树的部分结点上用<FONT 
  face="Times New Roman"><EM>R</EM> = 3</FONT>的。 
  <DT>　　通过一些验证式的搜索，我们也可以试图找到残局中使用空着向前裁剪的方法。如果你的空着搜索高出边界，你就减少深度来做常规搜索，看它是否也高出边界。我觉得这看上去有些破费，但是还是值得尝试的。 

  <DT>　　还有其他的改进方法值得尝试，但是我不想把它们一一列举出来。你可以去看<FONT 
  face="Times New Roman">Donninger</FONT>的文章，看《电脑、象棋与认知》<FONT 
  face="Times New Roman">(<EM>Computers, Chess and 
  Cognition</EM>)</FONT>的文章，或者看<FONT face="Times New Roman">Ernst 
  Heinz</FONT>的跟空着向前裁剪有关的文章。 
  <DT><FONT color=#0000ff>　　【译者有必要在这里介绍一下这两个思想：</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(1) </FONT><FONT color=#0000ff>根据不同情况来调整</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>R</EM></FONT><FONT 
  color=#0000ff>值的做法，称为“适应性空着裁剪”</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Adaptive Null-Move Pruning)</FONT><FONT 
  color=#0000ff>，它首先由</FONT><FONT face="Times New Roman" color=#0000ff>Ernst 
  Heinz</FONT><FONT color=#0000ff>发表在</FONT><FONT face="Times New Roman" 
  color=#0000ff>1999</FONT><FONT color=#0000ff>年的</FONT><FONT 
  face="Times New Roman" color=#0000ff>ICCA</FONT><FONT 
  color=#0000ff>杂志上。其内容可以概括为：</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>a. 
  </FONT><FONT color=#0000ff>深度小于或等于</FONT><FONT face="Times New Roman" 
  color=#0000ff>6</FONT><FONT color=#0000ff>时，用</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>R</EM> = 2</FONT><FONT 
  color=#0000ff>的空着裁剪进行搜索；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>b. 
  </FONT><FONT color=#0000ff>深度大于</FONT><FONT face="Times New Roman" 
  color=#0000ff>8</FONT><FONT color=#0000ff>时，用</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>R</EM> = 3</FONT><FONT 
  color=#0000ff>；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>c. 
  </FONT><FONT color=#0000ff>深度是</FONT><FONT face="Times New Roman" 
  color=#0000ff>6</FONT><FONT color=#0000ff>或</FONT><FONT face="Times New Roman" 
  color=#0000ff>7</FONT><FONT color=#0000ff>时，如果每方棋子都大于或等于</FONT><FONT 
  face="Times New Roman" color=#0000ff>3</FONT><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><FONT 
  face="Times New Roman" color=#0000ff><EM>R</EM> = 3</FONT><FONT 
  color=#0000ff>，否则用 </FONT><FONT face="Times New Roman" 
  color=#0000ff><EM>R</EM> = 2</FONT><FONT color=#0000ff>。</FONT> 
  <DT><FONT color=#0000ff>　　参阅：</FONT><FONT face="Times New Roman" 
  color=#0000ff>Heinz EA: <EM><STRONG>Adaptive Null-Move 
  Pruning</STRONG></EM><EM>, ICCA J.</EM> 22 (3): 123-132, 
  <STRONG>1999</STRONG></FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(2) </FONT><FONT 
  color=#0000ff>验证空着裁剪是否安全的做法，称为“带验证的空着裁剪”</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Verified Null-Move Pruning)</FONT><FONT 
  color=#0000ff>，它首先由</FONT><FONT face="Times New Roman" 
  color=#0000ff>Tabibi</FONT><FONT color=#0000ff>发表在</FONT><FONT 
  face="Times New Roman" color=#0000ff>2002</FONT><FONT 
  color=#0000ff>年的</FONT><FONT face="Times New Roman" 
  color=#0000ff>ICGA(</FONT><FONT color=#0000ff>原</FONT><FONT 
  face="Times New Roman" color=#0000ff>ICCA)</FONT><FONT 
  color=#0000ff>杂志上。其内容可以概括为：</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>a. 
  </FONT><FONT color=#0000ff>用</FONT><FONT face="Times New Roman" 
  color=#0000ff><EM>R</EM> = 3</FONT><FONT color=#0000ff>的空着裁剪进行搜索；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>b. 
  </FONT><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> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>c. 
  </FONT><FONT color=#0000ff>做浅一层的搜索时，子结点用</FONT><FONT face="Times New Roman" 
  color=#0000ff><EM>R</EM> = 3</FONT><FONT color=#0000ff>的不带验证的空着裁剪；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" color=#0000ff>d. 
  </FONT><FONT color=#0000ff>如果浅一层的搜索高出边界，那么带验证的空着裁剪是成功的，否则必须重新做完全的搜索。</FONT> 
  <DT><FONT color=#0000ff>　　参阅：</FONT><FONT face="Times New Roman" 
  color=#0000ff>Tabibi OD, Netanyahu NS: <EM><STRONG>Verified Null-Move 
  Pruning</STRONG></EM><EM>, ICGA J.</EM> 25 (3): 153-161, 
  <STRONG>2002</STRONG></FONT><FONT color=#0000ff>】</FONT> 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/nullmove.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/nullmove.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/advanced_quiescent.htm">高级搜索方法——静态搜索</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/advanced_aspiration.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>