Combinatorial Game Theory
who wins, and by how much
Concept

Chess — where it appears

A board game whose blocked pawn endings decompose into independent files, giving positions decided by tempo rather than by material. Elkies showed pawn endings whose values are infinitesimals, so the theory says something exact about a game nobody built it for.

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

Backward induction on a game that ends, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing.

The first theorem, and the winner it declines to name

Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.

history · Determinacy A blocked file, and the tempo it holds. Files of a blocked pawn ending: a White pawn below, a Black pawn above, and a gap between them that either side may close one square at a time. Each file carries the value the game recursion gives it. With only single steps available a file is worth a star or nothing, by the parity of the gap, so the whole position is tempo and no material at all — which is what a chess player means by mutual zugzwang.

A pawn ending is a sum

In a blocked pawn ending the material is level, the files never speak to each other, and whoever has to move is the one in trouble. Chess calls that mutual zugzwang; this site calls it a P-position; and the two vocabularies were built four decades and one subject apart to say the same thing.

applied · Chess Which clause of the rules produces which kind of value. Every combination of pawn-file clause in range, sorted by the kind of value it produces. Files where both pawns can advance are all-small and their values are nimbers and infinitesimals. A file where one pawn is stuck behind a friendly piece gives the other side free moves and is worth an integer. A file whose middle square can be held stops the other pawn the moment somebody reaches it, and is worth a switch — a position both players want to move in. The dictionary is read off the evaluation rather than asserted.

What has to break before a pawn is worth a number

Every value the blocked-file model can hold is an infinitesimal, and the reason is one sentence about the move rule rather than anything about pawns. Break that sentence — a pawn stuck behind a friend, a square only one side can hold — and integers, switches and positions worth fighting over arrive at once.

applied · Chess What one king costs a decomposition. Two pawn files and one king a side, solved as a joint position and again as the sum of its files. With the kings unable to move the two answers agree on every configuration, because a king that cannot choose between files is not a shared resource. Give each king a waiting move and the answers come apart, and on some configurations the sum of the parts names the wrong winner rather than merely the wrong value. Independence is a hypothesis about the position and this is the price of assuming it wrongly.

One king, and two files to be in

The whole apparatus needs the files to be independent, and a king is what makes them not. With the kings unable to move the sum of the parts is exact on every configuration; give each king a single waiting move and the sum names the wrong winner on one configuration in six, and on a hundred and twenty-six of two hundred and forty-three with three files.

applied · Chess A fortress, and the counter that gives it a label. A pawn ending where the defender's king shuffles for ever and the attacker needs time. Down the rows, how many moves of preparation the breakthrough needs; across the columns, how many moves the rule allows before declaring a draw. With no breakthrough the position is drawn whatever the rule says, and drawn as a residue the backward induction never reaches. With a breakthrough and no rule the attacker wins despite the cycle. Where the march is longer than the counter allows, the rule turns a won position into a drawn one.

A position with no value, and the rule that gives it one

A fortress is a cycle in the position graph, so the recursion defining a value has nowhere to bottom out and the propagation never reaches it. Chess has a rule for that — count fifty moves and call it drawn — and the rule does not merely tidy the theory up. On eleven cells of the sweep it takes away a win.

applied · Chess 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.

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

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

history · Dawson Three rows that do not add. Four diagrams of Dawson's pawns valued whole and as the sum of their rows. 3 + 1 is worth ∗ against ∗3 by rows. 4 + 3 + 1, three rows, is worth ∗ against ∗3, a difference of ∗2, over 4,153,158 positions. 5 + 2 + 1 and 3 + 2 + 1 add.

The rows that cancel

Every one of Dawson's diagrams that failed to be the sum of its rows had an even number of rows, and twenty-one with an odd number all added. One file past the edge of that sweep, four files beside three beside one fails: three rows, worth ∗ against ∗3 by its rows. What the parity was tracking is two deletions a sum allows — a row worth nought, and two identical rows — which the compulsory board turns out to allow as well. Each of 44 diagrams is worth exactly what is left after them, and in the fifty-diagram sweep that remainder happened to have as many rows, odd or even, as the diagram it came from.

history · Dawson The same table, read two ways. Two games of king and rook against king from a position 16 moves from mate. A white who reads the distance descends one move at a time to mate. A white who reads only whether a move keeps the win wanders and is still 13 moves from mate after 80 moves.

A win is not a way of winning

Solve a lone king against a rook completely and every one of 175,168 positions with white to move is won. Now let white play any move the table says keeps the win, and black resist as long as it can: in 400 games of up to 2,000 moves, white never mates. On a graph that loops, staying won is not progress. From every won position in the queen and rook endings white can stay inside the won set for ever, and what wins is a second number, the distance, which the theory of finite games never had to ask for.

applied · Chess

Named alongside it

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

Exhaustive searchDecompositionDisjunctive sumOutcome classDawsonIndependenceOctal gameZugzwangCounterexampleGrundy valueLoopyNimber

All concepts