Combinatorial Game Theory
who wins, and by how much
Generator

Move where it is hottest

Move where it is hottest
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.

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.

10 essays call play-the-hottest. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Changing this generator changes every one of these figures.

Which questions are answerable. The theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space. What it costs

How hard is it

Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.

 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. Temperature

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.

 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. Temperature

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.

 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. Sums and comparison

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.

 Every position of both games, and where the fights are. Every colouring of every graph in the library, under both rules, with the temperature of each computed. A position with a positive temperature is one both players want to move in. Col has none anywhere; Snort has them on every graph, and the hottest grows with the graph. Particular games

One rule makes it cold, the other hot

Col forbids painting next to your own colour and Snort forbids painting next to your opponent's. Over all 540 colourings of six graphs, not one Col position has anything at stake and 61 Snort positions do — the difference between a game that is a count and a game that is a series of fights, produced by one word.

 What the rule costs. Every sum of three components from a fixed pool, played out twice: once with one side following the rule "move where the stake is largest" and once with both sides evaluating exactly. The rule is not optimal, the gap is bounded, and the bound is the largest temperature on the board. Temperature

A rule with a guarantee

Evaluating a sum of a dozen fights is impossible; following a rule is not. Move where the stake is largest, and over 220 sums of three hot components the rule scores exactly what perfect play scores in 196 of them, is never more than one point behind, and never ends more than the largest single stake below the mean. The rule that is supposed to be different — answer the threat — chose differently in none of the 220.

 Four rules over 220 sums. Each rule plays every sum against an opponent evaluating exactly. Two of the rules come with a bound and two do not; the coldest rule is the control, and it violates the bound often enough to show that being inside it is a real constraint rather than a description of the pool. Temperature

A rule with no promise at all

Playing in a hottest component comes with a bound: never more than the largest single temperature below the mean of the board. Over 220 sums the bound holds 220 times — and so does the bound for a rule with nothing behind it, which scores exactly what perfect play scores on 205 sums against the hottest rule's 196. The control that shows the bound is doing work is the rule that plays the coldest component, which breaks it 74 times and loses up to eleven points.

 Five rules over 120 sums built to punish greed. Each rule plays every sum against an opponent evaluating exactly, on a pool whose components are traps: a large immediate gain that hands the opponent a larger follow-up. The pool was built to punish the greedy rule and does not — that rule scores a move by the stop it leaves, and a stop already contains the follow-up. What the traps catch is the rule below it, which scores a move by the territory it takes and loses up to 16. Temperature

A pool built to punish greed

The rung below found a rule with no theorem behind it beating the rule with one, and predicted that a pool of deliberate traps would reverse the result. It does not. The traps miss, because the rule called greedy scores a move by the stop it leaves and a stop already contains the follow-up — and the rule the traps do catch, losing sixteen points where the guaranteed rule loses five, had to be written to make the point.

 How far down the stack the guarantee reaches. The temperatures of a sum's components, sorted largest first, with each position asked whether playing in the hottest component can lose more than the temperature sitting there. The first two never fail; the third fails on 681 sums. Temperature

A schedule instead of a number

Playing in the hottest component loses at most the largest temperature on the board — the classical guarantee, stated against one number. Sorting the temperatures and reading the guarantee one step further down gives a promise 47 per cent smaller that is never breached over 1,734 sums. Two steps down it fails 120 times, so the schedule has exactly one step of slack in it.

 Five rules over 120 sums built to punish greed. Each rule plays every sum against an opponent evaluating exactly, on a pool whose components are traps: a large immediate gain that hands the opponent a larger follow-up. The pool was built to punish the greedy rule and does not — that rule scores a move by the stop it leaves, and a stop already contains the follow-up. What the traps catch is the rule below it, which scores a move by the territory it takes and loses up to 16. Temperature

An environment instead of a stack

The guarantee behind playing the hottest component survives one step down a board's sorted temperatures and fails at two. Against a coupon environment as hot as the board it survives all of them — because the rule stops being approximate and starts being optimal, on every sum in the pool built to punish it.

The whole library · The position index · The figures that play back