Combinatorial Game Theory
who wins, and by how much
Concept

Coupon stack — where it appears

An idealised environment beside a position: coupons of decreasing value, either of which a player may take instead of moving in the game. It makes an ambient temperature something a player can see, which is how the theory was first put in front of professionals.

Named by 9 essays across one field — each of them below, with the objects they name alongside it.

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

temperature · Coupons 4 | 0 and {2 | {1 | 0}} in the same environment. Two positions and one coupon stack, solved as a single board. The rows are the line optimal play takes; the coupon on top when each position is first entered is compared with the coupon it was entered at when it had the environment to itself. The mean contributions still add and the entry coupons need not agree.

Two games in one environment

A coupon stack measures a position: play the whole board out and the coupon the players stop at is the temperature, the score is the mean. Put a second position beside the first and one of the two measurements stops working. Over 36 ordered pairs the contributions still add to the means every time, and the coupon a fight is entered at moves on 13 of them — without either position changing.

temperature · Coupons Two clauses, one formula. The law split by which of the two temperatures is the smaller. When the answer is colder the correction is half of it; when it is hotter the correction saturates at half the fight's own temperature.

Half of the smaller temperature

The correction to the sente crossover has been priced twice — first as a factor of a half, then as a subtraction of a half — each time on a pool whose answers were all about the same size. Over 128 fights with answers from a number up to a temperature of six, the correction is half the answer's temperature, saturating at half the fight's own. Both earlier readings are regions of that one law.

temperature · Sente The ordering that does not order. Playing in the hottest component against playing by the larger of a component's two temperatures, over 220 boards. The proposed rule is exact far less often and its worst case is nine times as bad.

The quantity that does not order a board

The rung below found the players leaving an environment at the larger of a position's two temperatures, and proposed that a board should therefore be played in the order of that quantity. Over 220 boards of three components it plays exactly on 124 against playing-in-the-hottest's 196, loses 85 of the 97 disagreements, breaks Hotstrat's guarantee on six boards, and costs nine points on its worst one.

temperature · Coupons The rule that was supposed to lose. Five ordering rules on the same 220 boards. Playing where the temperature less the answer's is largest is exact more often than playing in the hottest component, which is what the rung below predicted it would not do.

A rule that beats the hottest

The rung below proposed the reverse of the rule that had just failed — discount a component by its answer's temperature rather than promoting it — and predicted, before the sweep, that it would not beat playing in the hottest component. It does. It plays exactly on 201 of 220 three-component boards against 196, wins two thirds of the boards where the two disagree, keeps inside a guarantee proved for the other rule, and the gap widens as the board grows.

temperature · Coupons The third temperature is not consulted. Positions grouped by their two top temperatures, with the third temperatures they hold between them. The crossover is the same for every position in a group however far apart their third temperatures are.

The two numbers at the top

The rung below found the crossover of a sente fight to be its temperature less half its answer's, and said a proof would settle the depth question with it. The depth question is settled without the proof, by construction: group the positions by their two top temperatures and the crossover is single-valued on every group, however far apart the third temperature is — and the formula survives a fourth level of fight, which the rung below never reached.

temperature · Sente 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 Five premises, and the step. The claims an induction would need, with what checks each. The last row is the step and nothing here checks it.

The premises an induction would need

The rung below settled by a grouping test that a position's crossover depends on its own temperature and its answer's and on nothing below them, and asked for the induction. The four paragraphs are not written here; the checking they would rest on is. The law holds at five levels, survives translation, heating and cooling — and none of that is the step.

temperature · Sente Two claims read as one. The proposed geometry separated into the claim the rung below established and the claim it needs but did not.

The four paragraphs prove something else

Three rungs earned the right to write the crossover law's proof as two straight walls meeting where the law says. The walls are straight — one of them everywhere, for a trivial reason, and the other only above the answer's own temperature. The crossover sits below that height, so the geometry holds nowhere the law is about, and where it does hold it proves the temperature instead.

temperature · Sente

Named alongside it

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

TemperatureSenteEnumerationFollow-upMean valueThermographAmbientBoundDisjunctive sumStrategyAmbient temperatureApproximation

All concepts