Combinatorial Game Theory
who wins, and by how much
Series

Chess — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

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

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

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

    part 4 · applied
  5. 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.

    part 5 · applied

All series