极小化极大算法

Minimax算法（亦稱 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。

概述

Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。

伪代码

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 α

外部連結

• 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