Combinatorial Game Theory
who wins, and by how much
Concept

Confusion — where it appears

The relation between two positions whose difference is a first-player win, which is a computed verdict rather than an absence of one. The set of numbers a position is confused with is an interval, and its width is exactly twice the position's temperature for a plain fight.

Named by 13 essays across 3 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 The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

Reading a thermograph

A thermograph is two walls rising from a number line, closing in as the tax on moving increases, and meeting where the position stops being worth fighting over. Everything about a position's hotness is in the shape.

temperature · Thermograph 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 values born by day three that are their own negatives. Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two. The nimbers do, and they are not the only ones: a switch symmetric about zero is unchanged by negation, and so is anything whose Left options are the negatives of its Right options. Each row carries the value, whether it is a nimber, and its outcome.

The values that are their own negatives

Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two in a group whose elements otherwise have infinite order. The nimbers do. So does ±1, on sight. Over the 1,474 values born by day three there are 30 of them and only four are nimbers, every one of the 900 sums of two is another, and the equality test and a symmetry of the written form agree 1,474 times out of 1,474.

sums · Negation Every day-three value, moved by every quarter. Four claims counted over 3,000 translations — 120 values, each moved by every quarter from −3 to 3: that adding a number leaves the temperature alone, that it shifts both stops by exactly itself, that the interval between the negated stops is where the two players are confused, and that the only failures of the last are on its endpoints.

What a number does to a fight

Adding a number to a position moves everything and changes nothing: over three thousand translations the temperature never once shifted and both stops moved by exactly the number added, every time. What the number decides is whether the fight is worth having — and the interval where the two players are confused is exactly the open interval between the negated stops, right in all 2,890 cases away from its endpoints and wrong in 110 that are all on them.

sums · Translation Where a switch stops being a switch. The same Left option with the Right one raised past it. While the Left option is above the Right one both players want to move, the bar spans a real fight and the temperature is half the gap. Where the two meet the position is the number plus a star — no longer a switch, and not a number either. Above that the simplicity rule takes over: the value is the simplest number strictly between the options, and there is nothing to fight about.

When a switch is not a switch

A position {a | b} with numbers on both sides is a fight only while a is above b. Sweeping the boundary with a fixed at 2 and b climbing from −2 to 3 turns up three regimes rather than the two the definition suggests: eight fights whose temperature is exactly half the gap, one position at a = b that is 2∗ and is not a number, and beyond that numbers chosen by the simplicity rule — which on 8 of 12 sampled cases is not the midpoint.

values · Switches 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 The fight never runs backwards. Each of the 22 values born by day two, drawn from its right stop to its left stop — what Right gets moving first, and what Left gets moving first, once the fight has been played out to a number. Every bar runs the same way. The left stop is never below the right one, which is what "both players are trying to improve their own position" amounts to, and the cold rows, where the two coincide, are drawn as a single point.

The fight never runs backwards

Left's stop is never below Right's — in every one of 1,780 distinct values, computed twice by two independently written routes, with nothing that disagreed anywhere. The inequality is what makes a mean value well defined and a fight a fight; and where it collapses to equality, 433 of the 460 cold positions turn out not to be numbers at all.

values · Stops 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 The 22 values born by day two, and the order they form. Each value sits above everything it is greater than, joined to what it covers. The order has 36 covering relations and is nine levels deep, and 52 of its 253 pairs are incomparable — and it is still a lattice: every pair has a least upper bound and a greatest lower bound among the same 22 values. Two values are marked, together with their join and their meet.

The simplest game above both

Values sit in a partial order, and a partial order is entitled to be ragged: two things with no least thing above them. The 22 values born by day two are not ragged at all. Every one of their 253 pairs has a least upper bound and a greatest lower bound among the same 22, and the order is distributive on all 10,648 triples — so it is a lattice, and the join of zero and star is one half.

values · Lattice 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 The fall stops. Comparability on days two, three and four, the last built and corrected.

A floor, and not a decline

Comparability fell eighteen points from day two to day three and the next day cannot be enumerated. It can be built — and the construction's bias measured one day lower, where the truth is known. Corrected, day four comes to 60.6 per cent against day three's 59.7: the fall was a one-day event.

sums · Comparison The day-four figure, twenty draws at a time. Corrected day-four comparability from twenty seeds of each of two constructions, as dots on a percentage axis, with the range of day three's four slices shaded and the single figure the earlier essay reported marked. The seeds spread over about twelve points and the two constructions agree.

Twenty draws and a second recipe

Day four's comparability was reported as 60.6 per cent against day three's 59.7, from one built sample and one calibration. Built twenty times with each of two recipes whose biases differ by six points, and calibrated against all 1,474 day-three values rather than a quarter of them, the corrected figure spreads over twelve points from seed to seed and the two recipes agree within one standard error. The floor survives; the decimal was one draw.

sums · Comparison

Named alongside it

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

ComparisonStar (∗)Outcome classCanonical formEqualityPartial orderBorn on dayExhaustive searchNumbersSwitchNormal playTemperature

All concepts