Combinatorial Game Theory
who wins, and by how much
Concept

Coupons — where it appears

A stack of moves worth fixed amounts, each cooler than the last, standing in for everything else on a board. A player facing a position plus a coupon stack has a decision with a number attached to it, which is how a claim about play in company is turned into arithmetic.

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

The same temperature, and four different departures. Positions with a temperature of one whose follow-ups are worth different amounts, with the coupon at which the players leave the environment. The departure tracks the follow-up.

How big the answer is

The rung below found every early departure from a coupon stack caused by a position with a follow-up, and could not say more: its follow-ups were all of a similar size, so the class it measured was one bit. A pool graded by follow-up size answers it. With the position's own temperature held at one, the departure runs from coupon 1 to coupon 3.5 as the follow-up's temperature runs from 1 to 4 — and over the whole grid the players leave at the larger of the two temperatures.

temperature · Coupons What a designed pool can say. Six statements about the coefficient, with which pool each rests on.

A second pool, designed differently

One designed pool put the rule's best coefficient between a quarter and a third, and all three board sizes agreed. A second pool, built by the identical greedy criterion from different material, has no cell that is best at every size — so the coefficient is a property of the pool and there is no number to find.

temperature · Coupons 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.

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.

temperature · Strategy

Named alongside it

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

EnumerationMean valueStrategyTemperatureThermographDisjunctive sumExhaustive searchHeuristicHot gameAmbientEnvironmentFollow-up

All concepts