Combinatorial Game Theory
who wins, and by how much
Concept

Bouton — where it appears

The 1902 theorem that solved Nim: a position is lost for the player to move exactly when the binary columns of the heap sizes all sum to an even number. It was the first complete answer to any combinatorial game, and it is the shape every later answer for an impartial one is measured against — a kernel rather than a count.

Named by 8 essays across 2 fields — each of them below, with the objects they name alongside it.

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.

history · Bouton Thirty-two words, four of them lost. Every position of five heaps grouped by the parities of its heaps in decreasing order of size. Each word is uniform, and four of the thirty-two are losing.

The parities, in size order

The rung below settled four of six parity classes in bounded Moore's Nim and asked whether the sizes pick out the losing positions in the two it could not. They do — but only through the order they put the parities in. Sort the heaps largest first, read off their parities, and that five-bit word settles the whole game at every width of move, with the losing words forming a subspace.

impartial · Moores-nim Four conditions. The four linear conditions whose kernels are the losing sets, with the cases each covers.

The parameter was the difference

The losing words of bounded Moore's Nim form a linear subspace and no map was known whose kernel they are. The equations exist, four conditions cover all thirteen cases at three to six heaps, and they are indexed not by the heap count but by the heaps less the width of a move — which turns the failure at six heaps into a prediction about seven.

impartial · Moores-nim 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.

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

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

history · Bouton 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.

history · Bouton 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.

history · Bouton

Named alongside it

The objects these essays reach for when they reach for this one.

InvariantExhaustive searchGrundy valueNim-sumCriterionNimSubtraction gameClosed formClosureCounterexampleMoores-nimSprague–Grundy

All concepts