本頁使用了標題或全文手工轉換

極小化極大演算法

維基百科,自由的百科全書
跳至導覽 跳至搜尋

Minimax演算法(亦稱 MinMax or MM[1])又名極小化極大演算法,是一種找出失敗的最大可能性中的最小值的演算法。

概述[編輯]

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 α

註釋[編輯]

  1. ^ Provincial Healthcare Index 2013 (Bacchus Barua, Fraser Institute, January 2013 -see page 25-)

外部連結[編輯]