Combinatorial Game Theory
who wins, and by how much
Concept

Hot position — where it appears

A position both players want to move in, so that moving first is worth points rather than merely being possible. A pile of copies of one is worth its mean plus a leftover fight, and the leftover alternates with the parity of the pile.

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

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.

temperature · Temperature Why nobody moves in the number. A hot position added to a number. Left wins the sum whoever moves — but only by moving in the fight. Spending the move on the number instead hands the position back as a first-player win, with Right to move, which throws the win away. The theorem says this is always so, and here it is happening.

Numbers avoid numbers

In a position with a number in it and anything else, the number is never the right move. That is a theorem rather than a heuristic, and it is the closest this subject comes to advice a player can carry into a real game.

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

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.

temperature · Strategy The same population counted twice. The temperature scale over the positions this site has enumerated, once with every position counted and once with every distinct value counted. The two disagree about how much of the subject is hot, about what the commonest hot temperature is, and about whether a number is the usual thing for a position to be worth.

How hot a real position is

Counted one value at a time, a tenth of the subject is hot. Counted one position at a time — every board this site has enumerated, all 11,397 of them — it is a twentieth, two thirds of the positions are worth numbers outright, and ten of the seventeen rulesets never produce a hot position at all.

temperature · Cold The same distance, different room. Two shared Amazons regions with the amazons the same distance apart, differing in how many squares both of them can still reach. The one sharing more is the colder.

Room pulls two ways

The rung below found the distance between two amazons setting a shared region's temperature and asked for something finer — the squares each can reach, or the squares both can. Neither beats the distance on its own. Together they beat it by half as much again, and the reason is that they pull opposite ways: further apart is hotter, and sharing more reachable squares is colder.

positions · Amazons A plateau, not a point. The rule's score as the coefficient is varied on a fine grid. It is constant across the open unit interval and drops at exactly one.

The worst value in its own interval

The rung below scored a component by its temperature less its hottest answer's and asked what rate the answer should really be charged at. Every weight strictly between nought and one scores the same and beats the rung below's choice of one at every board size — because a ranking rule's score is a step function of its own coefficient, and one is exactly where two components tie.

temperature · Coupons The five hottest regions. Every eight-square Domineering region at the ceiling temperature, with which of the boards swept ever produces it.

Eight squares, and no hotter

The rung below found no Domineering position hotter than three halves on four boards and asked for the position that attains it. It is a region of eight squares, there are five of them up to symmetry, three are the hot core of an attaining board on every size swept — and the ceiling holds at nine and ten squares too, where the obvious extrapolation predicted seven quarters.

temperature · Cold What the flip is worth, and what is at stake. Left's chances if Left moves and if Right moves, with the gap between them beside the position's temperature. The two are answers to the same question computed by different routes, and they do not order the positions the same way.

The coldest position has the biggest swing

How much a flip is worth is the gap between the coin's two branches, and it is a rival to the temperature — both answer how much is at stake. They disagree at once: the empty position has the lowest temperature there is and a swing of one, twice the hottest thing born on day two. On the small pool the two quantities look like a perfect three-way correspondence, and 255 of day three's values break it.

limits · Bidding

Named alongside it

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

TemperatureThermographEnumerationBoundCold positionExhaustive searchHeuristicHot gameMean valueMove selectionApproximationBoard

All concepts