Combinatorial Game Theory
who wins, and by how much
Generator

6 octal games, and which of them settle

6 octal games, and which of them settle
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.

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.

11 essays call octal-survey. 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

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

PositionWorth OutcomeDrawn in
·8f, a heap of 0 0 P A period with a constant added · A code that climbs by three
·8f, a heap of 1 0 P A period with a constant added · A code that climbs by three
·8f, a heap of 2 ∗1 N A period with a constant added · A code that climbs by three
·8f, a heap of 3 ∗1 N A period with a constant added · A code that climbs by three

Where it is called

Changing this generator changes every one of these figures.

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

 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.

 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.

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

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.

 Climbing is the ordinary case. The two-digit and three-digit hexadecimal families, each swept for exact and arithmetic periodicity. Seven in ten of the settled three-digit codes repeat with a constant added. Impartial games

The third digit

The rung below found 71 of the 255 two-digit hexadecimal codes repeating with a constant added rather than exactly, and asked whether the same share holds one digit wider. It rises. Of the 4,095 three-digit codes, 1,433 climb and 617 repeat exactly — seven in ten of the settled ones — so a saltus is the ordinary way a hexadecimal game settles and the exact repetition the octal survey was built to find is the special case.

 The digits they share. The condition satisfied by eighteen of the nineteen codes that climb by three. It says that splitting a heap into three is available on exactly one take and buys nothing else. Impartial games

The only way to split into three

Nineteen three-digit hexadecimal codes climb by three, and the rung below asked whether they share a form and what digits they have in common. The digits are exact: on eighteen of them the only way to split a heap into three is by taking exactly three counters, and taking three counters can do nothing else. The form is not shared — the eighteen carry four distinct sequences, and exactly one of the four counts in base three.

 Two counters, not one. The four periods of the odd-saltus class against the two base-three counters, with which each follows. Impartial games

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.

 Not rare at all. How many hexadecimal codes whose sequence settles have a stretch of heaps before the pattern begins. Impartial games

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.

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

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.

 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. How it was found

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.

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