Winning & losing positions
Impartial games, normal play, and computing W/L positions bottom-up. · 10 min read
Impartial games
An impartial game is a two-player, perfect-information game where the available moves depend only on the position, not on whose turn it is (so both players have the same options). Under normal play, the player who cannot move loses. Many take-away and stone games fit this mould.
Winning and losing positions
Label every position W (the player to move can force a win) or L (the player to move will lose against best play). Two rules define them:
- A position with no moves is L (you just lost).
- A position is W if some move leads to an L position (hand the loss to your opponent).
- A position is L if every move leads to a W position.
The subtraction game
From a pile of n stones, each move removes a count in a fixed set (e.g. {1, 2}); last to move wins. Compute W/L bottom-up from 0. With moves {1, 2}, the pattern is L, W, W, L, W, W, … — you lose exactly when n is a multiple of 3.
Interactive visualization: Win/Lose positions filled from the terminal state — step through it frame by frame on this page.
win[0] = L— No move ⟹ you lose.win[i] = W if any win[i−m] = L— You can hand your opponent a loss.otherwise win[i] = L— Every move helps the opponent.
Result: O(n · |moves|)
Practice: Subtraction Game (Medium) — Win/Lose DP: can the first player win from n with allowed moves?