?? 基本搜索方法——簡介(二).htm
字號:
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>></U></FONT> <FONT
face="Times New Roman"><EM>x</EM> +
Epsilon</FONT>。這種情況下，我們知道搜索結果也至少是 <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><</U></FONT> <FONT
face="Times New Roman"><EM>x</EM> </FONT><FONT face=Symbol>-</FONT><FONT
face="Times New Roman"> Epsilon</FONT>。這種情況下，我們知道搜索結果也最多是 <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> <FONT
face="Times New Roman">=</FONT> <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 <= 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 >= beta) {</FONT>
<DD><FONT color=#0000ff> return val;</FONT>
<DD><FONT color=#0000ff> }</FONT>
<DD><FONT color=#0000ff> if (val > 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>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -