Combinatorial Game Theory
who wins, and by how much
Generator

The octal game ·137, read out

The octal game ·137, read out
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.

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.

6 essays call octal-code. 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.

Where it is called

Changing this generator changes every one of these figures.

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.

 The Grundy values of ·137, and the exceptions to its period. An octal game's Grundy sequence, with the periodic part in gold and the exceptions in magenta. The exceptions are the point: a sequence described as eventually periodic contains values that disagree with the value one period later and always will, so the period is a statement about a tail and not about the sequence. The rule used to identify an exception is printed, because published lists of them differ by which convention was used. How it was found

A chess problem that turned out to be an octal game

Dawson posed it in 1934 as a puzzle about pawns. It is the octal game ·137, its Grundy sequence is eventually periodic with period 34 from heap 52 — and the word doing the work in that sentence is eventually, because five values below the start disagree with their repeats and always will.

 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.

 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.

 The same rules under the convention they were posed in. Dawson's chess under misère play, which is how Dawson posed it. Under normal play every position of the game collapses onto one of a handful of nimbers however large the heaps are allowed to get. Under misère play the positions that behave alike form classes whose number grows with the heap limit, and a heap carries a genus rather than a value. The first wild heap is where the two accounts stop resembling each other, and the classification doubles at exactly the limit that admits it. How it was found

The convention Dawson actually used

Dawson published his puzzle as a problem where running out of moves loses you the game, and every compact result about ·137 is about the other convention. Under his own, nine values become a classification that doubles the moment a wild heap enters the range, and a heap stops carrying a number at all.

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