Combinatorial Game Theory
who wins, and by how much
Generator

Grundy values for subtraction of 1, 2, 3

Grundy values for subtraction of 1, 2, 3
Grundy values for subtraction of 1, 2, 3. 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 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.

21 essays call grundy-strip. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

7 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
a heap of 0 0 P A period with a constant added · Grundy sequences, and where they stop being predictable · Splitting is a move · The formula is a limit
a heap of 11 ∗12 N Splitting is a move · The proof is sixteen cells
a heap of 12 ∗11 N Splitting is a move · The proof is sixteen cells
a heap of 3 ∗4 N A period with a constant added · Grundy sequences, and where they stop being predictable · Splitting is a move · The formula is a limit
a heap of 4 ∗3 N A period with a constant added · Grundy sequences, and where they stop being predictable · Splitting is a move · The formula is a limit
a heap of 7 ∗8 N A period with a constant added · Grundy sequences, and where they stop being predictable · One split is enough · Splitting is a move · The formula is a limit · The proof is sixteen cells
a heap of 8 ∗7 N Splitting is a move · The proof is sixteen cells

Where it is called

Changing this generator changes every one of these figures.

Every impartial position is a Nim heap. A heap in a subtraction game, its Grundy value, and the Nim heap it is equivalent to. The equivalence is exact: the two positions have the same options up to value, so they behave identically in any sum, which is the Sprague–Grundy theorem. Impartial games

Every impartial game is a Nim heap

Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.

 Grundy values for subtraction of 1, 2, 3. 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. Impartial games

Grundy sequences, and where they stop being predictable

Computing one Grundy value is a mex. Computing all of them produces a sequence, and the sequences do something nobody has fully explained — most of them eventually repeat, some of them take thousands of terms to start, and for a few nobody knows whether they ever do.

 The misère quotient of Nim, heaps up to 2. Each row and column is a class of positions that no sum in this universe can tell apart, and each entry is the class their sum falls into. The shaded classes are the ones a player wants to hand over. Under normal play the same positions need only the Nim values; the extra classes here are what misère play costs. Where it stops

What survives misère play

Misère play destroys the value theory, and something much smaller grows back. Fix one game, look only at sums of its own positions, and the classes that behave alike form a monoid — computed here, and larger than the normal-play answer every time.

 What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut. What it costs

The game with the shortest rule is the hard one

Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.

 The mex, and the rules that cannot replace it. Six candidate rules for the value of an impartial position, each a function of its options' values, run over the same subtraction game. The top strip is the truth. Every candidate but the mex assigns zero to a position somebody wins, or a non-zero value to a position somebody loses, and the circle marks the first heap where each one does it — which is why two people reaching for the same rule four years apart is evidence about the rule rather than about them. How it was found

Two people, four years apart, one theorem

Roland Sprague proved it in 1935 and Patrick Michael Grundy proved it in 1939, neither knowing of the other. That looks like coincidence until the alternatives are examined — and the rule they both reached turns out to be the only one that can work at all.

 A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values. How it was found

A golden ratio thirty years early

Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

 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. Impartial games

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.

 6 octal games, and which of them settle. Each row is an octal game: its code, the moves it allows, the first two dozen Grundy values, and whether a period was found in the values computed here. Guy and Smith surveyed these by hand in 1956 and conjectured that every finite octal game is eventually periodic. Seventy years and a great deal more arithmetic later, the rows in magenta are the state of that conjecture — not counterexamples, but sequences in which nothing periodic has yet appeared. How it was found

The sequence nobody has settled

Guy and Smith surveyed the octal games by hand in 1956 and conjectured that every finite one is eventually periodic. Seventy years and a great deal more arithmetic later, some of them have settled and some have not — and the evidence for the conjecture is entirely that nobody has found a counterexample they were looking for.

 Grundy values for subtraction of 1, 3, 4. 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. Impartial games

Take one, three or four

A heap and a list of legal takes. It is the smallest interesting impartial game there is, and the only family in the subject where eventual periodicity is not observed, not conjectured, but guaranteed — with a bound on when it must appear.

 Subtraction of 1, 3, 4 — and the window that proves the period. The Grundy values of a subtraction game, with the window that certifies the period marked. Everything after the window follows from it by induction, because a value is a mex over values at most one move back — so a finite check settles the whole infinite sequence, and the thousands of further values computed here agree with a claim that was already proved. What it costs

Four values, and the sequence is settled for ever

The Grundy values of a subtraction game repeat with period 7, and proving it needs a window of exactly four of them — one for each size of move the game allows. Everything past the window follows by induction. A finite computation has settled a claim about every heap there will ever be.

 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. Impartial games

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.

 Cram on 4 by 4: the pairing strategy. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements. Impartial games

Cram

Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.

 Swapping a branch for another of the same value. The ordinal sum of a base with a branch, and the same sum with the branch replaced by a heap of a different game carrying the same Grundy value. The two are compared by playing their difference, not by inspection — and they agree every time, which is what the colon principle claims and what the partizan case denies. Sums and comparison

When the nested sum only sees the value

The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.

 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. Impartial games

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.

 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. Impartial games

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.

 Every heap up to 40, won or lost. Heap sizes with the outcome for the player who moves first. The lost ones are shaded; they are exactly the Fibonacci numbers, which is a fact about a game with one heap, no board and no geometry in it anywhere. Impartial games

The heap is not the position

Fibonacci Nim bounds a move by twice the previous move, which puts the state outside the board: a heap of six with a cap of two and a heap of six with a cap of five are different games. So there is nothing to add and no Grundy value to compute — and the game is completely solved anyway. The opener loses on exactly the nine Fibonacci numbers up to 120, and the smallest term of the Zeckendorf numeral is a winning move in all 110 winnable heaps.

 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. Impartial games

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.

 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. Particular games

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.

 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. Impartial games

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.

 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. Impartial games

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.

 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. Impartial games

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.

The whole library · The position index · The figures that play back