Combinatorial Game Theory
who wins, and by how much
Concept

Incentive — where it appears

What a move gains the player making it, computed as the option minus the position, and negative for every move in a number. Every incentive in a number is a loss, which is the reason a number contributes no urgency to a sum.

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

Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

What a move is worth to the player making it

The gain from a move is the option minus the position it was played from — and that is a game rather than a number, so two moves can be incomparable instead of one of them being best. Temperature is what happens when the largest of those games is asked for a single number.

values · Incentives What each move is worth to the player making it. For each position: every incentive, whether they are all strictly negative, whether the position is a number, and its temperature. The middle two columns are two different computations of the same fact.

Nobody wants to move here

A position is a number exactly when every move loses ground for the player making it. The test never mentions numbers, it disagrees with the ordinary one on none of the 1,474 values born by day three — and the reason a position fails it is not that somebody wants to move. It is that somebody cannot afford to wait.

values · Incentives 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 What a pass buys, and what it costs. Rows of coins solved with and without a pass. Milnor's mean-value theory needs a non-negative incentive to move, and rows containing a coin nobody wants break that condition — a player forced to take is a player who would rather have passed. Allow a pass and the condition is not merely satisfied but unbreakable, on every row in range. The price is that a player who may pass is never stuck, so the last-move convention has nothing to attach to and the game needs a separate rule to end at all.

What a pass is worth to a theory

Fifteen of twenty-seven coin rows turn out to be ones where having the move is a disadvantage, and those are exactly the rows Milnor's mean-value theory has to assume away. Allow a pass and the hypothesis stops being a hypothesis — nought violations, on every row in range. What it costs is the convention the rest of the theory is built on.

applied · Scoring The condition has to hold underneath, not on top. Pairs of coin rows sorted by where the incentive condition holds, with Milnor's bound checked on each pair. Rows that satisfy the condition at every subposition never break the bound. Rows that satisfy it only at the top break it on a counted fraction — and a reader who tested the row rather than the row's insides would have called those safe. The distinction is invisible from the position and decides whether the theorem applies to it.

A hypothesis has to hold all the way down

Milnor's bound is proved by induction over the play, so the condition it needs has to hold at every position the play can reach. Checked on the row instead, ninety-two pairs pass the test and twenty-four of them break the bound. Checked at every subposition, twenty-eight pairs pass and none breaks it.

applied · Scoring Four restrictions, and what each one buys. Four candidate classes of scoring game — every row, the incentive condition at the top, the same condition at every subposition, and the rows that cancel against their own negatives — scored on two families of coin rows for the mean-value bound, for comparison by subtraction, and for cancellation.

The restriction that buys the most

Four candidate classes of scoring game, scored on the same two families and the same three questions. The class everyone expects to be tiny — the rows that cancel against their own negatives — is empty on rows of three and the widest restriction on rows of four, where it holds fifteen rows against the hereditary class's twelve and gets all 225 of its comparisons right against 108 of 144. The trade everyone expected does not exist.

applied · Scoring Cancelling is not pairing. For three sets of coin values and rows of two to seven coins, how many rows cancel against their own negatives, how many pair off as nested equal pairs, how many do both, and how many do one without the other.

Cancelling is not pairing

The coin rows that cancel against their own negatives looked like the rows whose coins pair off as nested equal pairs, and on rows of four they are exactly those. From six coins the description fails in both directions — twenty rows pair off perfectly and do not cancel, and one coin set has a hundred and thirty-six that cancel with no pairing at all — and a row of five coins cancels, though an odd row can never pair off. What does hold, on every row swept, is that the first player in a row plus its negative never finishes behind.

applied · Scoring Even rows always reward the move. For four coin sets and rows of one to seven coins, the number of rows in which the player to move does at least as well as when the opponent moves first. Every even column is full.

Even rows always reward the move

Milnor's mean-value theory needs an incentive to move — the player to move must do at least as well as if the opponent moved first. On a coin row with an even number of coins that is not a hypothesis but a theorem: the first player can collect one whole parity class of coins, and one of the two classes holds at least half the total. So the condition excludes no even row whatever the coins, the class the earlier table called 'incentive at the top' was every row of four, and the hereditary condition is a condition on odd intervals alone.

applied · Scoring Two even rows, and the incentive to move. Every sum of two coin rows of two or four coins under four coin sets, 4,095 sums each. The first player is never behind; the margin is never below the difference of the two rows' own margins, equals it on 3,147 sums, and exceeds it on the other 948.

Two rows still reward the move

A single coin row with an even number of coins always rewards the player to move, because the first player can take a whole parity class. Two such rows side by side break that argument, and the conclusion survives anyway: on every one of 16,380 sums of two rows the first player is never behind, and there is a proof — open the row worth more, then answer in whichever row the opponent moves in — that guarantees the difference of the two rows' margins, which is what two switches would give. The sum meets that floor on three pairs in four and beats it on the rest, once by both margins together. At three rows the switch arithmetic stops being a floor. The incentive does not.

applied · Scoring Seven clauses on one recursion. Seven operators built on the same recursion and differing only in the clause that stops it, each tested for f(G + H) = f(G) + f(H) on the 1,768 pairs of the earlier sweep. Failures: cooling 0, cooling with heating's clause 404, heating 263, heating exempting only integers 335, heating with a switch clause 1768, heating with no clause 0, Norton's product by t∗ 0.

The bonus an integer is owed

Heating fails to distribute over a sum where cooling never does, and the repair proposed for it was to change what its exception returns: heat a number into a switch instead of leaving it alone. Run on the same 1,768 pairs, that repair fails on every one of them, beginning with nought plus nought. What adds is a heating that changes which numbers it exempts and pays the bonus on the moves an integer holds in reserve — Norton's product, and heating with no exception at all, which at a whole-number bonus is the same operator. Given heating's exception, cooling stops adding too.

temperature · Heating

Named alongside it

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

Exhaustive searchMean valueTemperatureScoring gameBoundCounterexampleComparisonSwitchHot gameNumbersParityStrategy

All concepts