Combinatorial Game Theory
who wins, and by how much
Concept

Eventual periodicity — where it appears

Repeating for ever after some initial stretch, which is a theorem for subtraction games and a conjecture for octal ones. For subtraction games it is a theorem with a bound, and for octal games it is neither.

Named by 13 essays across 5 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 Grundy values for subtraction of 2, 5, 7. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none.

The period is small and the proof does not say so

Every subtraction game repeats eventually — that is a theorem, and its proof gives a bound of sixteen thousand for a three-move set. Over 112 sets the longest period measured is twenty-two. The proof and the fact are four orders of magnitude apart, and the rule of thumb that closes the gap is broken by one set in the sweep.

impartial · Subtraction 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 What each heap is worth. The value of a single heap of each size. Nothing here repeats: the forms grow deeper as the heap grows, which is what stops the impartial theory's periodic table from having an analogue.

Two players, two lists

Give each player their own list of how many counters they may take and the impartial theory stops applying. What survives is the outcome: it settles into a repeat, for every pair of lists, and that is a theorem. What does not survive is the value — on four of six pairs swept it has no repeat inside sixty heaps, and the birthdays are still climbing at the edge of the window.

positions · Partizan subtraction 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 A sequence with a rule and no period. The values of the subtraction game with Left taking 1 or 2 and Right taking 1 or 3, from heap 5 up. Each is the game whose only Left option is nought and whose only Right option is the value three heaps below — checked at every heap rather than asserted, and the two heaps where it fails are the two below the seeds.

A sequence with a rule and no period

The values of the subtraction game where Left takes one or two and Right takes one or three never repeat — thirty-one heaps, thirty-one different values. They are nonetheless completely described: three seeds and the rule v(k + 3) = {0 | v(k)} generate every one of them, which is what a pattern without a period looks like.

positions · Partizan subtraction 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 Two conditions, one of which survives. Two candidate conditions on a pair of subtraction lists, scored over all 961 pairs drawn from one to five. Translation holds on 83 pairs and every one of them repeats; all-odd holds on 49 and four of them do not.

The condition that survived the wider sweep

Which pairs of subtraction lists have a value sequence that repeats? Over the 49 pairs drawn from one, two and three, two conditions answer it identically — a translation and all-odd — and both are exactly right. Over the 961 pairs drawn from one to five, all 83 translations still repeat with no exception and four all-odd pairs do not, at heap ninety with a period as long as forty-two. Neither condition is necessary: 104 pairs repeat that satisfy neither.

positions · Partizan subtraction 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 One set, described three ways that share no arithmetic. Wythoff's cold positions can be stated as the Beatty pairs of the golden ratio, as a greedy construction over the integers that mentions no constant, and as a condition on Fibonacci numerals. None of the three consults the game. The fourth column is the game — a mex table over the moves — and all four name the same set of cold pairs over the whole square, which is what the figure counts.

A set with three descriptions, and a function with none

Wythoff's cold positions can be written three ways that share no arithmetic — an irrational constant, a greedy rule, a condition on Fibonacci digits — and all three are exact. The same game's Grundy values have no closed form at all. Both facts are about one table, and the gap between them is the subject.

applied · Wythoff's game What a certificate costs, in units of the one Guy and Smith wrote. Octal codes with the period of their Grundy sequence, the window a proof of that period needs, and the arithmetic each costs — counted as mex operations and exclusive-ors, which are the two things a person computing by hand actually performs. Everything is priced in units of the certificate for Dawson's chess, so the column reads as multiples of one hand computation rather than as a number of operations. Some codes cost tens of times as much, and some have no certificate at all.

What the arithmetic cost in 1956

The rung below ends by respecting a hand computation without pricing it. Priced in the operations a person actually performs, ·137's certificate is 7,919 of them — and the same sweep says ·47's is sixty-three times that, that a splitting move is what makes the cost quadratic, and that seventeen of sixty-four codes have no certificate at any price.

history · Dawson 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 Two heaps and a held pass. Every pair of heaps up to 16 with one pass available that may not be the last move. Filled cells are the pairs the player to move loses: the empty board and the pairs one and two, three and four, five and six, and so on. Outlined cells are the equal pairs Nim calls lost, all of which are wins once the pass is there.

Three heaps and a pass

Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.

limits · Pass

Named alongside it

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

PeriodicityExhaustive searchGrundy valueClosed formGrundy sequencesImpartialOctal gameMexEnumerationSubtraction gameTake-and-breakUnsolved game

All concepts