<DT>　　如果某個(gè)著法的結(jié)果大于<FONT face="Times New Roman">Alpha</FONT>但小于<FONT 
  face="Times New Roman">Beta</FONT>，那么這個(gè)著法就是走棋一方可以考慮走的，除非以后有所變化。因此<FONT 
  face="Times New Roman">Alpha</FONT>會(huì)不斷增加以反映新的情況。有時(shí)候可能一個(gè)合理著法也不超過<FONT 
  face="Times New Roman">Alpha</FONT>，這在實(shí)戰(zhàn)中是經(jīng)常發(fā)生的，此時(shí)這種局面是不予考慮的，因此為了避免這樣的局面，我們必須在博弈樹的上一個(gè)層局面選擇另外一個(gè)著法。 

  <DT>　　在第二個(gè)口袋里找到爛魚就相當(dāng)于超過了<FONT 
  face="Times New Roman">Beta</FONT>，如果口袋里沒有爛魚，那么考慮六盒裝流行唱片的口袋會(huì)比三明治的口袋好，這就相當(dāng)于超過了<FONT 
  face="Times New Roman">Alpha(</FONT>在上一層<FONT 
  face="Times New Roman">)</FONT>。算法如下，醒目的部分是在最小<FONT 
  face="Times New Roman">-</FONT>最大算法上改過的： 
  <DD>　 
  <DD>int <FONT color=#ff0000>AlphaBeta</FONT>(int depth<FONT color=#ff0000>, 
  int alpha, int beta</FONT>) { 
  <DD>　if (depth == 0) { 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD>　　MakeNextMove(); 
  <DD>　　val = -<FONT color=#ff0000>AlphaBeta</FONT>(depth - 1<FONT 
  color=#ff0000>, -beta, -alpha</FONT>); 
  <DD>　　UnmakeMove(); 
  <DD><FONT color=#ff0000>　　if (val &gt;= beta) {</FONT> 
  <DD><FONT color=#ff0000>　　　return beta;</FONT> 
  <DD><FONT color=#ff0000>　　}</FONT> 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　把醒目的部分去掉，剩下的就是最小-最大函數(shù)。可以看出現(xiàn)在的算法沒有太多的改變。 
  <DT>　　這個(gè)函數(shù)需要傳遞的參數(shù)有：需要搜索的深度，負(fù)無窮大即<FONT 
  face="Times New Roman">Alpha</FONT>，以及正無窮大即<FONT 
  face="Times New Roman">Beta</FONT>： 
  <DD>　 
  <DD>val = AlphaBeta(5, -INFINITY, INFINITY); 
  <DT>　 
  <DT>　　這樣就完成了<FONT face="Times New Roman">5</FONT>層的搜索。我在寫最小<FONT 
  face="Times New Roman">-</FONT>最大函數(shù)時(shí)，用了一個(gè)訣竅來避免用了“<FONT 
  face="Times New Roman">Min</FONT>”還用“<FONT 
  face="Times New Roman">Max</FONT>”函數(shù)。在那個(gè)算法中，我從遞歸中返回時(shí)簡(jiǎn)單地對(duì)返回值取了負(fù)數(shù)。這樣就使函數(shù)值在每一次遞歸中改變?cè)u(píng)價(jià)的角度，以反映雙方棋手的交替著子，并且它們的目標(biāo)是對(duì)立的。 

  <DT>　　在<FONT 
  face="Times New Roman">Alpha-Beta</FONT>函數(shù)中我們做了同樣的處理。唯一使算法感到復(fù)雜的是，<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>是不斷互換的。當(dāng)函數(shù)遞歸時(shí)，<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>不但取負(fù)數(shù)而且位置交換了，這就使得情況比口袋的例子復(fù)雜，但是可以證明它只是比最小<FONT 
  face="Times New Roman">-</FONT>最大算法更好而已。 
  <DT>　　最終出現(xiàn)的情況是，在搜索樹的很多地方，<FONT 
  face="Times New Roman">Beta</FONT>是很容易超過的，因此很多工作都免去了。 
  <DT>　 
  <DT><A name="branching factor"></A><FONT face=楷體_GB2312 
  size=5><STRONG>可能的弱點(diǎn)</STRONG></FONT> 
  <DT>　 
  <DT>　　這個(gè)算法嚴(yán)重依賴于著法的尋找順序。如果你總是先去搜索最壞的著法，那么<FONT 
  face="Times New Roman">Beta</FONT>截?cái)嗑筒粫?huì)發(fā)生，因此該算法就如同最小<FONT 
  face="Times New Roman">-</FONT>最大一樣，效率非常低。該算法最終會(huì)找遍整個(gè)博弈樹，就像最小<FONT 
  face="Times New Roman">-</FONT>最大算法一樣。 
  <DT>　　如果程序總是能挑最好的著法來首先搜索，那么數(shù)學(xué)上有效分枝因子就接近于實(shí)際分枝因子的平方根。這是<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法可能達(dá)到的最好的情況。 
  <DT>　　由于國(guó)際象棋的分枝因子在<FONT face="Times New Roman">35</FONT>左右，這就意味著<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法能使國(guó)際象棋搜索樹的分枝因子變成<FONT 
  face="Times New Roman">6</FONT>。 
  <DT>　　這是很大的改進(jìn)，在搜索結(jié)點(diǎn)數(shù)一樣的情況下，可以使你的搜索深度達(dá)到原來的兩倍。這就是為什么使用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索時(shí)，著法順序至關(guān)重要的原因。 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/alphabeta.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/alphabeta.htm</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://homepage.fudan.edu.cn/~auntyellow/computer/search_minimax.htm">基本搜索方法——最小<FONT 
face="Times New Roman">-</FONT>最大搜索</A> 
<LI>下一篇　<A 
href="http://homepage.fudan.edu.cn/~auntyellow/computer/search_iterative.htm">基本搜索方法——迭代加深</A> 

<LI>返　回　<A 
href="http://homepage.fudan.edu.cn/~auntyellow/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="基本搜索方法——Alpha-Beta搜索_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>