Alpha-beta剪枝

Alpha-beta剪枝是一種搜尋演算法,用以減少極小化極大演算法(Minimax演算法)搜尋樹的節點數。這是一種對抗性搜尋演算法,主要應用於機器遊玩的二人遊戲(如井字棋象棋圍棋)。當演算法評估出某策略的後續走法比之前策略的還差時,就會停止計算該策略的後續發展。該演算法和極小化極大演算法所得結論相同,但剪去了不影響最終決定的分枝[1]

歷史

Allen Newell和Herbert A. Simon在1958年,使用了John McCarthy所謂的「近似」alpha-beta演算法[2],此演算法當時「應已重新改造過多次」[3]亞瑟·李·塞謬爾(Arthur Samuel)有一個早期版本,同時Richards、Hart、Levine和/或Edwards在美國分別獨立發現了alpha-beta[4]。McCarthy在1956年達特默思會議上提出了相似理念,並在1961年建議給他的一群學生,其中包括MIT的Alan Kotok[5]。Alexander Brudno獨立發現了alpha-beta演算法,並在1963年發佈成果[6]Donald Knuth和Ronald W. Moore在1975年最佳化了演算法[7][8],Judea Pearl在1982年證明了其最佳性[9]

對原版極小化極大演算法的改進

Alpha-beta的優點是減少搜尋樹的分枝,將搜尋時間用在「更有希望」的子樹上,繼而提升搜尋深度。該演算法和極小化極大演算法一樣,都是分支限界類演算法。若節點搜尋順序達到最佳化或近似最佳化(將最佳選擇排在各節點首位),則同樣時間內搜尋深度可達極小化極大演算法的兩倍多。

在(平均或恆定)分枝因子為b,搜尋深度為d層的情況下,要評估的最大(即招法排序最差時)葉節點數目為O(b*b*...*b) = O(bd)——即和簡單極小化極大搜尋一樣。若招法排序最佳(即始終優先搜尋最佳招法),則需要評估的最大葉節點數目按層數奇偶性,分別約為O(b*1*b*1*...*b)和O(b*1*b*1*...*1)(或O(bd/2) = O(√bd))。其中層數為偶數時,搜尋因子相當於減少了其平方根,等於能以同深度搜尋兩次[10]b*1*b*1*...意義為,對第一名玩家必須搜尋全部招法找到最佳招式,但對於它們,只用將第二名玩家的最佳招法截斷——alpha-beta確保無需考慮第二名玩家的其他招法。但因節點生成順序隨機,實際需要評估的節點平均約為O(b3d/4)[2]

一般在alpha-beta中,子樹會由先手方優勢或後手方優勢暫時佔據主導。若招式排序錯誤,這一優勢會多次切換,每次讓效率下降。隨着層數深入,局面數量會呈指數性增長,因此排序早期招式價值很大。儘管改善任意深度的排序,都以能指數性減少總搜尋局面,但排序臨近根節點深度的全部局面相對經濟。在實踐中,招法排序常由早期、小型搜尋決定,如通過迭代加深

演算法使用兩個值alpha和beta,分別代表大分玩家放心的最高分,以及小分玩家放心的最低分。alpha和beta的初始值分別為正負無窮大,即雙玩家都以可能的最低分開始遊戲。在選擇某節點的特定分枝後,可能發生小分玩家放心的最小分小於大分玩家放心的最大分(beta <= alpha)。這種情況下,父節點不應選擇這個節點,否則父節點分數會降低,因此該分枝的其他節點沒有必要繼續探索。

偽代碼

下面為一有限可靠性版本的Alpha-beta剪枝的虛擬代碼[10]

 function alphabeta(node, depth, α, β, maximizingPlayer) // node = 节点,depth = 深度,maximizingPlayer = 大分玩家
     if depth = 0 or node是终端節點
         return 節點的啟發值
     if maximizingPlayer
         v := -∞
         for 每个子節點
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) // child = 子節點
             α := max(α, v)
             if β ≤ α
                 break // β裁剪
         return v
     else
         v := ∞
         for 每个子節點
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break // α裁剪
         return v
(* 初始調用 *)
alphabeta(origin, depth, -, +, TRUE) // origin = 初始節點

在這個有限可靠性的alpha-beta中,當v超出調用參數α和β構成的集合時(v < α或v > β),alphabeta函數返回值v。而與此相對,強化的有限可靠性alpha-beta限制函數返回在α與β包括範圍中的值。

參考文獻

  1. ^ Russell, Stuart J.; Norvig, Peter. Artificial Intelligence: A Modern Approach 3rd. Upper Saddle River, New Jersey: Pearson Education, Inc. 2010: 167 [2016-02-05]. ISBN 0-13-604259-7. (原始內容存檔於2011-02-28). 
  2. ^ 2.0 2.1 McCarthy, John. Human Level AI Is Harder Than It Seemed in 1955. LaTeX2HTML 27 November 2006 [2006-12-20]. (原始內容存檔於2012-04-08). 
  3. ^ Newell, Allen and Herbert A. Simon. Computer Science as Empirical Inquiry: Symbols and Search (PDF). Communications of the ACM. March 1976, 19 (3) [2006-12-21]. doi:10.1145/360018.360022. (原始內容 (PDF)存檔於2007-06-28). 
  4. ^ Edwards, D.J. and Hart, T.P. The Alpha–beta Heuristic (AIM-030). Massachusetts Institute of Technology. 4 December 1961 to 28 October 1963 [2006-12-21]. (原始內容存檔於2012-04-08). 
  5. ^ Kotok, Alan. MIT Artificial Intelligence Memo 41. 2004-12-03 [2006-07-01]. (原始內容存檔於2012-04-08). 
  6. ^ Marsland, T.A.. Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor) (PDF). J. Wiley & Sons: 159–171. May 1987 [2006-12-21]. (原始內容 (PDF)存檔於2008-10-30). 
  7. ^ * Knuth, D. E., and Moore, R. W. An Analysis of Alpha–Beta Pruning (PDF). Artificial Intelligence. 1975, 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. [永久失效連結] Reprinted as Chapter 9 in Knuth, Donald E. Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. 2000 [2016-02-05]. ISBN 1-57586-212-3. OCLC 222512366. (原始內容存檔於2010-11-15). 
  8. ^ Abramson, Bruce. Control Strategies for Two-Player Games (PDF). ACM Computing Surveys. June 1989, 21 (2): 137 [2008-08-20]. doi:10.1145/66443.66444. (原始內容 (PDF)存檔於2008-08-20). 
  9. ^ Pearl, Judea. The Solution for the Branching Factor of the Alpha–beta Pruning Algorithm and its Optimality. Communications of the ACM. August 1982, 25 (8): 559–564. doi:10.1145/358589.358616. 
  10. ^ 10.0 10.1 Russell, Stuart J.; Norvig, Peter, Artificial Intelligence: A Modern Approach 2nd, Upper Saddle River, New Jersey: Prentice Hall, 2003 [2016-02-05], ISBN 0-13-790395-2, (原始內容存檔於2011-02-28) 

外部連結