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

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

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
  face="Times New Roman">WIN </FONT>和 <FONT face="Times New Roman">-WIN</FONT> 
  的差的对数<FONT face="Times New Roman">)</FONT>。而<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>的思想则是用超出边界的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>对搜索进行控制：每次调用超出边界的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>就会返回一个值更接近于最终值，如果用这个搜索值作为下次测试的开始，我们最终会达到收敛。 

  <DD>　 
  <DD>// MTD(f) 
  <DD>int test = 0; 
  <DD>for ( ; ; ) { 
  <DD>　score = alphabeta(depth, test, test + 1); 
  <DD>　if (test == score) { 
  <DD>　　break; 
  <DD>　} 
  <DD>　test = score; 
  <DD>} 
  <DT>　 
  <DT><FONT 
  size=3>　　不幸的是，它和散列表之间的复杂作用会导致这个过程陷入无限循环，所以必须加上额外的代码，如果迭代次数太多而没有收敛，就必须中止搜索。</FONT> 

  <DT><FONT size=3>　　</FONT><FONT face="Times New Roman" 
  size=3>MTD(<EM>f</EM>)</FONT><FONT size=3>的一个大的优势在于我们可以简化</FONT><FONT 
  face="Times New Roman" size=3>Alpha-Beta</FONT><FONT 
  size=3>搜索，因为它只需要两个参数</FONT><FONT face="Times New Roman" size=3>(</FONT><FONT 
  size=3>深度和</FONT><FONT face="Times New Roman" size=3>Alpha)</FONT><FONT 
  size=3>而不是三个。</FONT><FONT 
  color=#0000ff>【据说这样做可以提高并行计算的效率，遗憾的是译者对并行计算一窍不通。】</FONT> 
  <DT><FONT color=#0000ff>　　【为了对</FONT><FONT face="Times New Roman" 
  color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT 
  color=#0000ff>有更详细的了解，译者查阅了该算法的发明者</FONT><FONT face="Times New Roman" 
  color=#0000ff>Plaat</FONT><FONT color=#0000ff>的网站，他提供的</FONT><FONT 
  face="Times New Roman" color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT 
  color=#0000ff>代码中用了两个边界，可以防止迭代过程中出现振荡而不收敛的情况，代码如下</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>原来是</FONT><FONT face="Times New Roman" 
  color=#0000ff>Pascal</FONT><FONT color=#0000ff>语言，现被译者转写为</FONT><FONT 
  face="Times New Roman" color=#0000ff>C</FONT><FONT 
  color=#0000ff>语言</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT color=#0000ff>：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>int MTDF(int test, int depth) {</FONT> 
  <DD><FONT color=#0000ff>　int score, beta, upperbound, lowerbound;</FONT> 
  <DD><FONT color=#0000ff>　score = test;</FONT> 
  <DD><FONT color=#0000ff>　upperbound = +INFINITY;</FONT> 
  <DD><FONT color=#0000ff>　lowerbound = -INFINITY;</FONT> 
  <DD><FONT color=#0000ff>　do {</FONT> 
  <DD><FONT color=#0000ff>　　beta = (score == lowerbound ? score + 1 : 
  score);</FONT> 
  <DD><FONT color=#0000ff>　　score = alphabeta(depth, beta - 1, beta);</FONT> 
  <DD><FONT color=#0000ff>　　(score &lt; beta ? upperbound : lowerbound) = 
  score;</FONT> 
  <DD><FONT color=#0000ff>　} while (lowerbound &lt; upperbound);</FONT> 
  <DD><FONT color=#0000ff>　return score;</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　而关于</FONT><FONT face="Times New Roman" 
  color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT color=#0000ff>的使用另有以下几点技巧：</FONT> 
  <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>MTD(<EM>f</EM>)</FONT><FONT color=#0000ff>搜索给出；</FONT> 
  <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>MTD(<EM>f</EM>)</FONT><FONT 
  color=#0000ff>的效率越高，例如国际象棋中可使一个兵的价值由</FONT><FONT face="Times New Roman" 
  color=#0000ff>100</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>MTD(<EM>f</EM>)</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>(3) </FONT><FONT 
  color=#0000ff>零宽度窗口的搜索需要置换表的有力支持，因此称为“用存储器增强的试探驱动器”</FONT><FONT 
  face="Times New Roman" color=#0000ff>(Memory-enhanced Test Driver</FONT><FONT 
  color=#0000ff>，即</FONT><FONT face="Times New Roman" 
  color=#0000ff>MTD)</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>n</EM></FONT><FONT color=#0000ff>和试探值</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>f</EM>)</FONT><FONT 
  color=#0000ff>，故得名为</FONT><FONT face="Times New Roman" 
  color=#0000ff>MTD(<EM>n</EM>,<EM>f</EM>)</FONT><FONT 
  color=#0000ff>，缩写为</FONT><FONT face="Times New Roman" 
  color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>PVS</STRONG></FONT> 
  <DT>　 
  <DT>　　或许最好的<FONT face="Times New Roman">Alpha-Beta</FONT>变体，要算是这些名称了：负值侦察<FONT 
  face="Times New Roman">(NegaScout)</FONT>和主要变例搜索<FONT 
  face="Times New Roman">(Principal Variation Search</FONT>，简称<FONT 
  face="Times New Roman">PVS)</FONT>。这个思想就是当第一次迭代搜索时找到最好的值，那么<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的效率最高。对着法列表进行排序，或者把最好的着法保存到散列表中，这些技术可能让第一个着法成为最佳着法。如果真是如此，我们就可以假设其他着法不可能是好的着法，从而对它们快速地搜索过去。 

  <DT>　　因此<FONT 
  face="Times New Roman">PVS</FONT>对第一个搜索使用正常的窗口，而后续搜索使用零宽度的窗口，来对每个后续着法和第一个着法作比较。只有当零窗口搜索失败后才去做正常的搜索。 

  <DD>　 
  <DD>// 主要变例搜索(超出边界的版本) 
  <DD>int alphabeta(int depth, int alpha, int beta) { 
  <DD>　move bestmove, current; 
  <DD>　if (棋局结束 || depth &lt;= 0) { 
  <DD>　　return eval(); 
  <DD>　} 
  <DD>　move m = 第一个着法; 
  <DD>　执行着法 m; 
  <DD>　current = -alphabeta(depth - 1, -beta, -alpha); 
  <DD>　撤消着法 m; 
  <DD>　for (其余的每个着法 m) { 
  <DD>　　执行着法 m; 
  <DD>　　score = -alphabeta(depth - 1, -alpha - 1, -alpha); 
  <DD>　　if (score &gt; alpha &amp;&amp; score &lt; beta) { 
  <DD>　　　score = -alphabeta(depth - 1, -beta, -alpha); 
  <DD>　　} 
  <DD>　　撤消着法 m; 
  <DD>　　if (score &gt;= current) { 
  <DD>　　　current = score; 
  <DD>　　　bestmove = m; 
  <DD>　　　if (score &gt;= alpha) { 
  <DD>　　　　alpha = score; 
  <DD>　　　} 
  <DD>　　　if (score &gt;= beta) { 
  <DD>　　　　break; 
  <DD>　　　} 
  <DD>　　} 
  <DD>　} 
  <DD>　return current; 
  <DD>} 
  <DT>　 
  <DT>　　这个算法跟<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>有个同样的优势，即搜索树的大多数结点都以零宽度的窗口搜索，可以用双参数的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>。由于“<FONT face="Times New Roman">Beta 
  &gt; Alpha + 1</FONT>”的调用非常少，因此不必担心额外的工作<FONT 
  face="Times New Roman">(</FONT>例如保存最佳着法以供将来使用<FONT 
  face="Times New Roman">)</FONT>会占用很多时间。<FONT 
  color=#0000ff>【原作者的意思是，调用零宽度窗口的搜索时，可以免去保存最佳着法等操作，因此可以省下不少时间。】</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>和<FONT 
  face="Times New Roman">PVS(</FONT>用在搜索过程内部<FONT 
  face="Times New Roman">)</FONT>。但是不同的棋类游戏不一样，由于这些搜索不难实现，所以要在这些方法中进行选择或调节参数，就必须对它们逐一实现并做一些试验。它们都必须返回同样的搜索值<FONT 
  face="Times New Roman">(</FONT>如果受散列表影响，那么至少是相近的值<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>Alpha-Beta</FONT><FONT 
  color=#0000ff>搜索，在使用散列表时可能会返回不同的值】</FONT><FONT 
  face="Times New Roman">)</FONT>，但搜索的结点数会不同。在你的棋类的典型局面中，能使搜索树最小的方法则被采纳。 
  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/990202b.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/990202b.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/advanced_intro1.htm">高级搜索方法——简介<FONT 
face="Times New Roman">(</FONT>一<FONT face="Times New Roman">)</FONT></A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/advanced_quiescent.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>
12

⌨️ 快捷键说明

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