Combinatorial Game Theory
who wins, and by how much
The collection

Every essay — page 10

One idea per essay, ordered so that the earlier ones set up the later ones — but nothing here depends on being read in sequence.

How it was found

The theory looks inevitable in retrospect and the record says otherwise. The older arguments are run here rather than recounted — and one of them still answers a question nothing since has answered.

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.

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.

6 figures · Dawson Three complete solutions, each asked about the others. Bouton's 1901 criterion for Nim, Wythoff's 1907 description of his own cold positions, Moore's 1910 rule for taking from several heaps, and the Grundy criterion that arrived thirty years later, each checked against the truth on every position of four games. Every one of the old criteria is exact about its own game and wrong about the others. The blanks matter more than the numbers: Wythoff's is a description of a pair and has no form for three heaps at all, and the Grundy criterion has no form for a game whose moves touch several heaps at once.

Three complete solutions in nine years

Bouton in 1901, Wythoff in 1907, Moore in 1910 — three airtight solutions of three games, all published before there was any theory of games at all. Asked about each other's games they all fail, and two of them fail by being wrong while one fails by having no form for the question. Only the last kind of failure decides anything.

6 figures · Bouton How far a description of that kind could ever have gone. Subtraction games sorted by whether a Bouton-style column criterion describes their losing positions. His test reads the heap sizes in binary and counts the marks in each column, which works exactly when a heap's value is a function of its own bits — and that is true of a small minority of the family. Below it, the weaker readings: a criterion on the low bits, and a sequence that merely repeats. The method itself is available for every game and says nothing; what 1901 supplied was a set with a description shorter than the game.

A set with a short description

Bouton's argument is a closure argument about a set, and every impartial game has such a set — its own losing positions. So the method is complete and proves nothing. What made 1901 a theorem is that his set had a description shorter than the game, and swept over fifty-six subtraction games, exactly seven have one of his kind.

6 figures · Bouton The misère sentence, asked of games it was not written for. Bouton's one-sentence solution of misère Nim put to four other impartial games and checked against a search on every position. It is exact on Nim, which is the game it is a theorem about, and wrong on all the others — and wrong in both directions, calling wins losses and losses wins, where the same paper's normal-play criterion errs only one way. The clause responsible is the one about heaps of size one, which is a statement about how many counters are left rather than about what a move can do with them.

The sentence that solved the other convention

Bouton's paper solves misère Nim too, in one line, and it is the only misère result in the subject that fits on one. Transplanted the way the normal criterion is, it fails differently — the normal one calls losses wins and never the reverse, and this one errs in both directions on every game tried, because the clause it adds is about counters rather than about moves.

6 figures · Bouton A vocabulary that is not closed under its own arithmetic. Every pair of named values added together, with the answer sorted by whether it has a name. The named vocabulary covers every game born by day two and one in twenty-three born by day three, and coverage is the wrong measurement: the notation exists so that positions can be added. A sixth of the sums of two named values at day three cannot be written without opening a brace, and the first one to escape is a sum of two of the symbols anybody learns first.

Two names that add to nothing nameable

The special symbols reach one game in twenty-three at day three. Coverage is the wrong measurement. The notation exists so that positions can be added, and a sixth of the sums of two named values at day three cannot be written without opening a brace — starting with a sum of two of the six symbols anybody learns first.

6 figures · Notation Two numbers instead of an expression. The mean and the temperature of a position, set against its brace expression. The pair is readable in a way the expression is not and is half its length, and it is not exact: most of the games born by day three share a pair with some other game. The cost is not abstract — two games written the same way here can be separated by adding an ordinary small position to each, which is exactly the test a table of outcomes fails one level down.

What two numbers cannot tell apart

A thermograph summarises a position in a mean and a temperature — nine characters against the brace form's twenty-two, and readable in a way the expression is not. It is also not exact: 1,454 of the 1,474 games born by day three share a pair with some other game, 291 of them share one pair, and adding a star to two of those gives different winners.

6 figures · Notation Writing a board as a sum, and as the value it is. Every sum of two, three and four games born by day two, written as the parts joined by plus signs and as the single value the sum equals, with the number of distinct values, the share that can be written without a brace, the share longer as one value than as a sum, the middle length each way and the longest single value. The single value is shorter in the middle and far longer at the top, and needs a brace more often the more parts there are.

A board is written as a sum

Every measurement of the brace notation so far has been of a single position, and nobody writes a single position. A board is several parts, and it can be written as the parts joined by plus signs or as the one value they add up to. Over every sum of up to four games born by day two, the one value is usually the shorter — and the share of boards that need a brace climbs with every part added, until the longest value is four times its sum.

6 figures · Notation A shuttle and a loop, judged by what the play returns to. A three-node loopy game drawn as a graph, with Left's moves in blue, Right's in red and position a marked. Beside it, each position-and-mover pair under the backward labelling and under the rule that a never-ending play goes to Left when it returns to a infinitely often. Four pairs are drawn by the labelling; the new rule gives two to Left and two to Right and leaves the decided pairs as they were.

What the play keeps coming back to

A draw is what the backward labelling never reaches, and handing every never-ending play to one player turns the draws into wins wholesale. Judge an infinite play instead by what it keeps returning to, and every draw gets a winner of its own: over the 262,144 three-node games, 15,432 send some of their draws to one player and some to the other, which no wholesale rule can do. Finding those winners takes a fixed point inside a fixed point.

6 figures · Determinacy A hub with two spokes, and the bit of memory it needs. A three-node loopy game in which Left, at a hub, chooses between two spokes and Right must return from either. Left wins a never-ending play that passes through both spokes infinitely often. With one bit of memory recording which spoke is owed, Left wins from the hub; with a strategy that depends only on the position, Left always takes the same spoke and loses. Three position-and-mover pairs change hands.

One bit of memory

Judge an infinite play by whether one position keeps recurring and every winner can play from a table of one move per position, with nothing remembered. Ask for two positions to keep recurring and that stops being true. At a hub with two spokes a player has to alternate, and a table cannot alternate: over every three-node game, 49,487 position-and-mover pairs are won with one bit of memory and lost without it.

6 figures · Determinacy One step and four captures. Dawson's pawns on a board three ranks deep and five files wide. A White pawn steps forward on the middle file, and because a capture must be made when one is available, four captures follow: Black takes, White retakes, Black takes, White retakes. Five moves later the three middle files are finished and the two outer files are untouched, which is the octal move taking three from a heap of five and leaving two heaps of one.

The capture that has to be made

Dawson's chess is quoted as the octal game ·137, and the step from a pawn diagram to a row of counters has been taken on trust. Searched as a chess position, the diagram agrees with ·137 on every board from one file to twelve, under both endings, and every exchange it can start is an odd number of moves that lands on one of ·137's options. The whole reduction rests on one rule of the diagram that the octal code never mentions: a capture, when one is available, must be made. Make it optional and the winner changes on two, three, six and seven files.

6 figures · Dawson A row of files, valued rather than won. Dawson's pawn diagram on a single row of one to 5 files, with the value of the position under each capture rule beside the nimber ·137 gives the corresponding heap. The winners agree throughout; the values agree until five files, where the diagram is worth ∗ and the heap is ∗3.

A wall the pawns cannot cross and the rule can

Two rows of Dawson's diagram separated by a file with no pawn on it: 1,616 moves were examined and not one crosses the gap. With captures optional the rows add on every diagram checked. With captures compulsory they do not, because the compulsion is a rule about the whole board — and the game that is a sum is the one ·137 does not describe.

6 figures · Dawson Which conditions make a winner remember. Every condition on which set of three positions a never-ending play keeps returning to, grouped by two properties of the condition alone, against the arenas swept. 32 of 128 conditions have an arena Left wins and cannot win from a table of one move per position; 19 of those are closed under union.

The rule decides who has to remember

Whether a winner needs memory is a property of the winning condition and not of the board, and the property everybody reaches for is the wrong one. Of the 128 conditions on which of three positions a play keeps returning to, 32 demand memory and 19 of those are closed under union. What separates them is measured two independent ways and the two agree on all 128: a condition needs no memory exactly when it can be rewritten as a number on each position.

7 figures · Determinacy One more row, and the correction comes back. Dawson's diagram of three files beside a row of one, then two, then three, each drawn with the difference between the whole board's value and the sum of its rows. The correction is ∗2, then 0, then ∗2: adding a row removes it and adding another restores it.

A difference the rows cannot predict

The diagrams that are not the sum of their rows have been counted and never priced. Priced over 50 diagrams and 63,408,981 positions, the difference takes three values and is a function of nothing a reader can see: seven diagrams whose rows are worth ∗ and ∗ split five to two on it, the third value arrives only at the ninth file, and the one rule that survives is a parity — all twenty-one diagrams of three, five and seven rows add, and every failure carries an even number of rows.

7 figures · Dawson The tree of {a and b and c}, and the states it costs. The Zielonka tree of one winning condition on which positions a never-ending play recurs at. The root is the whole set of positions; the children of a node are the largest subsets the condition judges the other way. The number of memory states a winner needs is read back up the tree by adding at accepted nodes and taking the largest at rejected ones, and this condition costs 3.

Two things to hold at once, or three

Whether a condition makes a winner remember has been settled over every condition on three positions; how much it makes them remember has not. A tree built out of the condition alone, with no board in it anywhere, prices all 128: sixty-one cost nothing, fifty-eight cost two states and nine cost three. It also names the property that was nearly right — closure under union of the sets a condition rejects decides it exactly, where being writable as numbers is sufficient and reaches twenty-six.

6 figures · Determinacy Every two-position loopy region, as two names. The 256 loopy regions of two positions, placed by the names of their onside and offside as identified against the 1,474 values born by day three. Ten names cover every side: 0, 1, −1, ∗, on, off, over, under, upon + ∗ and −upon + ∗. The largest groups are on & off with 94 regions and off & off and on & on with 53 each; 25 regions need only finite names.

A loop is written with two names

A region with a cycle in it has no brace expression, and every one of the 256 regions of two positions can be written anyway — as two names, the game it is when a play that never ends goes to Left and the game it is when it goes to Right. Checked against all 1,474 values born by day three, ten names cover every side, 25 regions need only finite ones, and the pair predicts every sum with a finite game, draws included: a draw arrives exactly where the two names disagree.

6 figures · Notation

All ladders · Every object named here · The position index · Figures that play back · Search