Combinatorial Game Theory
who wins, and by how much
Concept

Difference — where it appears

The game G minus H, whose winner settles how the two compare, and which exists only because every position has a negative. Every comparison on this site is one of these played out, which is why comparing is a search rather than a look.

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

Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.

Comparing positions

One position is worth at least another when the second player wins their difference. That is the only definition there is, it is a computation rather than a judgement, and it produces an order in which some pairs are simply not comparable.

sums · Comparison Every position has an exact opposite. A position beside its negative, which is the same game with the players exchanged, and the sum of the two. The sum is worth zero every time — a second-player win — because the second player can answer each move with its mirror image. It is the fact that makes values a group, and it is what lets one position be subtracted from another.

Turn the board through a right angle

A two-by-four Domineering board is worth something no number can express, and Right is ahead on it. Turn a second board through a right angle, put the two side by side, and the total is exactly zero. Every position has an exact opposite, and that single fact is what makes subtraction — and therefore comparison — possible at all.

sums · Negation Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.

Confused is not the same as unknown

Two positions can be neither greater, nor smaller, nor equal. That is a fourth relation with its own symbol, it is a fact about the pair rather than a limit of the method, and it is what makes a game worth playing — a position is a first-player win exactly when it is confused with zero.

sums · Comparison The context that tells them apart. Two positions put into the same company, one context at a time. Each column is a game X; each cell is the outcome class of that side added to X. Equality means every column agrees, for every X there is — so a single disagreeing column is a disproof, and agreement across a bounded list of contexts is evidence rather than proof. The proof is that the difference is zero.

Equal in every company

Two games are equal when no third game can tell them apart — a quantifier over every position there is, discharged by one finite test. A search over 184 contexts separates all 5,790 unequal pairs it is handed and still calls two different games the same, which is exactly why G − H = 0 is a theorem and an exhaustive search is not.

sums · Equality 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 How often one value is above another. The partial order counted on two successive days. The proportion of pairs that can be compared at all falls sharply, and so does the proportion of values that can be compared with zero — which is the proportion of positions whose winner does not depend on who moves.

How rare it is to be bigger

Values are partially ordered, and 'partially' does most of the work. On day two, 179 of 231 pairs can be compared and 13 of the 22 values can be compared with zero. One day later the shares are 60% and 29%, and the largest set of mutually incomparable values found rises from four to at least twenty-three. Comparison is the exception; confusion is what values normally do to one another.

sums · Comparison Options handed to Left in 1 | −1. A position, and one candidate option after another added to it. Where the gift is one the player would never take the value does not move at all; where it is one they would, it does. The last column is the value of the enlarged form, computed by the same recursion as the original.

An option nobody would take

Every reduction of a form deletes. The gift horse principle adds: a move may be handed to a player for nothing, provided it is one they would never choose. Over all 484 additions to the values born by day two, 283 leave the value exactly where it was and the 201 that move it are precisely the ones the condition forbids — with the boundary at *not better*, which is a weaker demand than *worse*.

values · Gift horse

Named alongside it

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

ComparisonEqualityPartial orderConfusionOutcome classStar (∗)Disjunctive sumExhaustive searchNormal playAdditivityBorn on dayCanonical form

All concepts