Combinatorial Game Theory
who wins, and by how much
Series

Periodicity — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    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.

    part 1 · complexity
  2. 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.

    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.

    part 2 · history
  3. Which bit of the rule decides. Four properties of an octal rule table set against whether the game it describes settles into a period. Only one holds on every code that does not: whether a move may leave two non-empty heaps. It is necessary and not sufficient.

    Three bits of rule

    An octal code is three bits a digit. The Grundy sequence it determines costs anywhere from one bit to a hundred and thirty-six — a factor of two hundred and seventy-two across rules that differ by a single digit — or it cannot be written down at all. Of four properties of the rule table tested against that, exactly one holds on every code that never settles: whether a move may leave two non-empty heaps. It is necessary, it is not sufficient, and nine codes carry it and produce answers smaller than their own rules.

    part 3 · history
  4. Right for five hundred heaps before it can be known. The Grundy sequence of the octal game ·45 read one heap at a time, with the period a sweep would report at each depth. False readings of period 1 and period 20 come and go until depth 538, after which the reading is period 20 from heap 498 for good; the periodicity theorem's window does not close until depth 1038.

    A repetition is a guess

    Read an octal game's values one heap at a time and report the first pattern that fits, and the report is a guess that changes. Over the 291 short octal codes whose period can be proved, the guess is wrong 4,684 times before it settles; on ·45 it changes 181 times, is right from heap 538 and cannot be proved until heap 1,038. No false guess ever reaches the window that would certify it — the furthest gets 74 per cent of the way — and no fixed number of repetitions is a safe substitute, because the window asks for as many as the period's late start requires: two on some codes, twenty-seven on ·45.

    part 4 · complexity
  5. A saltus found, and none on offer. Two Grundy sequences read heap by heap for an arithmetic period. The hexadecimal code ·28 is read 71 wrong ways and then, from depth 107, as period 53 with saltus 16 for good. The octal code ·6, whose values also grow, is read 1128 ways in 1,200 heaps and every reading breaks within a few periods.

    Growing is not climbing

    The octal codes whose values grow were expected to be arithmetically periodic — repeating with a constant added each period — and to fool a reader with false climbs. Read for that pattern, the 220 octal codes of up to three digits with no certified period produce 246,048 readings in 1,200 heaps and not one holds for more than six periods. The false climbs are exactly as short as on the hexadecimal codes where the climb is real; the difference is that no right reading ever arrives, and the largest values grow more slowly than any constant climb allows.

    part 5 · complexity

All series