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>