Minimax for two-player games

The minimax procedure

For a two-person, zero-sum game (one player's gain is the other's loss), minimax assumes both sides play optimally. The two players are MAX, who tries to *maximize* the evaluation, and MIN, who tries to *minimize* it. Label the game tree with alternating MAX and MIN levels:

- Leaf nodes get an actual or heuristic value (here: $+1$ if MAX wins, $-1$ if MIN wins, $0$ for a draw). - A MAX node takes the maximum of its children's backed-up values. - A MIN node takes the minimum of its children's backed-up values.

Values propagate up to the root. The root value is the best outcome MAX can guarantee, *assuming MIN also plays optimally*. That optimality assumption is both the strength (a rational guarantee) and the limit (an irrational opponent may behave differently) of minimax.

n-ply look-ahead and the horizon effect

Real games are too large to search to the end, so programs search n plies deep, apply a heuristic to the leaves, and back the values up. Deeper usually plays better — but not always, and a fixed depth creates the horizon effect: a disaster lurking one ply *beyond* the cutoff is invisible, so the program may walk into it (e.g. accept a piece that lures it into losing a bigger one). *Quiescence* / selective deepening (search a few extra plies for volatile positions) softens this but cannot remove it.

Worked example: tic-tac-toe

Encode the board as 9 cells; X is MAX, O is MIN. On a mid-game board where it is X's turn and taking the centre forces a win, minimax recurses to terminal positions, backs up $+1/-1/0$, and returns best move (2,2), value +1 (X wins). On an empty board, optimal play by both sides is a draw, so the root value is $0$ — minimax correctly reports tic-tac-toe as a draw under perfect play. The chosen move is the child that achieves the backed-up root value.