Combinatorial Game Theory
who wins, and by how much
Series

Sprague–Grundy — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Every impartial position is a Nim heap. A heap in a subtraction game, its Grundy value, and the Nim heap it is equivalent to. The equivalence is exact: the two positions have the same options up to value, so they behave identically in any sum, which is the Sprague–Grundy theorem.

    Every impartial game is a Nim heap

    Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.

    part 1 · impartial
  2. Turning Turtles: a row of 12 coins. A row of coins, some heads and some tails. A move turns some of them over, and the rightmost coin turned must go from heads to tails — which is what makes the game end. The number under each place is what a lone head there is worth, and the row is worth the exclusive or of the places showing heads.

    A row of coins is already a sum

    Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.

    part 2 · impartial
  3. The mex, and the rules that cannot replace it. Six candidate rules for the value of an impartial position, each a function of its options' values, run over the same subtraction game. The top strip is the truth. Every candidate but the mex assigns zero to a position somebody wins, or a non-zero value to a position somebody loses, and the circle marks the first heap where each one does it — which is why two people reaching for the same rule four years apart is evidence about the rule rather than about them.

    Two people, four years apart, one theorem

    Roland Sprague proved it in 1935 and Patrick Michael Grundy proved it in 1939, neither knowing of the other. That looks like coincidence until the alternatives are examined — and the rule they both reached turns out to be the only one that can work at all.

    part 3 · history
  4. Three partizan positions against every nimber, and not one match. Sprague and Grundy give every impartial position a single number that is complete: two positions with the same value are interchangeable everywhere. The three positions here are partizan — the two players have different moves — and each is compared against every nimber up to eight. Nothing is equal to anything. The magenta cells are worse than inequality: a position confused with a nimber is not above it or below it either, so no ordering could rescue the substitution.

    Where the impartial theory stops

    Sprague–Grundy gives every impartial position one number, and the number is complete. The moment the two players have different moves no number works at all — not a harder one to compute, none — and three positions here are compared against every nimber to show it.

    part 4 · sums

All series