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

📄 基本搜索方法——简介(二).htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
  face="Times New Roman">Alpha = </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">Infinity</FONT>，<FONT face="Times New Roman">Beta = 
  Infinity(</FONT>无穷大<FONT face="Times New Roman">)</FONT>。 
  <DT>　　但是，如果我们使用迭代加深，就可能有办法知道主要变例是怎么样的。假设我们猜其值为<FONT 
  face="Times New Roman"><EM>x</EM>(</FONT>例如<FONT 
  face="Times New Roman"><EM>x</EM></FONT>就是前一次搜索到<FONT 
  face="Times New Roman"><EM>D</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">1</FONT>深度时的值<FONT 
  face="Times New Roman">)</FONT>，并设<FONT 
  face="Times New Roman">Epsilon</FONT>为一个很小的值，它代表从<FONT 
  face="Times New Roman"><EM>D</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">1</FONT>深度到<FONT 
  face="Times New Roman"><EM>D</EM></FONT>深度搜索评价的期望变化范围。我们可以尝试调用<FONT 
  face="Times New Roman">alphabeta(<EM>D</EM>, <EM>x</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> Epsilon, <EM>x</EM> + 
  Epsilon)</FONT>，那么可能发生三种情况： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>搜索的返回值会落在区间<FONT 
  face="Times New Roman">(<EM>x</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> Epsilon, <EM>x</EM> + 
  Epsilon)</FONT>内。这种情况下，我们知道它返回的是正确值，我们就能放心地选择这个着法，在搜索树中这个着法指向具有返回值的那个结点。 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>搜索会返回一个值<FONT 
  face="Times New Roman"><EM>v</EM> <U>&gt;</U></FONT>&nbsp;<FONT 
  face="Times New Roman"><EM>x</EM> + 
  Epsilon</FONT>。这种情况下，我们知道搜索结果也至少是&nbsp;<FONT face="Times New Roman"><EM>x</EM> 
  + Epsilon</FONT>，但是我们不知道它到底是几<FONT 
  face="Times New Roman">(</FONT>正确的主要变例可能被裁剪掉了，因为我们看到有别的着法的值大于<FONT 
  face="Times New Roman">Beta)</FONT>。我们必须把我们所猜的值<FONT 
  face="Times New Roman"><EM>x</EM></FONT>调整得更高，然后再试一次<FONT 
  face="Times New Roman">(</FONT>可能还要用更大的<FONT 
  face="Times New Roman">Epsilon)</FONT>。这种情况称为“高出边界”<FONT 
  face="Times New Roman">(Fail High)</FONT>。 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>搜索会返回一个值<FONT 
  face="Times New Roman"><EM>v</EM> <U>&lt;</U></FONT>&nbsp;<FONT 
  face="Times New Roman"><EM>x</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> Epsilon</FONT>。这种情况下，我们知道搜索结果也最多是&nbsp;<FONT 
  face="Times New Roman"><EM>x</EM> + 
  Epsilon</FONT>，但是我们不知道它到底是几。我们必须把我们所猜的值<FONT 
  face="Times New Roman"><EM>x</EM></FONT>调整得更低，然后再试一次<FONT 
  face="Times New Roman">(</FONT>可能还要用更大的<FONT 
  face="Times New Roman">Epsilon)</FONT>。这种情况称为“低出边界”<FONT 
  face="Times New Roman">(Fail Low)</FONT>。 
  <DT>　　即便有两种可能失败的情况，使用期望搜索<FONT face="Times New Roman">(</FONT>用一个比<FONT 
  face="Times New Roman">(</FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">Infinity, Infinity)</FONT>更小的区间<FONT 
  face="Times New Roman">(Alpha, Beta))</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">Beta</FONT>情况的分析”，即假设任何可能的情况下都会发生<FONT 
  face="Times New Roman">Alpha-Beta</FONT>裁剪。下一次我们会知道如何让<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索接近我们的所分析的情况。在这里我只考虑浅的裁剪，因为它会让分析变得更加简单。 

  <DT>　　在最好的情况下，除了主要变例上的结点不会裁剪外<FONT 
  face="Times New Roman">(</FONT>如果这个结点也被裁剪了，那么整个算法会高出边界或低出边界，这当然不是最好的情况<FONT 
  face="Times New Roman">)</FONT>，在裁剪前，深<FONT face="Times New Roman"><EM>D 
  </EM></FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">1</FONT>层的每个结点只会搜索一个深<FONT 
  face="Times New Roman"><EM>D</EM></FONT>层的子结点。 
  <DT>　　但是在深<FONT face="Times New Roman"><EM>D </EM></FONT><FONT 
  face=Symbol>-</FONT><FONT 
  face="Times New Roman">2</FONT>层时，谁也没有被裁剪，因为所有的子结点都返回大于或等于<FONT 
  face="Times New Roman">Beta</FONT>的值，而<FONT face="Times New Roman"><EM>D</EM> 
  </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">2</FONT>层是要取负数，因此它们都小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>。 
  <DT>　　继续朝树根走，<FONT face="Times New Roman"><EM>D </EM></FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman">3</FONT>层的每个结点<FONT 
  face="Times New Roman">(</FONT>除了主要变例外<FONT 
  face="Times New Roman">)</FONT>都被裁剪，而<FONT face="Times New Roman"><EM>D</EM> 
  </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">4</FONT>层谁也没被裁剪，等等。 
  <DT>　　因此，如果搜索树的分枝因子是<FONT 
  face="Times New Roman"><EM>B</EM></FONT>，那么在搜索树一半的深度上，结点以因子<FONT 
  face="Times New Roman">B</FONT>作增长，而在另一半的深度上则保持不变<FONT 
  face="Times New Roman">(</FONT>我们忽略了主要变例<FONT 
  face="Times New Roman">)</FONT>。所以这个搜索树所有要搜索的结点数，粗略地写成<FONT 
  face="Times New Roman"><EM>B</EM><SUP><EM>D</EM>/2</SUP></FONT>&nbsp;<FONT 
  face="Times New Roman">=</FONT>&nbsp;<FONT 
  face="Times New Roman">sqrt(<EM>B</EM>)<SUP><EM>D</EM></SUP></FONT>。因此<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索最终可以将分枝因子减少为原来的平方根那么多，因此它可以让我们搜索原来两倍的深度。正因为这个原因，它是所有基于最小<FONT 
  face="Times New Roman">-</FONT>最大策略的棋类对弈程序的最重要的算法。 
  <DT><FONT color=#0000ff>　　【译注：原作者一开始提到的“浅的裁剪”和“深的裁剪”这两个概念，实际上包含了</FONT><FONT 
  face="Times New Roman" color=#0000ff>Alpha-Beta</FONT><FONT 
  color=#0000ff>搜索的两个层次，前者只是用过传递参数</FONT><FONT face="Times New Roman" 
  color=#0000ff>Beta</FONT><FONT color=#0000ff>对搜索树作了部分裁剪，可以称为</FONT><FONT 
  face="Times New Roman" color=#0000ff>Beta</FONT><FONT 
  color=#0000ff>搜索，而后者增加一个传递参数</FONT><FONT face="Times New Roman" 
  color=#0000ff>Alpha</FONT><FONT color=#0000ff>，使得裁剪更加充分，这就形成了</FONT><FONT 
  face="Times New Roman" color=#0000ff>Alpha-Beta</FONT><FONT 
  color=#0000ff>搜索。</FONT> 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>Beta</FONT><FONT color=#0000ff>搜索的伪代码是：</FONT> 
  <DD>　 
  <DD><FONT color=#ff0000>double alphabeta(int depth, double beta) {</FONT> 
  <DD><FONT color=#0000ff>　if (depth &lt;= 0 || 棋局结束) {</FONT> 
  <DD><FONT color=#0000ff>　　return evaluation();</FONT> 
  <DD><FONT color=#0000ff>　}</FONT> 
  <DD><FONT color=#0000ff>　就当前局面，生成并排序一系列着法;</FONT> 
  <DD><FONT color=#ff0000>　double alpha = -infty;</FONT> 
  <DD><FONT color=#0000ff>　for (每个着法 m) {</FONT> 
  <DD><FONT color=#0000ff>　　执行着法 m;</FONT> 
  <DD><FONT color=#ff0000>　　double val = -alphabeta(depth - 1, -alpha);</FONT> 
  <DD><FONT color=#0000ff>　　撤消着法 m;</FONT> 
  <DD><FONT color=#0000ff>　　if (val &gt;= beta) {</FONT> 
  <DD><FONT color=#0000ff>　　　return val;</FONT> 
  <DD><FONT color=#0000ff>　　}</FONT> 
  <DD><FONT color=#0000ff>　　if (val &gt; alpha) {</FONT> 
  <DD><FONT color=#0000ff>　　　alpha = val;</FONT> 
  <DD><FONT color=#0000ff>　　}</FONT> 
  <DD><FONT color=#0000ff>　}</FONT> 
  <DD><FONT color=#0000ff>　return alpha;</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>对红色部分加一些改进，就变成</FONT><FONT face="Times New Roman" 
  color=#0000ff>Alpha-Beta</FONT><FONT color=#0000ff>搜索的伪代码了。】</FONT> 
  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/970422.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/970422.html</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/search_intro1.htm">基本搜索方法——简介<FONT 
face="Times New Roman">(</FONT>一<FONT face="Times New Roman">)</FONT></A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/search_intro3.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>
12

⌨️ 快捷键说明

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