Combinatorial Game Theory
who wins, and by how much
Concept

Take-and-break — where it appears

The family of impartial games in which a move removes counters and may split what is left, which octal codes describe. Whether a rule table's sequence has a closed form is not predicted by anything anybody has found in the table.

Named by 8 essays across one field — each of them below, with the objects they name alongside it.

The octal game ·137, read out. An octal code is a rule table. The kth digit says what a player may do after taking k tokens from one heap: end that heap, leave one heap, or split the rest into two. Three bits, one digit, and the whole family of take-away games becomes something that can be listed and swept.

Naming a game with a number

An octal code is a rule table compressed into an integer. It turns "which game" into something that can be counted through, which is how the family was swept — and how the games nobody can solve were found.

impartial · Grundy sequences How many different values a Grundy sequence has used. One curve per octal code: the number of distinct Grundy values among the first n heaps. A periodic game runs out of values and its curve levels off. The codes nobody has settled are still climbing at six thousand heaps.

The values that keep arriving

A Grundy sequence that repeats uses finitely many values and stops needing new ones. Six thousand heaps into ·007 the count of distinct values is 187 and still climbing, and the share of heaps carrying something outside the twenty-two commonest rises from 32% in the first thousand to 85% in the sixth. The rare values a periodicity argument needs to thin out are getting commoner.

impartial · Sparse space 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.

impartial · Lasker Twenty-two codes, swept to 600 heaps. Octal codes and hexadecimal ones under the same search, which looks for a period and for a period with a constant added. The second kind occurs only in the wider family here, and a search that looks only for plain repetition reports those sequences as unsettled.

A period with a constant added

An octal code says what a player may do when removing k counters, in three bits; a hexadecimal code adds a fourth — leave three heaps — and the digits run to fifteen. Over twenty-two codes swept to six hundred heaps, five hexadecimal ones repeat with a fixed amount added each time round and no octal one does. Their values climb for ever and never repeat, so a search that looks only for repetition reports them unsettled.

impartial · Hexadecimal Two counters, not one. The four periods of the odd-saltus class against the two base-three counters, with which each follows.

Two counters, and one displaced term

The rung below found four Grundy sequences in the odd-saltus class and asked which term each displaces and whether the digits predict it. They do — but there are two base-three counters and not one, chosen by whether a heap of one can be taken away. And there are three sequences rather than four: the fourth is the third with three isolated values, and was counted separately because its period had not settled.

impartial · Hexadecimal 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.

impartial · Lasker 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.

impartial · Lasker 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.

impartial · Lasker

Named alongside it

The objects these essays reach for when they reach for this one.

Grundy valueClosed formImpartialMexOctal gamePeriodicityEventual periodicityExhaustive searchGrundy sequencesNim-sumOctal codeEnumeration

All concepts