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

Every essay — page 8

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.

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.

7 figures · Periodicity How long a win takes, against how long the argument allows. Ordinary impartial games with the size of their position graphs, the number of rounds the backward labelling takes, and the number of moves the longest win actually lasts. The round a position settles in is the length of the play from it, which is computed here a second way so the two must agree. The rounds are a handful and the positions are many, which is the gap Zermelo's 1913 paper is about — his question was how many moves a forced win needs, and the answer he could prove was the size of the whole graph.

The paper was about how long

Zermelo's 1913 paper is remembered for a theorem it proves in passing. The question it actually asks is how many moves a forced win takes, the answer it can prove is the size of the whole position graph, and the round counter in the procedure is the real answer — a quantity nobody named for another forty years.

6 figures · Determinacy Two solutions to one set of equations. The winning condition written as a single predicate and solved twice: once as the least solution of its own equations and once as the greatest. The least says Left can force a win; the greatest says Left cannot be forced to lose, which admits the positions where Left can keep the game going for ever. On a graph with no cycle in it the two coincide and the equations determine an answer. Where they differ, the difference is exactly the set the backward propagation never reaches — so a draw is not a leftover of the algorithm, it is the equations failing to have one answer.

The gap between two answers

A draw is usually described as what the backward labelling never reached, which makes it sound like a shortfall of the algorithm. Written as one predicate the winning condition is an equation, the equation is monotone, and it has a least solution and a greatest one — and the set the two disagree about is exactly the drawn set, on every game checked.

6 figures · Determinacy A game every play of which ends, and no round settles. A game whose first move chooses how long the game will be, cut off at several sizes. Every play of it is finite and no position is drawn, so the fourth outcome class has nothing to do with what goes wrong. What goes wrong is the round counter: the opening is a loss, a loss settles only when the last of its options is known, and there is no last option. Cut the game off larger and the round grows, so no number in the column is the answer for the untruncated game — and the induction that labels it has to run past every finite stage.

Every play ends and no round settles

Take the finiteness hypothesis away carefully — not by adding a cycle, which has already been priced twice, but by adding infinitely many positions to a game every play of which still ends. Nothing is drawn, every line finishes, and the round the opening settles in grows with every cut: two, four, six, eight, twelve, sixteen, and no number in the column is the answer.

6 figures · Determinacy What a certificate costs, in units of the one Guy and Smith wrote. Octal codes with the period of their Grundy sequence, the window a proof of that period needs, and the arithmetic each costs — counted as mex operations and exclusive-ors, which are the two things a person computing by hand actually performs. Everything is priced in units of the certificate for Dawson's chess, so the column reads as multiples of one hand computation rather than as a number of operations. Some codes cost tens of times as much, and some have no certificate at all.

What the arithmetic cost in 1956

The rung below ends by respecting a hand computation without pricing it. Priced in the operations a person actually performs, ·137's certificate is 7,919 of them — and the same sweep says ·47's is sixty-three times that, that a splitting move is what makes the cost quadratic, and that seventeen of sixty-four codes have no certificate at any price.

6 figures · Dawson 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

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