-
極小化極大算法
鎖定
Minimax算法（亦稱 MinMax or MM）又名極小化極大算法，是一種找出失敗的最大可能性中的最小值的算法。
- 中文名
- 極小化極大算法
- 外文名
- Minimax算法
- 別 名
- MinMaxorMM
極小化極大算法介紹
Minimax算法常用於棋類等由兩方較量的遊戲和程序。該算法是一個零總和算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，另一方則選擇令對手優勢最小化的方法
[1]
。而開始的時候總和為0。很多棋類遊戲可以採取此算法，例如井字棋（tic-tac-toe）。
極小化極大算法基本算法思想
極小化極大（minimax）算法顧名思義，就是讓最大得情況最小，這裏的最大一般是指最差的情況，比如遊戲中最不利的情況。
該算法需要滿足零和博弈，初略的解釋就是若有兩個玩家進行遊戲，如果其中一方得到利益那麼另一方就會失去利益，遊戲利益的總和為0（某些情況下為常數）。
因此，零和的約束條件也使得該算法在很多遊戲中圖體現出很好的效果，比如大多數的棋類遊戲。
其實説白了，這個算法就是一個樹形結構的遞歸算法，每個節點的孩子和父節點都是對方玩家，所有的節點被分為極大值（我方）節點和極小值（對方）節點。
極小化極大算法算法優化
α-β剪枝算法
在上述的極大極小算法中，MIN和MAX過程將所有的可能性省搜索樹，然後再從端點的估計值倒推計算，這樣的效率非常低下。而α-β算法的引入可以提高運算效率，對一些非必要的估計值進行捨棄。其策略是進行深度優先搜索，當生成結點到達規定深度時，立即進行靜態估計，一旦某一個非端點的節點可以確定倒推值的時候立即賦值，節省下其他分支拓展到節點的開銷。
剪枝規則：
（1）α剪枝，任一極小層節點的β值不大於他任一前驅極大值層節點的α值，即α（前驅層）≥β（後繼層），則可以終止該極小層中這個MIN節點以下的搜索過程。這個MIN節點的倒推值確定為這個β值。
（2）β剪枝，任一極大層節點的α值不小於它任一前驅極小值層節點的β值，即β（前驅層）≤α（後繼層），則可以終止該極大值層中這個MAX節點以下的搜索過程。這個MAX節點的倒推值確定為這個α值。
極小化極大算法偽代碼
function minimax(node, depth)
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
let α := +∞
foreach child of node
α := min(α, minimax(child, depth-1))
else {we are to play at node}
let α := -∞
foreach child of node
α := max(α, minimax(child, depth-1))
return α
- 參考資料
-
- 1. 基於極小化極大算法的正射影像鑲嵌線搜索 ．知網[引用日期2018-07-07]
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：4次歷史版本
- 最近更新： tujiaqi大本营