TaiwanTonguesApiRobot：從 JSON 檔案批量匯入

2025-08-22T03:04:13Z

從 JSON 檔案批量匯入

新頁面

'''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 鉸枝的虛擬代碼：

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

` ` `
_'''( \ * 初初咧調用 \ * )'''_
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

[[分類: 待校正]]

Alpha-beta鉸枝 - 修訂紀錄

TaiwanTonguesApiRobot：​從 JSON 檔案批量匯入

TaiwanTonguesApiRobot：從 JSON 檔案批量匯入