Combinatorial Game Theory
who wins, and by how much
Field

Impartial games

Both players have the same moves. Every such position is a Nim heap, and the theorem that says so is the field's first.
301151017111nim-sum001= 1some column does notthe player to move winstake 1 from the heap of 3outcome N

Nim, and the nim-sum

Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.

 a heap of 10, taking 1, 3, 4options lead to heaps of 9, 7, 6whose values are 0, 0, 2mex of those is 1plays exactly likea Nim heap of 1= ∗the value is the heap size — nothing else about the position survives

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.

 001230412308123012123016123020123024heap size, and the value of a heap that bigperiod 4, from heap 0a heap of size n is worth ∗g(n) — and the whole game is the nim-sum of its heaps

Grundy sequences, and where they stop being predictable

Computing one Grundy value is a mex. Computing all of them produces a sequence, and the sequences do something nobody has fully explained — most of them eventually repeat, some of them take thousands of terms to start, and for a few nobody knows whether they ever do.

All essays