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

Every essay — page 24

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

Sums and comparison

Real games break into independent parts. Adding them up is the whole method, and comparing them is how it is checked.

The reversing move is the follower's. For each follower under which some gift horse escapes domination, the number of escapes, how many are reversed by Right's move inside the follower, and how many by a Right move in the base part. The follower's move reverses every one.

The follower does the reversing

The gift-horse theorem for the ordinal sum needs two cases, and the second — the added option is reversible — was counted and not described. Recorded move by move, the reversing answer is always Right's move inside the follower: on all 410 escapes under five followers, and on every one of the 2,628 gift horses under every follower that gives Right a move at all. The case split is by follower, not by horse.

6 figures · Ordinal sum What survived, and what did not. The gift-horse theorem, the two-case proof and the one-line description of the reversal case, each scored on the day-three sweep and its mirror and on the day-four sweep and its mirror.

The split slips one day deeper

The reversal case of the gift-horse theorem was described in one line — the follower's own move reverses every gift horse, whenever the follower has one — and tested only where it was found. In the mirror it holds exactly, with 1 and −1 trading places. One day deeper it fails: under ↑ and ½, three gift horses on built day-four bases are not reversed by the follower's move. All three are dominated, so the theorem stands; the clean split by follower does not.

6 figures · Ordinal sum The day-four figure, twenty draws at a time. Corrected day-four comparability from twenty seeds of each of two constructions, as dots on a percentage axis, with the range of day three's four slices shaded and the single figure the earlier essay reported marked. The seeds spread over about twelve points and the two constructions agree.

Twenty draws and a second recipe

Day four's comparability was reported as 60.6 per cent against day three's 59.7, from one built sample and one calibration. Built twenty times with each of two recipes whose biases differ by six points, and calibrated against all 1,474 day-three values rather than a quarter of them, the corrected figure spreads over twelve points from seed to seed and the two recipes agree within one standard error. The floor survives; the decimal was one draw.

6 figures · Comparison

Temperature

How much is at stake, measured. Thermographs, cooling, and why a player moves where the game is hottest.

The thermograph of {5 | 1}. 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.

What is at stake

Some positions both players are desperate to move in, and some neither player wants to touch. The difference is a number — how much the move is worth — and it turns out to be the most useful single quantity for deciding where to play.

6 figures · Temperature The thermograph of {5 | 1}. 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.

Reading a thermograph

A thermograph is two walls rising from a number line, closing in as the tax on moving increases, and meeting where the position stops being worth fighting over. Everything about a position's hotness is in the shape.

6 figures · Thermograph Move where it is hottest. four independent components of one position, ordered by temperature. The temperature is how much a player loses by moving somewhere else instead, so the hottest component is the one to take — and a component that is already a number has no temperature at all, because nobody gains by moving in it.

Playing the hottest

Given several independent fights, play in the one with most at stake. The rule is simple, it is what strong Go players do without being told, it is provably close to optimal — and it is provably not optimal, which is the interesting part.

7 figures · Temperature Cooling {5 | 1}, one degree at a time. The same position under a rising tax on moving. Each bar is what Left gets moving first and what Right gets moving first, once every move costs the tax. The bars close as the tax rises, and at the temperature they meet — and from there on the position is worth its mean value and neither player wants to touch it.

Cooling

Charge a tax on every move and a fight becomes a number. The height of tax at which that happens is the temperature — so cooling is not a technique for finding the temperature, it is what the temperature is.

7 figures · Temperature 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 endgame, accounted for

Add up what each region is worth, then add the biggest thing at stake, subtract the next, and so on down. On a board of simple fights the result is exact — and the moment one region has a fight inside it, the account is out by a point.

6 figures · Thermograph {2 | 0} + {2 | 0} — where the temperature goes. Three thermographs on one frame: two positions and their sum. The mean of the sum is the sum of the means, every time. The temperature is not: it is bounded by the hottest of the parts and is often far below it, so the number that says how much is at stake in a whole board cannot be got by adding up the parts.

Two hot fights that add to a cold number

The mean of a sum is the sum of the means, every time. The temperature is not — it is bounded by the hottest part and is often far below it. Two positions each worth fighting over can add to a plain number that neither player wants to touch.

6 figures · Thermograph {2 | 0}, added to itself. The value of n copies of one position, for each n, beside n times its mean and the smallest distance between the two. The mean value theorem says that distance stays bounded however many copies are piled up — and the bound is the position's temperature, which is what makes the temperature a second genuine measurement rather than a diagram-reading convenience.

The same fight, eight times over

The mean is not roughly what a position is worth. It is the number that eight copies of the position stay close to — and the theorem is that the closeness does not decay as the copies pile up. The gap stops at the temperature, and stays there for ever.

8 figures · Temperature How much changes hands, against how much is at stake. Two ways of choosing where to move, run against optimal play over every board from a pool of three components. Biggest-first takes the component where the most changes hands, which is the count in every endgame book; hottest-first takes the one with the highest temperature. They disagree on most of these boards, the count costs points more often, and — the difference that matters — the count sometimes loses more than the largest temperature on the board, which is the bound the theory's rule is guaranteed to keep.

Big is not the same as hot

A player sizes a move by how much changes hands when it is played, which is the number in every endgame book. The theory sizes it by temperature. On a plain switch the two agree exactly, so nothing shows; on a move with a follow-up they come apart, and the count gives up more than the guarantee the theory's rule carries.

8 figures · Temperature {5 | {4 | 0}} beside one other fight. A local position and a single switch, played out together at each of several ambient temperatures. The middle columns are what optimal play does: whether it opens the local fight, and whether it answers when the opponent opens it. The answer stops being forced at a temperature the local position alone does not name.

Sente is a fact about the rest of the board

A move that must be answered is called sente, and the word is used as though it described the local position. It does not. The same fight is answered while the rest of the board is quiet and ignored once it is busy, and the crossover — measured by solving the whole board at every temperature — sits at the follow-up's own temperature.

7 figures · Sente The thermograph of {6 | {5 | {4 | 0}}}. 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 thermograph is built from its options'

The diagram is not measured, it is computed — each wall is an extremum over the options' opposite walls, shifted by the tax. That construction is why a hot follow-up lowers the temperature instead of raising it, and why two fights with the same swing can differ by a factor of two in what is at stake.

6 figures · Thermograph Is {{5 | 3} | {2 | −4}} double sente?. One local fight with a follow-up on each side, played out inside a sum with a switch whose temperature rises. The two middle columns are what optimal play does when each player opens the fight. Whether the opponent has to answer is settled by the ambient temperature and not by the shape, so the same position is double sente, sente for one player, and gote for both, at three different ambients.

Double sente is not a property of the position

A fight with a threat on each side is called double sente, as though the phrase named a shape. Swept against a rising ambient temperature, one such fight — { {5 | 3} | {2 | −4}} — is double sente up to an ambient of 1, sente for one player only from 3/2 to 3, and gote for both from 7/2, and the two band edges are the temperatures of the two follow-ups.

9 figures · Sente {4 | 0} played out in a stack of 5 coupons. An idealised environment: coupons worth a fixed step less each, which either player may take instead of moving in the game. The rows are the line optimal play takes over the whole board, in order. What the game turned out to be worth is set beside its mean value, and the coupon the players stopped at beside its temperature — two quantities measured from the play, and two computed from the thermograph.

An environment made of coupons

Beside the game sits a stack of coupons worth 4, 3, 2, 1, 0, and a player may always take the top one instead of moving. Play the whole thing out and two quantities the theory computes are measured instead: {4 | 0} comes out worth exactly 2, its mean value, and the coupons stop at 2, its temperature. For {10 | {9 | 1}}, whose temperature is 1, they stop at 7/2 — because what the stopping coupon measures is the hottest temperature anywhere in the tree.

9 figures · Coupons

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