Minimax算法（亦稱 MinMax or MM）又名極小化極大算法，是一種找出失敗的最大可能性中的最小值的算法。
基本介紹
- 中文名：極小化極大算法
- 外文名：Minimax算法
- 別名：MinMax or MM
介紹,基本算法思想,算法最佳化,偽代碼,
介紹
Minimax算法常用於棋類等由兩方較量的遊戲和程式。該算法是一個零總和算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，另一方則選擇令對手優勢最小化的方法。而開始的時候總和為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 α