Combinatorial Game Theory
who wins, and by how much
Concept

Difference game — where it appears

The game formed by adding one position to the negative of another, whose outcome class is the whole answer to comparing them. Comparing two positions means playing a third, and there is no cheaper test.

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

Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in.

Knowing who wins, and knowing what it is worth

Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.

complexity · Value cost Which end of the interval is open. Every value born by day 3 compared with each of its own two stops — 2,948 comparisons, each one a search over the difference. The two rows are mirror images because the day is closed under negation, and the small number in each row is the exception class: the 352 values whose two stops coincide, for which the left stop is the right stop and the law has nothing to bite on.

Which end of the interval is open

The confusion interval is open at both ends, and the two ends are not the same kind of open. At its own left stop a position can be below the number, confused with it or equal to it, and — over 2,948 comparisons — above it exactly thirty-three times, every one of them a value whose two stops are the same number and whose left end is therefore also its right one.

values · Stops A game beside its own mirror, and what is left over. Every coin row added to its own negative, played out exactly, with the resulting scores counted. Under the last-move convention every such sum is worth nothing, because the mirroring strategy guarantees the second player the last move. Here the same strategy is available and the score it produces is not nothing: the mirror of a coin conceded is another coin conceded. Gold is the sums that do come to nothing, which are a minority.

Nothing to subtract with

Comparison is defined by contexts and computed by subtraction, and the equivalence between the two is a theorem about groups. A scoring game is not one — sixty-six of eighty-one coin rows do not cancel against their own negatives — and the difference test then fails on a row compared with itself, which every context accepts and nothing certifies.

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 Cancelling rows add to cancelling rows. Every pair of cancelling coin rows of two, four and five coins from minus two, one and three, grouped by their lengths, with the number of pairs whose sum cancels against the sum of their negatives.

A cancelling pair is a zero

Two cancelling coin rows side by side cancel against their two negatives — all 190 pairs from rows of two, four and five coins, the odd row that cancels without pairing off included. And a cancelling row beside its negative is invisible next to any other row: in 741 tests against every row of one to three coins, neither score of the context moves. A non-cancelling pair moves a score in 452 of 780. Scoring games have no inverses in general; this class has them, and they behave as inverses must.

applied · Scoring

Named alongside it

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

ComparisonExhaustive searchGroupScoring gameContextNegationCounterexampleEqualityIncentivePartial orderTemperatureAdditivity

All concepts