Combinatorial Game Theory
who wins, and by how much
Concept

Octal code — where it appears

A string of digits naming a take-and-break game by saying, for each number of counters removed, how many heaps a move may leave. It makes a whole family of games enumerable, so a claim can be checked across dozens of rule tables rather than on one.

Named by 7 essays across 2 fields — 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 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 The genus of a sum. Every pair of heaps up to 9 counters, from nine impartial games, filed by the genus symbols of its two parts. The claim under test is that the file determines the answer; it does, and neither half of the symbol determines it alone.

The genus of a sum

A genus symbol is meant to be carried one per heap, so that a solver never has to look at the heap again. That is a claim that the pair of symbols determines the sum's, and across nine games and 405 pairs it holds without exception — while the bases alone determine it in only 38 of 50 cases and the superscripts alone in 70 of 74. Both halves of the symbol are load-bearing, and two wild heaps can add to a tame sum.

limits · Genus How two genus symbols make a third. The composition rule for genus symbols, stated with its cases and checked on every pair of heaps of nine games. The base exclusive-ors, the sum is fickle only when every component is, and the symbol follows from those two.

The rule the symbols follow

Two genus symbols make a third by three lines and no lookup table: the base exclusive-ors, the sum is fickle only when every component is, and the symbol follows. Checked on 252 pairs across nine games it is right on 238 — and the fourteen failures are exactly the fourteen pairs with a wild heap in them, which is the boundary the genus is defined up to arriving as a measurement.

limits · Genus Every saltus in the two-digit family. The constant added each time round, over all 255 two-digit hexadecimal codes. Forty-eight codes add one, thirteen add two, six add four and three add sixteen — and one code adds three.

A code that climbs by three

Five hexadecimal codes were known to repeat with a constant added, and every one of the five constants was a power of two — either a fact about exclusive-or or a coincidence over five cases. Sweeping all 255 two-digit codes settles it: seventy-one climb, seventy of them by 1, 2, 4 or 16, and one by three. The exception is ·3f, whose values are 3⌊n/6⌋ + (n mod 3) on every heap to twelve hundred.

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

Exhaustive searchGrundy valueOctal gamePeriodicityRule tableClosed formEventual periodicityGrundy sequencesTake-and-breakImpartialMexMisère play

All concepts