極小化極大演算法
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
Minimax演算法(亦稱 MinMax or MM[1])又名極小化極大演算法,是一種找出失敗的最大可能性中的最小值(最小化最壞情況)的演算法。
概述
Minimax演算法常用於棋類等由兩方較量的遊戲和程式。該演算法是一個零總和演算法,即一方要在可選的選項中選擇將其優勢最大化的選擇,另一方則選擇令對手優勢最小化的方法。而開始的時候總和為0。很多棋類遊戲可以採取此演算法,例如井字棋(tic-tac-toe)。
偽代碼
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
參考文獻
- ^ Provincial Healthcare Index 2013 (頁面存檔備份,存於互聯網檔案館) (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)
外部連結
- Hazewinkel, Michiel (編), Minimax principle, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- A visualization applet (頁面存檔備份,存於互聯網檔案館)
- Maximin principle at Dictionary of Philosophical Terms and Names
- Play a betting-and-bluffing game against a mixed minimax strategy (頁面存檔備份,存於互聯網檔案館)
- Minimax (頁面存檔備份,存於互聯網檔案館) at Dictionary of Algorithms and Data Structures
- Minimax (頁面存檔備份,存於互聯網檔案館) (with or without alpha-beta pruning) algorithm visualization — game tree solving (Java Applet), for balance or off-balance trees.
- Minimax Tutorial with a Numerical Solution Platform (頁面存檔備份,存於互聯網檔案館)
- Java implementation used in a Checkers Game (頁面存檔備份,存於互聯網檔案館)
|