Combinatorial Game Theory
who wins, and by how much
Series

Bouton — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Bouton's invariant, checked over 512 positions. Nim positions in binary, one column per bit. Bouton's 1901 argument is that a position is a loss for the mover exactly when every column holds an even number of marks — and that from such a position every move breaks a column, while from any other position some move repairs them all. Both halves are checked here over every position in the range rather than illustrated once, and the middle row shows the repairing move being made.

    The theorem that needed none of the theory

    Bouton solved Nim completely in 1901, with an argument that mentions no value, no sum of games and no Grundy number, because none of the three existed. The argument is two closure properties and it is airtight — and run on any other game it fails at the step that does the work.

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

    part 2 · history
  3. 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.

    part 3 · history
  4. 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.

    part 4 · history
  5. One substitution, thirty-four years. Bouton's criterion and the Sprague–Grundy theorem run side by side over a family of games. They differ in one quantity: the heap's size against the heap's Grundy value. The exclusive-or that combines them is the same operation in both, and it is the one Bouton published in 1901.

    The step nobody took for thirty-four years

    Bouton's criterion is that the heap sizes exclusive-or to nothing. The 1935 theorem is that the heap Grundy values do. The exclusive-or is the same operation in both and it is his, so the whole of the intervening thirty-four years is one substitution — and run over eight games and 672 positions, the substituted criterion is exact on every one while the original is exact on Nim and nowhere else.

    part 5 · history
  6. Bouton's argument, indexed by a value. Bouton's two closure properties stated for every Grundy value rather than for nought alone: no move stays inside a value class, and every class above a value can reach it. Checked on each game and each value in range.

    The picture Bouton's proof leaves behind

    His argument is two closure properties of one set, and the Sprague–Grundy theorem is the same two sentences with nought replaced by a variable — checked here on five games and every value in range, with no move staying inside a class and no class failing to be reachable from above. What the argument also leaves behind is a picture in which the values descend, and that is false: 99 of 444 moves here raise a value, and none of them is in Nim.

    part 6 · history

All series