極小化極大演算法

Minimax演算法（亦稱 MinMax or MM）又名極小化極大演算法，是一種找出失敗的最大可能性中的最小值（最小化最壞情況）的演算法。

概述

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

外部連結

• 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 （頁面存檔備份，存於網際網路檔案館）