Combinatorial Game Theory
who wins, and by how much
The collection

Every essay — page 34

One idea per essay, ordered so that the earlier ones set up the later ones — but nothing here depends on being read in sequence.

Values

What a position is worth — numbers, and the things that are not numbers, and how to find the simplest one.

The chain, scored. The chain reading of the level count against both pools.

The bend above the top

The chain reading gets three values in 2,403 wrong because it counts bends that the diagram never reaches. Counting only the bends below the position's own temperature fixes all three and breaks none — the first exact reading on this ladder, and it needs one comparison rather than the envelope the rung below expected.

5 figures · Switches The same game, written twice. A position as it arises and the same position reduced. Left would never move to 0 when 2 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

A reduction that reads a graph

The two reductions are defined as deletions from an option list, and the shared form has no option lists — a node is reached from several parents at once. Both restate as rewritings at a node, the rewriting is confluent, and its fixed point is the canonical form. What does not carry over is the sharing: four fifths of the shared nodes need a different answer under different parents.

5 figures · Reversibility The order one day out. Whether the values born by day three still form a lattice. Twice as many pairs are incomparable as at day two, and every incomparable pair still has a least upper bound and a greatest lower bound — so the order becomes more tangled without becoming ragged.

One of four questions

Three rungs of this ladder rest on sweeps of day two — 22 values, 253 pairs. Day three is 1,474 values and over a million pairs, and only one of the four questions can be asked of it. The order can: twice as many pairs are incomparable and every one of 1,606 sampled still has a least upper bound and a greatest lower bound, none of them a value day two already had. The other three compare sums of day-three values, which are born on day six, and sixty of those exhausted an eight-gigabyte heap.

6 figures · Lattice

All ladders · Every object named here · The position index · Figures that play back · Search