跳转到内容

极小化极大算法

本页使用了标题或全文手工转换
维基百科,自由的百科全书
(重定向自Minimax

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

参考文献

  1. ^ Provincial Healthcare Index 2013页面存档备份,存于互联网档案馆) (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)

外部連結