極小化極大演算法

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-)

外部連結

編輯