Combinatorial Game Theory
who wins, and by how much
Series

Lasker — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Three take-and-break games, three kinds of answer. The Grundy sequences of Nim, Lasker's Nim and Kayles over the first heaps. Adding a move that removes nothing takes Nim's sequence from the identity to a four-line formula; bounding how much may be taken instead takes it somewhere with no formula at all.

    Splitting is a move

    Add to Nim a move that removes nothing — break a heap in two — and the Grundy sequence gets simpler, not harder. Lasker's Nim has a closed form with one clause per residue modulo four, exact on all 2,001 heaps checked: the identity with every fourth pair transposed. Kayles is the same kind of game with the taking bounded instead of the splitting, and it has no closed form at all, settling into a period of twelve only from heap 71 with fourteen values outside it for ever.

    part 1 · impartial
  2. Lasker's Nim in sixteen cells. A four-by-four table. Each row and column is a residue mod 4 of one part of a split heap, with the residue of that part's Grundy value beside it; each cell is the residue mod 4 of the split's value, the nim-sum of the two parts. Every split of every heap to four hundred lands in the cell its residues name.

    The proof is sixteen cells

    Lasker's Nim has a four-clause formula that was checked on two thousand heaps and never proved. The proof fits in a four-by-four table: the last two bits of a split's value are fixed by the last two bits of its parts, so no split can land in its own heap's class — except at 3 mod 4, where it lands exactly on the one value the takes leave missing and pushes the answer up by one.

    part 2 · impartial
  3. One split is enough, and some are not. Lasker's Nim beside five versions of it that allow only some splits, over the first twenty-four heaps, with every cell that leaves the formula outlined. Allowing only the split that takes one counter off reproduces the whole sequence; allowing only equal halves turns it back into Nim.

    One split is enough

    A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.

    part 3 · impartial
  4. The formula as the limit of periodic games. Lasker's Nim above eight versions of it with the number of counters that may be taken bounded at one to eight. Each bounded game is periodic and agrees with Lasker's formula on its first few heaps; the region of agreement grows with the bound.

    The formula is a limit

    Cap the take in Lasker's Nim at k counters and the game is a finite rule table, 4.33…3, whose Grundy sequence repeats with period k + 1 rounded up to even and follows Lasker's formula until the cap bites. The formula is what those periods converge to. And the same column of codes, with a free split in front, holds Kayles itself: the rule 4.4 on a heap of n + 1 is Kayles on a row of n.

    part 4 · impartial

All series