極小化極大估計亦稱Minimax估計、最小最大估計。
算法,代碼,
算法
極小化極大算法又名Minimax算法，是一種找出失敗的最大可能性中的最小值的算法。Minimax算法常用於棋類等由兩方較量的遊戲和程式，這類程式由兩個遊戲者輪流，每次執行一個步驟。我們眾所周知的五子棋、象棋等都屬於這類程式，所以說Minimax算法是基於搜尋的博弈算法的基礎。該算法是一種零總和算法，即一方要在可選的選項中選擇將其優勢最大化的選擇，而另一方則選擇令對手優勢最小化的方法。
我們知道，常用的博弈算法都是基於搜尋的博弈算法，所有可能的下棋步驟構成一個樹的結構，以Tic-tac-toe（中文稱為井字棋，即兩人輪流在井字棋盤的方格內劃×或〇，誰先將划過的三個方格成一直線或對角線為勝）遊戲為例，下面一幅圖表示了Tic-tac-toe遊戲的前兩步所有可能的步驟。
上圖中第0層為空棋盤，第1層是×方所有可能的步驟，第2層是〇方所有可能的步驟。在第1層，×方需要選擇使其優勢最大的選擇，而在第2層，〇方則需要選擇使×方優勢最小即己方優勢最大的選擇。
Minimax的含義就是極小化對手的最大利益，在上圖中，在第2層〇方一定會選擇使自己優勢最大的選擇，而對於×方需要做的就是選擇〇方最大選擇中的極小值。
代碼
Minimax是一種深度優先搜尋，其用偽代碼表示如下：
- functionminimax(node,depth)
- ifnodeisaterminalnodeordepth=0
- returntheheuristicvalueofnode
- iftheadversaryistoplayatnode
- letα:=+∞
- foreachchildofnode
- α:=min(α,minimax(child,depth-1))
- else{wearetoplayatnode}
- letα:=-∞
- foreachchildofnode
- α:=max(α,minimax(child,depth-1))
- returnα。
