极小化极大算法

Minimax算法（亦稱 MinMax or MMProvincial Healthcare Index 2013  (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)）又名极小化极大算法，是一种找出失败的最大可能性中的最小值（最小化最坏情况）的算法。

 概述 
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

 参考文献 

外部連結

 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 

Category:检测论
Category:游戏人工智能
Category:图算法
Category:最优化算法
Category:搜尋演算法
Category:博弈论
Category:数理与定量方法 (经济学)
Category:离散数学定理
Category:决策论
Category:不动点
Category:带有伪代码示例的条目