Combinatorial Game Theory
who wins, and by how much
Series

Disjunctive sum — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. A position is the sum of its parts. Four separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable.

    The sum is the object

    Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all.

    part 1 · sums
  2. Which part to move in. A sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least.

    Which part to move in

    The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing.

    part 2 · sums
  3. Three ways to add the same games. One list of components, added three different ways. Under the disjunctive rule a move is a move in exactly one part; under the conjunctive rule it is a move in every part at once, and play stops as soon as any part runs out; under the selective rule it is a move in any non-empty set of parts. The outcomes are computed by search from each rule's own definition.

    Three ways to add the same games

    A move in exactly one component is a choice, not a law. Move in every component at once and the game is different; move in any set of them and it is different again. The same two positions, added three ways, give three different answers — and only one of the three has values that add.

    part 3 · sums
  4. A boundary drawn, and a boundary there. One Domineering board split two ways. Above, a line imagined down the middle: the two halves are evaluated separately and their sum is not the value of the board, because every horizontal domino that would have crossed the line has been thrown away. Below, the same column blocked out: the halves are then genuinely independent and the sum is exact. Every value is computed from its own board.

    Independence is a claim

    Splitting a position into parts and adding the values is the whole method of this subject, and the splitting step is a claim about the position rather than a fact about the drawing. Where it is false the two answers differ — and the failures that matter are the ones that keep the same winner and change the value, because nothing reports those.

    part 4 · sums
  5. Four candidate bounds, and the one that holds. Each candidate bound tested against every failing cut. One domino and the height of the cut both fail on six; twice the height holds on all twenty-two; the whole board's temperature fails on eighteen.

    How wrong a nearly-independent split is

    Treating a connected board as a sum of two halves is a claim, and the rung below counted how often it fails. This one prices it: over every vertical cut of every small Domineering rectangle the error is a game rather than a number, it is never in Right's favour, and it is bounded below by twice the height of the cut — a bound the height alone does not supply.

    part 5 · sums
  6. One number, two statements. The smallest true bound on the cost of splitting a board, in both of the currencies it can be stated in.

    One number, stated two ways

    Twice the height of the cut held and was loose; the height alone failed. The smallest true constant is three halves — exact and attained as a bound on how far the value can fall, and an infimum attained nowhere as a bound on the value. The gap between the two is one move.

    part 6 · sums

All series