Combinatorial Game Theory
who wins, and by how much
Concept

Switches — where it appears

The positions worth fighting over, each worth a mean with a temperature and neither of the numbers it leads to. Two of them with equal temperatures can add to nothing at all, which is the commonest way a sum loses its heat.

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

Three partizan positions against every nimber, and not one match. Sprague and Grundy give every impartial position a single number that is complete: two positions with the same value are interchangeable everywhere. The three positions here are partizan — the two players have different moves — and each is compared against every nimber up to eight. Nothing is equal to anything. The magenta cells are worse than inequality: a position confused with a nimber is not above it or below it either, so no ordering could rescue the substitution.

Where the impartial theory stops

Sprague–Grundy gives every impartial position one number, and the number is complete. The moment the two players have different moves no number works at all — not a harder one to compute, none — and three positions here are compared against every nimber to show it.

sums · Sprague–Grundy The endgame, accounted for. Several independent regions, each a fight with a settled value and a size. The account plays them hottest first: add up what each is worth on average, then add the largest amount at stake, subtract the next, and so on down. The exact value of the whole position is computed beside it, and the figure prints both.

The first time it told somebody something

A theory earns its keep when it produces an answer nobody had. Temperature did that for Go endgames — the orthodox account gives a move order that is provably right and is not the one experience offers, and the position it is right about is small enough to check here completely.

history · Temperature the temperature that bounds the loss. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

A rule that is never right and cannot be far wrong

Playing the hottest component is not optimal — over 440 measured lines it costs something on 17 of them. What makes it worth having is that the cost is bounded by the temperature, provably, and that the same test run with the ordering reversed breaks the bound on 54.

complexity · Approximation The switch formulas, off the hypothesis they were stated for. Values born by day three with exactly one option a side, split by whether both options are numbers. On the twenty-one that satisfy the textbook hypothesis the midpoint and half-gap formulas are exact; on the 146 that do not, the same formulas read off the two stops instead hold about three quarters of the time.

A fight with no midpoint

The mean of {a | b} is the midpoint and the temperature is half the gap — on the twenty-one values of day three where a and b are numbers. One hundred and forty-six others have the same shape and not the hypothesis, and the repair that suggests itself, reading the two stops instead of the two options, holds on about three quarters of them and no more.

values · Switches The wall as an envelope. A thermograph with each option's contribution to its wall drawn over it, built from that option's two stops alone. The wall is the envelope of those contributions and it bends where the envelope has a corner.

The bend is in the stops

The rung below reduced the whole stop reading to one question — does this wall bend? — and asked whether that could be answered from the options' stops instead of from a diagram. It can, in four lines, and it gives more than the bend: on all 1,459 non-number values born by day three the options' stops determine the entire thermograph. One day deeper it breaks, and every failure is a value with a bent-walled option.

values · Switches 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.

values · Switches The bound, and the cost, on four pools. Hottest-first play against optimal play on boards of two, three and four components drawn from four pools, 4,240 lines in all. The bound on the cost is the largest temperature on the board, which reaches 3; the worst cost measured anywhere is 1, and 100 lines meet the bound exactly.

The bound names the hottest part and the cost does not

Moving in the hottest component costs at most the largest temperature on the board, and that bound is attained: 100 lines of 4,240 pay exactly it. It is still the wrong quantity. Across four pools and boards of two, three and four parts the cost is nothing on 90.8% of lines and otherwise takes one of two values — half a point or one — on boards whose largest temperature runs to three, and it exceeds the coolest component on 13 lines and twice it on none.

complexity · Approximation

Named alongside it

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

Mean valueTemperatureThermographDisjunctive sumApproximationCanonical formStopsCounterexampleDay threeEnumerationExact evaluationExhaustive search

All concepts