Combinatorial Game Theory
who wins, and by how much
Concept

Grundy sequences — where it appears

The Grundy values of a game's heaps listed by size, whose eventual repetition is the whole question about an octal game. Two positions with the same Grundy value can take very different numbers of moves to play out, which the sequence does not record.

Named by 11 essays across 2 fields — each of them below, with the objects they name alongside it.

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 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 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 Not rare at all. How many hexadecimal codes whose sequence settles have a stretch of heaps before the pattern begins.

A pattern that has not started yet

A pre-period was supposed to be rarer in this family than a defect. Two hexadecimal codes in five have one, 321 have a pre-period longer than their own period, and the code the rung below found slow takes fifty-four heaps to settle rather than two blocks — which is also the account of three defects the rung below recorded and could not explain.

impartial · Hexadecimal One of the two quantities is inert. The candidate predictors of a pre-period's length, each scored by correlation against the measured length.

The quantity that carried nothing

The rung below proposed predicting a pre-period's length from the saltus and the period. The saltus correlates with it at −0.03, which is nothing; the period correlates at 0.77 with a coefficient of one, so a pre-period is about one period long. The digit that predicts whether there is one predicts nothing at all about how long.

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.

PeriodicityOctal gameEventual periodicityExhaustive searchGrundy valueImpartialClosed formEnumerationTake-and-breakCounterexampleMexOctal code

All concepts