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

📄 国际象棋程序设计(五)：高级搜索方法.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
  face="Times New Roman">Alpha-Beta</FONT>搜索的变种，开始时用从负无穷大到正无穷大来限定搜索范围，然后在期望值附近设置小的窗口。如果实际数值恰好落在窗口以内，那么你赢了，你会准确无误地找到路线，并且比其他的路线快<FONT 
  face="Times New Roman">(</FONT>因为很多路线都被截断了<FONT 
  face="Times New Roman">)</FONT>。如果没有，那么算法就失败了，但是这个错误是很容易被检测的<FONT 
  face="Times New Roman">(</FONT>因为“最小<FONT 
  face="Times New Roman">-</FONT>最大”值就是其中一条边界<FONT 
  face="Times New Roman">)</FONT>，你必须浪费一点时间，用一个更大的窗口重新搜索。如果前面的情况比后面的情况多，那么总体上你还是赢了。很明显，你预先猜的数值越好，这个技术的收效就越大。 

  <DT>　　在上世纪<FONT face="Times New Roman">90</FONT>年代中期，研究员<FONT 
  face="Times New Roman">Aske Plaat</FONT>把期望搜索拓展为一个逻辑问题：如果你把带期望的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的窗口大小设定成<FONT 
  face="Times New Roman">0</FONT>，将会发生什么事？它当然永远不会成功。但是如果它成功了，那速度将是惊人的，因为它把几乎所有的路线全都截断了。现在，如果失败意味着实际数值低于你的估计，那么你用稍低点的宽度为零的窗口再试一次，重复下去。这样，你就等于用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索来做某个“最小<FONT 
  face="Times New Roman">-</FONT>最大”值的拆半查找<FONT face="Times New Roman">(Binary 
  Search)</FONT>，直到你最终找到那个宽度为零的窗口。 
  <DT>　　这个伟大的设想发表在一个网站上：<A href="http://theory.lcs.mit.edu/~plaat/mtdf.html" 
  target=about:blank><FONT 
  face="Times New Roman">http://theory.lcs.mit.edu/~plaat/mtdf.html</FONT></A>，它的具体实现称为<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>搜索算法，只有十多行。加上<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索和置换表的运用，<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>呈现出惊人的效率，还善于做并行计算。它在“粗糙”<FONT 
  face="Times New Roman">(</FONT>简单且快速<FONT 
  face="Times New Roman">)</FONT>的局面分析中运行得更好，很明显，如果局面评估的最小单位越大<FONT 
  face="Times New Roman">(</FONT>例如从<FONT 
  face="Times New Roman">0.001</FONT>个兵增加到<FONT 
  face="Times New Roman">0.1</FONT>个兵<FONT 
  face="Times New Roman">)</FONT>，它搜索的步数就越少。 
  <DT>　　在<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的变种当中，还有很多具有广泛用途的算法<FONT 
  face="Times New Roman">(</FONT>例如名声狼藉的<FONT 
  face="Times New Roman">NegaScout</FONT>，我宁可给白痴讲广义相对论，也不想给你们讲这些<FONT 
  face="Times New Roman">)</FONT><FONT color=#0000ff>【之所以说</FONT><FONT 
  face="Times New Roman" color=#0000ff>NegaScout</FONT><FONT 
  color=#0000ff>名声狼藉，是因为它的发明者</FONT><FONT face="Times New Roman" 
  color=#0000ff>Reinefeld</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>PVS(</FONT><FONT color=#0000ff>主要变例搜索</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>取代，因为它更容易理解】</FONT>，但是<FONT 
  face="Times New Roman">Plaat</FONT>坚持认为<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>是至今为止效率最高的算法。我就信了他的话，所以我的程序里用了<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</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>(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><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>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>10</FONT><FONT color=#0000ff>行，而跟它异曲同工的算法</FONT><FONT 
  face="Times New Roman" color=#0000ff>PVS</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>5</FONT><FONT 
  color=#0000ff>行左右，因此很奇怪原作者</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Laram</FONT><FONT color=#0000ff>é</FONT><FONT 
  face="Times New Roman" color=#0000ff>e)</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>MTD(<EM>f</EM>)</FONT><FONT 
  color=#0000ff>在并行计算上确实比</FONT><FONT face="Times New Roman" 
  color=#0000ff>PVS</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>PVS</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>PVS</FONT><FONT 
  color=#0000ff>的结论，而事实上大部分的程序用的都是</FONT><FONT face="Times New Roman" 
  color=#0000ff>PVS</FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><B>单步延伸</B></FONT> 
  <DT>　 
  <DT>　　在我们结束这个主题以前，这是最后一个话题。在象棋中，有些着法明显比其他的好，这样就可能没必要搜索其他的变化了。 
  <DT>　　例如，假设你在迭代加深过程中正在做深度为<FONT face="Times New Roman"><I>N</I></FONT><FONT 
  face=Symbol> -</FONT><FONT face="Times New Roman"> 1</FONT>的搜索，发现某步的评分为<FONT 
  face="Times New Roman">+9000(</FONT>即你吃了对方的后<FONT 
  face="Times New Roman">)</FONT>，而其他都低于<FONT 
  face="Times New Roman">0</FONT>。如果像比赛一样想节约时间，你会跳过前面的<FONT 
  face="Times New Roman"><I>N</I></FONT>层搜索而对这步进行<FONT 
  face="Times New Roman"><I>N</I></FONT>层搜索<FONT 
  color=#0000ff>【对于这步来说，搜索加深了一层，对于优势局面来说，优势应该是越来越大的，所以加深一层后评分应通常要高】</FONT>，如果这步额外搜索的评分不比预期的低，那么你可以假设这步棋会比其他着法都好，这样你就可以提前结束搜索了。<FONT 
  face="Times New Roman">(</FONT>记住，如果平均每层有<FONT 
  face="Times New Roman">35</FONT>种合理着法，那么你就可能节省<FONT 
  face="Times New Roman">97%</FONT>的时间！<FONT face="Times New Roman">)</FONT> 
  <DT>　　深蓝的小组发展了这个思想并提出了“单步延伸”<FONT face="Times New Roman">(Singular 
  Extension)</FONT>的概念。如果在搜索中某步看上去比其他变化好很多，它就会加深这步搜索以确认里边没有陷阱。<FONT 
  face="Times New Roman">(</FONT>实际过程远比这里说的要复杂，当然基本思想没变。<FONT 
  face="Times New Roman">)</FONT>单步延伸是耗费时间的，对一个结点增加一层搜索会使搜索树的大小翻一番，评估局面的计算量同时也翻一番。换句话说，只有深蓝那种硬件水平才吃得消它，我那笨拙的<FONT 
  face="Times New Roman">Java</FONT>代码肯定不行。但是它的成效是不可否认的，不是吗？<FONT 
  color=#0000ff>【原作者的意思可能是指，单步延伸技术会明显提高棋力，同时也会增加搜索时间。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><B>下一个月</B></FONT> 
  <DT>　 
  <DT>　　在第六部分中，我们会着重讨论局面评估函数，它才真正告诉程序一个局面是好是坏。这个主题具有极其广泛的内容，可以花几年时间来改进评估方法<FONT 
  face="Times New Roman">(</FONT>也确实有人这样做<FONT 
  face="Times New Roman">)</FONT>，因此我们必须对这些内容进行彻底讨论，包括它们的可行性和重要程度。<FONT 
  color=#0000ff>【在这篇普及型的连载中，作者怎么可能给你们讲那么多呢？】</FONT>如果任何事情都按照计划进行，我就该用一些<FONT 
  face="Times New Roman">Java</FONT>代码来给你们填饱肚子，但是这很难办到，不是吗？ 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">Fran</FONT>&ccedil;<FONT 
  face="Times New Roman">ois Dominic Laram</FONT>é<FONT 
  face="Times New Roman">e</FONT>，<FONT face="Times New Roman">2000</FONT>年<FONT 
  face="Times New Roman">9</FONT>月 
  <DT>　 
  <DT>　　原文：<A 
  href="http://www.gamedev.net/reference/programming/features/chess5/" 
  target=_blank><FONT 
  face="Times New Roman">http://www.gamedev.net/reference/programming/features/chess5/</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>　　说明：<FONT face="Times New Roman">2004</FONT>年<FONT 
  face="Times New Roman">11</FONT>月首先发表于《<A href="http://www.chessit.net/" 
  target=_blank>国际象棋译文苑</A>》，<FONT face="Times New Roman">2005</FONT>年<FONT 
  face="Times New Roman">5</FONT>月修订译注。 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/basic_search.htm">国际象棋程序设计<FONT 
face="Times New Roman">(</FONT>四<FONT face="Times New Roman">)</FONT>：基本搜索方法</A> 

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