⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 高级搜索方法——静态搜索.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0059)http://www.elephantbase.net/computer/advanced_quiescent.htm -->
<HTML><HEAD><TITLE>高级搜索方法——静态搜索</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=高级搜索方法——静态搜索_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隶书 size=6>静态搜索</FONT> </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">Bruce Moreland (</FONT><A 
  href="mailto:brucemo@seanet.com"><FONT 
  face="Times New Roman">brucemo@seanet.com</FONT></A><FONT 
  face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
  <DT>　 
  <DT>　　国际象棋中会有很多强制的应对。如果有人用马吃掉你的象，那么你最好吃还他的马。 
  <DT>　　<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索不是特别针对这种情况的。你把深度参数传递给函数，当深度到达零就做完了，即使一方的后被捉。 

  <DT>　　一个应对的方法称为“静态搜索”<FONT face="Times New Roman">(Quiescent 
  Search)</FONT>。当<FONT 
  face="Times New Roman">Alpha-Beta</FONT>用尽深度后，通过调用静态搜索来代替调用“<FONT 
  face="Times New Roman">Evaluate()</FONT>”。这个函数也对局面作评价，只是避免了在明显有对策的情况下看错局势。 
  <DT>　　简而言之，静态搜索就是应对可能的动态局面的搜索。 
  <DT>　　典型的静态搜索只搜索吃子着法。这会引发一个问题，因为在国际象棋中吃子通常不是强制的。如果局势很平静，而且你面对的吃子只有<FONT 
  face="Times New Roman">QxP(</FONT>后吃兵，导致丢后<FONT 
  face="Times New Roman">)</FONT>，你不会强迫后去吃兵的，所以静态搜索不应该强迫吃子。 
  <DT>　　因此，走子一方可以选择是吃子还是不吃子。这就好比打扑克牌时可以只用手中的牌而不去抓牌<FONT 
  color=#0000ff>【译注：术语“</FONT><FONT face="Times New Roman" 
  color=#0000ff>Standing Pat</FONT><FONT color=#0000ff>”】</FONT>。 
  <DT>　　代码如下： 
  <DD>　 
  <DD>int Quies(int alpha, int beta) { 
  <DD>　val = Evaluate(); 
  <DD>　if (val &gt;= beta) { 
  <DD>　　return beta; 
  <DD>　} 
  <DD>　if (val &gt; alpha) { 
  <DD>　　alpha = val; 
  <DD>　} 
  <DD>　GenerateGoodCaptures(); 
  <DD>　while (CapturesLeft()) { 
  <DD>　　MakeNextCapture(); 
  <DD>　　val = -Quies(-beta, -alpha); 
  <DD>　　UnmakeMove(); 
  <DD>　　if (val &gt;= beta) { 
  <DD>　　　return beta; 
  <DD>　　} 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DD>　 
  <DT><FONT size=3>　　这看上去和“</FONT><A 
  href="http://www.elephantbase.net/computer/search_alphabeta.htm" 
  target=_blank><FONT face="Times New Roman" size=3>Alpha-Beta</FONT></A><FONT 
  size=3>”非常相似，但是区别是很明显的。这个函数调用静态评价，如果评价好得足以截断而不需要试图吃子时，就马上截断</FONT><FONT 
  face="Times New Roman" size=3>(</FONT><FONT size=3>返回</FONT><FONT 
  face="Times New Roman" size=3>Beta)</FONT><FONT 
  size=3>。如果评价不足以产生截断，但是比</FONT><FONT face="Times New Roman" 
  size=3>Alpha</FONT><FONT size=3>好，那么就更新</FONT><FONT face="Times New Roman" 
  size=3>Alpha</FONT><FONT size=3>来反映静态评价。</FONT> 
  <DT>　　然后尝试吃子着法，如果其中任何一个产生截断，搜索就中止。可能它们没有一个是好的，这也没问题。 
  <DT>　　这个函数有几个可能的结果：可能评价函数会返回足够高的数值，使得函数通过<FONT 
  face="Times New Roman">Beta</FONT>截断马上返回；也可能某个吃子产生<FONT 
  face="Times New Roman">Beta</FONT>截断；可能静态评价比较坏，而任何吃子着法也不会更好；或者可能任何吃子都不好，但是静态评价只比<FONT 
  face="Times New Roman">Alpha</FONT>高一点点。 
  <DT>　　注意这里静态搜索中没有传递“深度”这个参数。正因为如此，如果找到好的吃子，或者有一系列连续的强制性吃子的着法，那么搜索可能会非常深。 
  <DT>　　我的示范程序不检测将军，因此它不能找到杀棋。先询问要走的一方是否被将军，这是可以尝试的做法。如果被将军了，就不能用“<FONT 
  face="Times New Roman">Evaluate()</FONT>”来尝试截断，而应该以一层的深度调用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>。例如： 
  <DD>　 
  <DD>int Quies(int alpha, int beta) { 
  <DD>　if (InCheck()) { 
  <DD>　　return AlphaBeta(1, alpha, beta); 
  <DD>　} 
  <DD>　val = Evaluate(); 
  <DD>　if (val &gt;= beta) { 
  <DD>　　return beta; 
  <DD>　} 
  <DD>　if (val &gt; alpha) { 
  <DD>　　alpha = val; 
  <DD>　} 
  <DD>　GenerateGoodCaptures(); 
  <DD>　while (CapturesLeft()) { 
  <DD>　　MakeNextCapture(); 
  <DD>　　val = -Quies(-beta, -alpha); 
  <DD>　　UnmakeMove(); 
  <DD>　　if (val &gt;= beta) { 
  <DD>　　　return beta; 
  <DD>　　} 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　这个版本会找到带有连续吃子的杀棋。至于用哪个版本，取决于个人喜好和测试结果。 
  <DT>　　“好的”吃子的界定也是仁者见仁智者见智的。如果你允许任何吃子，并且以任何原始的顺序来搜索，那么你会降低搜索效率，并且导致静态搜索的膨胀，从而大幅度降低搜索深度，并使程序崩溃。 

  <DT>　　有一些简单的做法可以避免静态搜索的膨胀。 
  <DT>　 
  <DT><A name=MVVLVA></A><FONT face=Arial size=5><STRONG>MVV/LVA</STRONG></FONT> 

  <DT>　 
  <DT>　　<FONT face="Times New Roman">MVV/LVA </FONT>意思是“最有价值的受害者<FONT 
  face="Times New Roman">/</FONT>最没价值的攻击者”<FONT face="Times New Roman">(Most 
  Valuable Victim/Least Valuable 
  Attacker)</FONT>。这是一个应用上非常简单的着法排序技巧，从而最先搜索最好的吃子着法。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子，那么假设用最小的子去吃是最好的。 

  <DT>　　这就意味者<FONT face="Times New Roman">PxQ(</FONT>兵吃后<FONT 
  face="Times New Roman">)</FONT>首先考虑<FONT 
  face="Times New Roman">(</FONT>假设王的将军另外处理<FONT 
  face="Times New Roman">)</FONT>。接下来是<FONT 
  face="Times New Roman">NxQ</FONT>或<FONT 
  face="Times New Roman">BxQ</FONT>，然后是<FONT 
  face="Times New Roman">RxQ</FONT>、<FONT 
  face="Times New Roman">QxQ</FONT>、<FONT 
  face="Times New Roman">KxQ</FONT>。接下来是<FONT 
  face="Times New Roman">PxR</FONT>、<FONT 
  face="Times New Roman">B/NxR</FONT>、<FONT 
  face="Times New Roman">RxR</FONT>、<FONT 
  face="Times New Roman">QxR</FONT>、<FONT face="Times New Roman">KxR</FONT>，等等。 
  <DT>　　这个工作总比不做要好，但是很明显有很严重的问题。即使车被保护着，<FONT 
  face="Times New Roman">RxR</FONT>仍旧排在<FONT 
  face="Times New Roman">PxB</FONT>的前面。 
  <DT>　　<FONT face="Times New Roman">MVV/LVA 
  </FONT>可以解决静态搜索膨胀的问题，但是它仍然留给你比较庞大的静态搜索树。 
  <DT>　　<FONT face="Times New Roman">MVV/LVA 
  </FONT>的优势在于它实现起来非常方便，而且可以达到很高的<FONT face="Times New Roman">NPS</FONT>值<FONT 
  face="Times New Roman">(</FONT>每秒搜索的结点数<FONT 
  face="Times New Roman">)</FONT>。它的缺点是搜索效率低——你花大量的时间来评估吃亏的吃子，所以你的搜索不会很深。 
  <DT>　 
  <DT><A name=SEE></A><FONT face=Arial size=5><STRONG>SEE</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">SEE </FONT>意思是“静态交换评价”<FONT 
  face="Times New Roman">(Static Exchange Evaluation)</FONT>。它比 <FONT 
  face="Times New Roman">MVV/LVA </FONT>更复杂，但是着法排序更准确，从而很多吃子都不必考虑。 
  <DT>　　在 <FONT face="Times New Roman">MVV/LVA </FONT>中你无法去掉<FONT 
  face="Times New Roman">QxP</FONT>的着法，因为很可能兵是没保护的，这就意味着<FONT 
  face="Times New Roman">QxP</FONT>是好的着法。当然，如果兵是保护的，我不相信你还能在搜索这步时有什么好的发现。用了 
  <FONT face="Times New Roman">SEE </FONT>后，如果<FONT 
  face="Times New Roman">QxP</FONT>是吃亏的着法，你就可以把它挑出来，然后在吃子的顺序里把它排在最后，或简单地把它裁剪掉。 
  <DT>　　现在我还没有 <FONT face="Times New Roman">SEE 
  </FONT>的示范代码，你可以设计一个处理吃子的过程，然后根据它看上去能得到的价值进行排序。<FONT 
  color=#0000ff>【当考虑吃子着法时，需要考虑能吃到的该子的所有攻击子，也要保护该子的所有防守子，因此处理吃子的过程是相当复杂的。】</FONT> 

  <DT>　　<FONT face="Times New Roman">SEE 
  </FONT>能让你非常有效地裁剪掉坏的着法，很多重要的吃子不会被错误地裁剪，并且能改进着法的顺序。你能做的另一件事是，如果着法看起来还不算充分好，那么你可以裁剪掉这些好的着法。如果你领先一个车，那么得一个兵的吃子或许不值得在静态搜索中尝试。 

  <DT>　　我很怀疑用 <FONT face="Times New Roman">SEE </FONT>的程序能比相同的但用了 <FONT 
  face="Times New Roman">MVV/LVA </FONT>的程序强。问题在于代码的编写上，需要很好地设计数据结构，才能让 <FONT 
  face="Times New Roman">SEE </FONT>变得有效。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>静态搜索不是完美的</STRONG></FONT> 
  <DT>　 
  <DT>　　静态搜索极有可能会犯错误。这是一个不幸的现实，但是它更多地在搜索看上去非常愚蠢<FONT 
  face="Times New Roman">(</FONT>例如一层的搜索，它根本不会是非常好的<FONT 
  face="Times New Roman">)</FONT>的情况下会犯错误，因此这不是一个严重的问题。 
  <DT>　　如果可能用更准确的静态搜索而不降低速度，那么我肯定这个程序会比以前更强。但是我们必须明白的是，你在耗费时间的前提下试图让静态搜索更准确，需要找到平衡点。如果为了让静态搜索更聪明，你花费了几层完全搜索的时间，那么这就不值得让它更聪明了。 

  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/quiescent.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/quiescent.htm</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译加译注 </DT></DL>
<DIR>
<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/advanced_nullmove.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>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -