高级搜索方法——简介(一).htm

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

  color=#0000ff>”一文。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>选择性延伸</STRONG></FONT> 
  <DT>　 
  <DT>　　如果局面在前面的路线中非常活跃，那么这就证明后面会有进一步的手段，或者前面的着法使得这些手段推迟了，从而在很深的地方会有好的局面。因此如果搜索到一个“感兴趣”的着法例如吃子或将军，就要增加搜索深度。在<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的伪代码中，调用搜索过程时参数“<FONT 
  face="Times New Roman">depth </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 1</FONT>”可以用“<FONT face="Times New Roman">depth 
  </FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman"> 1 + 
  extension</FONT>”来代替。你必须小心不要经常做这些事，否则最终会把搜索树延伸得特别庞大<FONT 
  face="Times New Roman">(</FONT>甚至可能无限大<FONT face="Times New Roman">)</FONT>。 
  <DT>　　有一个技巧可以使这样的延伸终止，即延伸一个分数的层数。比较好的做法是，“深度”参数记录的是你想要搜索的层数乘上一个因子，比如说“深度 <FONT 
  face="Times New Roman">= </FONT>层数 <FONT face="Times New Roman">x 
  24</FONT>”。在递归调用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的时候，就传递参数“<FONT 
  face="Times New Roman">Depth </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 24 + Extension</FONT>”。如果延伸值总是小于<FONT 
  face="Times New Roman">24</FONT>，那么这个方法能保证终止，这个方法还可以有选择地多延伸些或少延伸些。 
  <DT>　　在评价函数里加上“局面如何难以评价”这个知识，也是有用的，这样就可以在局面太难评价的时候延伸搜索。我的程序就做到了这点，程序对当前结点调用评价函数。如果局面十分复杂，而且深度接近零，那么评价会返回一个特殊的值<FONT 
  color=#0000ff>【表示评价失败，这个值不能在“</FONT><FONT face=Symbol 
  color=#0000ff>-</FONT><FONT face="Times New Roman" 
  color=#0000ff>Infinity</FONT><FONT color=#0000ff>”和“</FONT><FONT 
  face="Times New Roman" color=#0000ff>Infinity</FONT><FONT 
  color=#0000ff>”之间，否则会和正常值混淆】</FONT>，通知搜索继续进行下去。如果深度达到一个负得很大的数<FONT 
  color=#0000ff>【原作者的意思是评价连续失败导致延很长】</FONT>，那么评价函数总是成功的，这样搜索将会终止。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>如何把准确性和重要性结合起来？</STRONG></FONT> 
  <DT>　 
  <DT>　　到目前为止，我们都在讨论并试图找到评价局面可能不准确的原因。但是对于搜索树的一些不重要的部分，或许我们不在乎它不准确，而我们真正关心的是主要变例上的结点。我们如何来关注选择性延伸的重要性呢？ 

  <DT>　　<FONT face="Times New Roman">(1) </FONT>在<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索时，不要只根据准确性作延伸，而忽视了重要性； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>对主要变例部分<FONT 
  face="Times New Roman">(</FONT>或附近<FONT 
  face="Times New Roman">)</FONT>的线路作延伸，例如单步延伸<FONT 
  face="Times New Roman">(Singular Extension)</FONT>，深蓝<FONT 
  face="Times New Roman">(Deep 
  Blue)</FONT>及其前身就用这个方法，如果一个局面的某个着法远比其他着法好，就延伸这个着法。 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>把视线从<FONT 
  face="Times New Roman">Alpha-Beta</FONT>上移开。有一个称为“对策数搜索”<FONT 
  face="Times New Roman">(Conspiracy Number 
  Search)</FONT>的策略，即某些局面会使得能应对的好的着法很少<FONT 
  color=#0000ff>【根据原文，译者也无法了解这个策略的确切含义】</FONT>，这些局面要搜索得深一些。 
  <DT>　　<FONT 
  color=#0000ff>【选择性延伸通常运用在强制着法上，强制着法的界定在各个程序中有所不同，但主要有以下几种判断方法：</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(1) </FONT><FONT color=#0000ff>将军：此时必须应将，显然属于强制着法；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(2) </FONT><FONT 
  color=#0000ff>单一应着：走子的一方只有一种合理着法时，显然属于强制着法；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(3) </FONT><FONT 
  color=#0000ff>杀棋威胁：当一方不走子时就会被对方在几步内杀掉，那么解除杀棋威胁也属于强制着法，这种判断比较困难，通常利用下面所介绍的“空着搜索”来做判断。</FONT> 

  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(4) </FONT><FONT 
  color=#0000ff>吃回被吃棋子：这很有可能是兑子过程，因此大多数情况下为强制着法；</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(5) </FONT><FONT 
  color=#0000ff>通路兵挺进：在王兵残局中，最简单的处理就是搜索到兵升变时的局面，从而绕开正方型法则、关键格理论等知识，这就需要对通路兵的挺进作延伸。</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>如果兵挺</FONT><FONT face="Times New Roman" 
  color=#0000ff>5</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>5</FONT><FONT 
  color=#0000ff>层就能看到了，因为在连续挺兵的这条线路上已经延伸到了</FONT><FONT face="Times New Roman" 
  color=#0000ff>10</FONT><FONT color=#0000ff>层。</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT> 
  <DT><FONT color=#0000ff>　　大多数程序都结合以上若干种判断，以决定是否进行延伸。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>空着搜索</STRONG></FONT> 
  <DT>　 
  <DT>　　这个思想符合本文的整个主题，即在适当时机调整搜索层数，但是它是通过相反的方式来表现的。这个思想不是在复杂的局面上延伸，而是在简单的局面上减少搜索。 

  <DT>　　这个思想是建立在国际象棋知识的基础上的：有害的着子是非常罕见的<FONT 
  face="Times New Roman">(</FONT>除了残局以外<FONT 
  face="Times New Roman">)</FONT>。通常如果轮到你走，你一定能让局面更好些。所有可能的着法都使局面变得更糟，这样的局面称为“无等着”<FONT 
  face="Times New Roman">(Zugzwang)(</FONT>德语，意思为强迫着子<FONT 
  face="Times New Roman">)</FONT>，通常只发生在残局中。像其他棋类，例如五子棋，无等着根本不会发生。因此，如果你改变国际象棋的规则，允许有“弃权”的着法，那么弃权通常是错误的，它不会使棋局有进展。 

  <DT>　　因此，假设你搜索一个希望高出边界的结点<FONT face="Times New Roman">(</FONT>即<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的返回值至少是<FONT 
  face="Times New Roman">Beta)</FONT>，空着搜索就是先搜索“弃权”着法<FONT 
  color=#0000ff>【即“空着”</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Null-Move)</FONT><FONT 
  color=#0000ff>】</FONT>，即使它通常不是最好的。如果弃权着法高出边界，那么真正最好的着法也可能高出边界，你就可以直接返回<FONT 
  face="Times New Roman">Beta</FONT>而不要再去搜索了。要把搜索做得更快，弃权着法搜索的深度通常比常规着法浅。 
  <DT>　　你必须小心，这种启发会改变搜索结果，也可能使你忽略棋局中的一些重要的线路。不要连续两次用空着<FONT 
  face="Times New Roman">(</FONT>因为这样你的搜索会退化，结果只返回评价函数<FONT 
  face="Times New Roman">)</FONT>，而且要小心，只能在不会出现无等着的情况下使用。在国际象棋中，这就意味着当局面还有很多子的时候才能使用。 

  <DT>　 
  <DD>// 带空着启发的Alpha-Beta搜索 
  <DD>alphabeta(int depth, int alpha, int beta) { 
  <DD>　if (赢棋 || depth &lt;= 0) { 
  <DD>　　return score; 
  <DD>　} 
  <DD><FONT color=#ff0000>　放弃着子;</FONT> 
  <DD><FONT color=#ff0000>　if (上一步不是空着 &amp;&amp; 局面不是无等着局面 &amp;&amp;</FONT> 
  <DD><FONT color=#ff0000>　　　alphabeta(depth - 3, beta, beta + 1) &gt;= beta) 
  {</FONT> 
  <DD><FONT color=#ff0000>　　// </FONT><FONT color=#0000ff>【深度参数如果是 depth - 
  1，那就是纯粹的“启发”算法，而现在搜索浅了(depth - 3)，因此称为“空着裁剪”更为恰当。】</FONT> 
  <DD><FONT color=#ff0000>　　return beta;</FONT> 
  <DD><FONT color=#ff0000>　}</FONT> 
  <DD>　/*<FONT color=#0000ff> 
  【“放弃着子”蕴涵着交换着子方的操作，空着启发做完后还必须交换回来。这样，上面用醒目颜色标出的代码(是由译者标出的)就存在一些问题，应该改为：</FONT> 

  <DD>　 
  <DD><FONT color=#0000ff>　if (上一步不是空着 &amp;&amp; 局面不是无等着局面) {</FONT> 
  <DD><FONT color=#0000ff>　　放弃着子;</FONT> 
  <DD><FONT color=#0000ff>　　int val = alphabeta(depth - 3, beta, beta + 
  1);</FONT> 
  <DD><FONT color=#0000ff>　　撤消放弃着子; // 如果只作简单处理，放弃着子和撤消放弃着子都只交换着子方。</FONT> 
  <DD><FONT color=#0000ff>　　if (val &gt;= beta) {</FONT> 
  <DD><FONT color=#0000ff>　　　return beta;</FONT> 
  <DD><FONT color=#0000ff>　　}</FONT> 
  <DD><FONT color=#0000ff>　}</FONT> 
  <DD><FONT color=#0000ff>】 </FONT>*/ 
  <DD>　for (每个可能的着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　alpha = max(alpha, -alphabeta(depth - 1, -beta, -alpha); 
  <DD>　　撤消着法 m; 
  <DD>　　if (alpha &gt;= beta) { 
  <DD>　　　break; 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/990204.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/990204.html</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_hashing.htm">基本搜索方法——置换表</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/advanced_intro2.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>