function MINIMAX-DECISION(state) returns an action
return arg max a ∈ ACTIONS(s) MIN-VALUE(RESULT(state, a))
function MAX-VALUE(state) returns a utility value
if TERMINAL-TEST(state) then return UTILITY(state)
v ← −∞
for each a in ACTIONS(state) do
v ← MAX(v, MIN-VALUE(RESULT(state, a)))
return v
function MIN-VALUE(state) returns a utility value
if TERMINAL-TEST(state) then return UTILITY(state)
v ← ∞
for each a in ACTIONS(state) do
v ← MIN(v, MAX-VALUE(RESULT(state, a)))
return v
Figure ?? An algorithm for calculating minimax decisions. It returns the action corresponding to the best possible move, that is, the move that leads to the outcome with the best utility, under the assumption that the opponent plays to minimize utility. The functions MAX-VALUE and MIN-VALUE go through the whole game tree, all the way to the leaves, to determine the backed-up value of a state. The notation argmax a ∈ S f(a) computes the element a of set S that has maximum value of f(a).
function EXPECTIMINIMAX(s) =
UTILITY(s) if TERMINAL-TEST(s)
maxa EXPECTIMINIMAX(RESULT(s, a)) if PLAYER(s)= MAX
mina EXPECTIMINIMAX(RESULT(s, a)) if PLAYER(s)= MIN
∑r P(r) EXPECTIMINIMAX(RESULT(s, r)) if PLAYER(s)= CHANCE