《對弈程序基本技術》專題
 
Alpha-Beta搜索
 
Bruce Moreland /
 
最小-最大的問題
 
  Alpha-Beta 同“最小-最大”非常相似,事實上只多了一條額外的語句。最小最大運行時要檢查整個博弈樹,然后盡可能選擇最好的線路。這是非常好理解的,但效率非常低。每次搜索更深一層時,樹的大小就呈指數式增長。
  通常一個國際象棋局面都有35個左右的合理著法,所以用最小-最大搜索來搜索一層深度,就有35個局面要檢查,如果用這個函數來搜索兩層,就有352個局面要搜索。這就已經上千了,看上去還不怎樣,但是數字增長得非常迅速,例如六層的搜索就接近是二十億,而十層的搜索就超過兩千萬億了。
  要想通過檢查搜索樹的前面幾層,并且在葉子結點上用啟發式的評價,那么做盡可能深的搜索是很重要的。最小-最大搜索無法做到很深的搜索,因為有效的分枝因子實在太大了。
 
口袋的例子
 
  幸運的是我們有辦法來減小分枝因子,這個辦法非常可靠,實際上這樣做絕對沒有壞處,純粹是個有益的辦法。這個方法是建立在一個思想上的,如果你已經有一個不太壞的選擇了,那么當你要作別的選擇并知道它不會更好時,你沒有必要確切地知道它有多壞。有了最好的選擇,任何不比它更好的選擇就是足夠壞的,因此你可以撇開它而不需要完全了解它。只要你能證明它不比最好的選擇更好,你就可以完全拋棄它。
  你可能仍舊不明白,那么我就舉個例子。比如你的死敵面前有很多口袋,他和你打賭賭輸了,因此他必須從中給你一樣東西,而挑選規則卻非常奇怪:
  每個口袋里有幾件物品,你能取其中的一件,你來挑這件物品所在的口袋,而他來挑這個口袋里的物品。你要趕緊挑出口袋并離開,因為你不愿意一直做在那里翻口袋而讓你的死敵盯著你。
  假設你一次只能找一只口袋,在找口袋時一次只能從里面摸出一樣東西。
  很顯然,當你挑出口袋時,你的死敵會把口袋里最糟糕的物品給你,因此你的目標是挑出“諸多最糟的物品當中是最好的”那個口袋。
  你很容易把最小-最大原理運用到這個問題上。你是最大一方棋手,你將挑出最好的口袋。而你的死敵是最小一方棋手,他將挑出最好的口袋里盡可能差的物品。運用最小-最大原理,你需要做的就是挑一個有“最好的最差的”物品的口袋。
  假設你可以估計口袋里每個物品的準確價值的話,最小-最大原理可以讓你作出正確的選擇。我們討論的話題中,準確評價并不重要,因為它同最小-最大或Alpha-Beta的工作原理沒有關系。現在我們假設你可以正確地評價物品。
  最小-最大原理剛才討論過,它的問題是效率太低。你必須看每個口袋里的每件物品,這就需要花很多時間。
  那么怎樣才能做得比最小-最大更高效呢?
  我們從第一個口袋開始,看每一件物品,并對口袋作出評價。比方說口袋里有一只花生黃油三明治和一輛新汽車的鑰匙。你知道三明治更糟,因此如果你挑了這只口袋就會得到三明治。事實上只要我們假設對手也會跟我們一樣正確評價物品,那么口袋里的汽車鑰匙就是無關緊要的了。
  現在你開始翻第二個口袋,這次你采取的方案就和最小-最大方案不同了。你每次看一件物品,并跟你能得到的最好的那件物品(三明治)去比較。只要物品比三明治更好,那么你就按照最小-最大方案來辦——去找最糟的,或許最糟的要比三明治更好,那么你就可以挑這個口袋,它比裝有三明治的那個口袋好。
  比方這個口袋里的第一件物品是一張20美元的鈔票,它比三明治好。如果包里其他東西都沒比這個更糟了,那么如果你選了這個口袋,它就是對手必須給你的物品,這個口袋就成了你的選擇。
  這個口袋里的下一件物品是六合裝的流行唱片。你認為它比三明治好,但比20美元差,那么這個口袋仍舊可以選擇。再下一件物品是一條爛魚,這回比三明治差了。于是你就說“不謝了”,把口袋放回去,不再考慮它了。
  無論口袋里還有什么東西,或許還有另一輛汽車的鑰匙,也沒有用了,因為你會得到那條爛魚。或許還有比爛魚更糟的東西(那么你看著辦吧)。無論如何爛魚已經夠糟的了,而你知道挑那個有三明治的口袋肯定會更好。
 
算法
 
  Alpha-Beta就是這么工作的,并且只能用遞歸來實現。稍后我們再來談最小一方的策略,我希望這樣可以更明白些。
  這個思想是在搜索中傳遞兩個值,第一個值是Alpha,即搜索到的最好值,任何比它更小的值就沒用了,因為策略就是知道Alpha的值,任何小于或等于Alpha的值都不會有所提高。
  第二個值是Beta,即對于對手來說最壞的值。這是對手所能承受的最壞的結果,因為我們知道在對手看來,他總是會找到一個對策不比Beta更壞的。如果搜索過程中返回Beta或比Beta更好的值,那就夠好的了,走棋的一方就沒有機會使用這種策略了。
  在搜索著法時,每個搜索過的著法都返回跟AlphaBeta有關的值,它們之間的關系非常重要,或許意味著搜索可以停止并返回。
  如果某個著法的結果小于或等于Alpha,那么它就是很差的著法,因此可以拋棄。因為我前面說過,在這個策略中,局面對走棋的一方來說是以Alpha為評價的。
  如果某個著法的結果大于或等于Beta,那么整個結點就作廢了,因為對手不希望走到這個局面,而它有別的著法可以避免到達這個局面。因此如果我們找到的評價大于或等于Beta,就證明了這個結點是不會發生的,因此剩下的合理著法沒有必要再搜索。
  如果某個著法的結果大于Alpha但小于Beta,那么這個著法就是走棋一方可以考慮走的,除非以后有所變化。因此Alpha會不斷增加以反映新的情況。有時候可能一個合理著法也不超過Alpha,這在實戰中是經常發生的,此時這種局面是不予考慮的,因此為了避免這樣的局面,我們必須在博弈樹的上一個層局面選擇另外一個著法。
  在第二個口袋里找到爛魚就相當于超過了Beta,如果口袋里沒有爛魚,那么考慮六盒裝流行唱片的口袋會比三明治的口袋好,這就相當于超過了Alpha(在上一層)。算法如下,醒目的部分是在最小-最大算法上改過的:
 
int AlphaBeta(int depth, int alpha, int beta) {
 if (depth == 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -AlphaBeta(depth - 1, -beta, -alpha);
  UnmakeMove();
  if (val >= beta) {
   return beta;
  }
  if (val > alpha) {
   alpha = val;
  }
 }
 return alpha;
}
 
  把醒目的部分去掉,剩下的就是最小-最大函數。可以看出現在的算法沒有太多的改變。
  這個函數需要傳遞的參數有:需要搜索的深度,負無窮大即Alpha,以及正無窮大即Beta
 
val = AlphaBeta(5, -INFINITY, INFINITY);
 
  這樣就完成了5層的搜索。我在寫最小-最大函數時,用了一個訣竅來避免用了“Min”還用“Max”函數。在那個算法中,我從遞歸中返回時簡單地對返回值取了負數。這樣就使函數值在每一次遞歸中改變評價的角度,以反映雙方棋手的交替著子,并且它們的目標是對立的。
  在Alpha-Beta函數中我們做了同樣的處理。唯一使算法感到復雜的是,AlphaBeta是不斷互換的。當函數遞歸時,AlphaBeta不但取負數而且位置交換了,這就使得情況比口袋的例子復雜,但是可以證明它只是比最小-最大算法更好而已。
  最終出現的情況是,在搜索樹的很多地方,Beta是很容易超過的,因此很多工作都免去了。
 
可能的弱點
 
  這個算法嚴重依賴于著法的尋找順序。如果你總是先去搜索最壞的著法,那么Beta截斷就不會發生,因此該算法就如同最小-最大一樣,效率非常低。該算法最終會找遍整個博弈樹,就像最小-最大算法一樣。
  如果程序總是能挑最好的著法來首先搜索,那么數學上有效分枝因子就接近于實際分枝因子的平方根。這是Alpha-Beta算法可能達到的最好的情況。
  由于國際象棋的分枝因子在35左右,這就意味著Alpha-Beta算法能使國際象棋搜索樹的分枝因子變成6
  這是很大的改進,在搜索結點數一樣的情況下,可以使你的搜索深度達到原來的兩倍。這就是為什么使用Alpha-Beta搜索時,著法順序至關重要的原因。
 
  原文:http://www.seanet.com/~brucemo/topics/alphabeta.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 基本搜索方法——最小-最大搜索
  • 下一篇 基本搜索方法——迭代加深
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果