Minimax Algorithm

Minimax Value

The minimax value of a node is the utility value achievable by the MAX player against an optimal MIN player:

MINIMAX(s) =
    UTILITY(s)                                    if IS-TERMINAL(s)
    max over a in ACTIONS(s) of MINIMAX(RESULT(s,a))   if TO-MOVE(s) = MAX
    min over a in ACTIONS(s) of MINIMAX(RESULT(s,a))   if TO-MOVE(s) = MIN

Intuition: MAX chooses the move that maximizes the value; MIN chooses the move that minimizes the value. Both play optimally.

Algorithm

function MINIMAX-SEARCH(game, state) returns an action
    player ← TO-MOVE(state)
    value, move ← MAX-VALUE(game, state)
    return move

function MAX-VALUE(game, state) returns (utility, move)
    if IS-TERMINAL(state) then return UTILITY(state, player), null
    v ← -∞
    for each a in ACTIONS(state) do
        v2, a2 ← MIN-VALUE(game, RESULT(state, a))
        if v2 > v then
            v, move ← v2, a
    return v, move

function MIN-VALUE(game, state) returns (utility, move)
    if IS-TERMINAL(state) then return UTILITY(state, player), null
    v ← +∞
    for each a in ACTIONS(state) do
        v2, a2 ← MAX-VALUE(game, RESULT(state, a))
        if v2 < v then
            v, move ← v2, a
    return v, move

Worked Example

         MAX
        /   \
      3       MIN
             /   \
           MAX   MAX
          / \   / \
         3   5  2  9

MIN at right chooses min(MAX(3,5), MAX(2,9)) = min(5,9) = 5. MAX at root chooses max(3, 5) = 5. Root value = 5.

Actually for the canonical 3-node example:

       MAX
      / | \
    MIN MIN MIN
   /|\ /|\ /|\
  3 12 8 2 4 6 14 5 2

MIN values: min(3,12,8)=3, min(2,4,6)=2, min(14,5,2)=2 MAX value: max(3,2,2) = 3

Properties

Where b = branching factor, m = maximum depth.

For chess: O(35^80) — completely intractable without pruning or depth limits.

Optimality Against a Suboptimal Opponent?

Minimax is optimal against an optimal opponent.

Against a suboptimal opponent, minimax is still correct (never worse), but it may not be the best strategy — exploiting opponent mistakes could yield higher utility.

Example: If opponent never takes the queen, optimal play against that opponent would deliberately leave the queen en prise. Minimax won’t do this (it assumes opponent plays perfectly).

Multi-Player Generalization

For n players, each node stores a utility vector (one value per player). Each player maximizes their own component. No longer zero-sum → coalitions may form.

MINIMAX(s) =
    UTILITY-VECTOR(s)                if terminal
    argmax over player(s)'s component  of MINIMAX(RESULT(s,a))   otherwise

Connection to Backward Induction

Minimax = backward induction from game theory: work backward from terminal states, assigning optimal strategies at each node. The resulting strategy profile is a subgame perfect Nash equilibrium — neither player benefits from deviating at any subgame.