Alpha-beta鉸枝

Alpha-beta 鉸枝是一種搜揣演算法，用減少極小化極大演算法（Minimax 演算法）搜尋樹仔的節點數。這是一種對抗性搜揣演算法，主要應用佇機器𨑨迌的二人遊戲（若井字棋、象棋、圍棋）。做演算法評估出某策略的後續行法比進前這个策略的差時，就會停止計算該策略後續的發展。該演算法佮極小化極大演算法所得結論仝款，但剪去無影響最終決定的分枝。

歷史

Allen Newell 和 Herbert A . Simon 佇一九五八年，使用矣 John McCarthy 咱所講的「近來親像」alpha-beta 演算法，此演算法彼陣「應該已經重新改造傷過濟改」。亞瑟・李・塞譀爾（Arthur Samuel）有一个早期版本，同時 Richards、Hart、Levine 和 / 抑是 Edwards 佇美國分別獨立發現矣 alpha-beta。McCarthy 佇一九五六年達特默思會議頂提出相仝理念，並且佇一九六一年建議予伊的一陣學生，其中包括講 MIT 的 Alan Kotok。Alexander Brudno 獨立發現矣 alpha-beta 演算法，並且佇一九六三年發布成果。Donald Knuth 和 Ronald W . Moore 佇一九七五年最佳化矣演算法，Judea Pearl 佇咧一九八二年證明矣其最佳性。

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

Alpha-beta 的優點是減少搜揣樹仔的分枝，將搜揣時間用佇咧「閣較有希望」的子樹頂，繼續提升搜揣深度。該演算法佮極小化極大演算法仝款，攏是分支限界類演算法。若節點搜揣順序達到最佳化抑是近近了後最佳化（將最佳選擇排佇咧各節點頭一位），仝款時間內搜揣深度會當極小化極大演算法的兩倍外。

佇咧（平均抑是恆定）分枝因為 _ b _，搜揣深度為 _ d _ 層的情形下，講愛評估的上大（即招法排序上䆀的時）葉節點數目為 _ O _ ( _ b _ \ * _ b _ \ * . . . \ * _ b _ )=_ O _ ( _ b _ d )—— 即佮簡單極小化極大搜揣一項。若招法排序最佳（即始終優先搜揣最佳的招法），著愛評估上大葉節點數目揤層數奇偶性，分別約為 _ O _ ( _ b _ \ * 一 \ * _ b _ \ * 一 \ * . . . \ * _ b _ ) 和 _ O _ ( _ b _ \ * 一 \ * _ b _ \ * 一 \ * . . . \ * 一 )（抑是 _ O _ ( _ b _ d / 二 )=_ O _ ( √ _ b _ d )）。其中層數共偶數的時，搜揣因為減少其平方根，等於會當平深度搜揣兩改。_ b _ \ * 一 \ * _ b _ \ * 一 \ * . . . 意義為，著第一名𨑨迌物仔著愛搜揣全部招法揣著最佳的招式，毋過對𪜶，只用將第二名𨑨迌家的最佳招法截斷—— alpha-beta 確保無需要考慮第二名𨑨迌物仔的其他招法。毋過因為節點成順序隨機，實際需要評估的節點平均約為 _ O _ ( _ b _ 三 _ d _ / 四 )。

一般咧 alpha-beta 中，子樹仔會由先手方優勢抑是後手方的優勢暫時占照主導。若是招式排序錯誤，這一優勢會多次切換，逐擺予效率下降。隨著層數來深入，局面數量會呈指數性增長，因為按呢排序早期算蓋大。就算改善任意深度的排序，攏以會當指數性減少總搜尋局面，但排序臨近根節點深度的全部局面相對經濟。咱佇實踐中，撇法排序定定由較早、小型搜揣決定，迵過迵天代加深。

演算法使用兩个值 alpha 和 beta，分別代表大分𨑨迌人放心上懸分，以及細分𨑨迌物仔放心的上低分。alpha 和 beta 的初初值分別為正負無窮大，即雙耍家攏以可能是上低分開始遊戲。佇咧選擇某節點的特定分枝了後，可能發生𨑨迌物仔放心的上細分較細分別別人放心的上大分（beta <=alpha）。這款情形下，父節點無應選擇這个節點，若無父節點分數會降低，所以應該分枝的其他的節點無必要繼續探索。

虛擬碼

下跤為一有限可靠性版本的 Alpha-beta 鉸枝的虛擬代碼：

` ` ` functionalphabeta ( node , depth , α , β , maximizingPlayer ) _ / / node=鋪排，depth=深度，maximizingPlayer=大分𨑨迌的 _ ifdepth=零ornode 是被五節點 return節點的啟發值 ifmaximizingPlayer v :=-∞ for每個子節點 v :=max ( v , alphabeta ( child , depth-一 , α , β , FALSE ) ) _ / / child=子節點 _ α :=max ( α , v ) ifβ ≤ α break_ / / β 裁剪 _ returnv else v :=∞ for每個子節點 v :=min ( v , alphabeta ( child , depth-一 , α , β , TRUE ) ) β :=min ( β , v ) ifβ ≤ α break_ / / α 裁剪 _ returnv ` ` `

` ` ` _( \ * 初初咧調用 \ * )_ alphabeta ( origin , depth ,-∞ , + ∞ , TRUE ) _ / / origin=初節點 _ ` ` `

佇這个有限可靠性的 alpha-beta 中，當 v 調用參數 α 和 β 構成的集合的時陣（v < α 抑是 v > β）， alphabeta 函式返回值 v。若佮這相對來講，強化的有限可靠性 alpha-beta 限制函式倒轉來佇 α 佮 β 包括範圍中的值。

參考文獻

George T . Heineman , Gary Pollice , and Stanley Selkow . Chapter 七 : Path Finding in AI . Algorithms in a Nutshell . Oreilly Media . 兩千空八 : 兩百十七喔–兩百二十三 . ISBN 九百七十八追空抹五百九十六知五一千六百二十四含六 .
Judea Pearl , _ Heuristics _ , Addison-Wesley , 一千九百八十四
John P . Fishburn . Appendix A : Some Optimizations of α-β Search . Analysis of Speedup in Distributed Algorithms ( revision of 一千九百八十一 PhD thesis ) . UMI Research Press . 一千九百八十四 : 一百空七爿一百一十一 . ISBN 空九八千三百五十七石一千五百二十七石二 .

外部連結

http : / / www . emunix . emich . edu / ~ evett / AI / AlphaBeta \ _ movie / sld 一 . htm
http : / / sern . ucalgary . ca / courses / CPSC / 五百三十三 / W 九十九 / presentations / L 一 \ _ 五 B \ _ McCullough \ _ Melnyk /
http : / / sern . ucalgary . ca / courses / CPSC / 五百三十三 / W 九十九 / presentations / L 二 \ _ 五 B \ _ Lima \ _ Neitz / search . html
https : / / web . archive . org / web / 二十五空二百十二岫兩千三百十二岫空三千三百五十九 / http : / / www . maths . nott . ac . uk / personal / anw / G 十三 GAM / alphabet . html
https : / / web . archive . org / web / 二十五空四百一十一孵兩千三百空六鼻一千空四十四 / http : / / chess . verhelst . org / search . html
http : / / www . frayn . net / beowulf / index . html
http : / / hal . inria . fr / docs / 十二分之零 / 十六分之十五 / PDF / RR 抹六千空六十二 . pdf
Minimax ( with or without alpha–beta pruning ) algorithm visualization-game tree solving ( Java Applet ) , for balance or off-balance trees
Demonstration / animation of minimax game search algorithm with alpha–beta pruning ( using html 五 , canvas , javascript , css )
Java implementation used in a Checkers Game