Combinatorial Game Theory
who wins, and by how much
Concept

Construction — where it appears

Building values from earlier ones by one rule, which produces the numbers, the nimbers and everything past them. It has no stopping rule in it, and where it is stopped is exactly what this site can compute.

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

The days this site can compute, and the ones it cannot. Zero on the first day, ±1 on the second, and thereafter the simplest number in every remaining gap — the construction run by the game recursion, which produces only fractions with a power of two underneath however long it goes on. Below it, three objects the same recursion reaches when the stopping rule is removed, each written with its option set and the exact reason this site's machinery cannot hold it. They are named rather than drawn, which is the honest half of a figure-first collection.

The numbers came out of the game

The construction is always taught numbers first and games second, and the discovery ran the other way. Conway arrived at the number system from positions, which is why the definition quantifies over sets of previously built objects rather than over cuts — and why it produces a genuinely different collection at every finite stage.

history · Numbers The days this site can compute, and the ones it cannot. Zero on the first day, ±1 on the second, and thereafter the simplest number in every remaining gap — the construction run by the game recursion, which produces only fractions with a power of two underneath however long it goes on. Below it, three objects the same recursion reaches when the stopping rule is removed, each written with its option set and the exact reason this site's machinery cannot hold it. They are named rather than drawn, which is the honest half of a figure-first collection.

The recursion this site cannot run

Remove the stopping condition from the construction and it reaches ω, its reciprocal, and one third — none of which this site's evaluator can represent, because it interns a position from a finite list of options. The figure draws what it computes and names what it cannot, which is where the boundary belongs.

values · Numbers How old a sum is. Every unordered pair of the twenty-two values born by day two, with nought dropped because adding it settles nothing — 231 sums. The birthday of each sum was read off its own canonical form and compared with the sum of the two parts' birthdays, which is the bound. The bound holds everywhere and is attained 163 times.

The birthday of a sum

Two values born by days m and n have a sum born by day m + n at the latest, which is the bound that stops a board made of many small parts from being unboundedly complicated. Over 231 pairs of day-two values the bound holds every time and is exact 163 times — and every pair it misses by three days or more has a sum that is a number or a nimber, so the slack is not noise but a measure of how much cancelled.

values · Numbers How hot a day gets. The hottest value born by each of the first three days, with every temperature that occurs on it. Day one tops out at nought, day two at one, day three at two — a day buys exactly one degree — and the value attaining the maximum is unique each time. Each temperature was computed as the height at which that value's two thermograph walls meet. The temperatures of day three are exactly the half-gaps between the numbers born by day two, which is what puts a hole in the scale at 7/4.

How hot a day gets

A day of construction buys exactly one degree of temperature — nought, then one, then two — and the value attaining the maximum is unique on every day: ∗, then {1 | −1}, then {2 | −2}. The distribution underneath is not tidy at all: it peaks at a half, leans to the right of the peak, and has a hole in it at one and three quarters where nothing is born.

temperature · Cold What the third colour reaches. Every row of Toppling Dominoes up to 7 long, over two colours and over three, with the number of distinct values each set of rows carries. Each value was computed by the recursion; the last column is the count of values three colours reach that two do not, cumulatively.

How long a row a value needs

Add a third colour that either player may topple and a row of seven dominoes reaches 1,047 distinct values where two colours reach 149. That makes the length of the shortest row worth a value into a measure of the value's complexity — one a reader can hold in their hand — and it is not the birthday: 1↑ is born on day three and needs seven dominoes.

positions · Toppling dominoes A sequence with a rule and no period. The values of the subtraction game with Left taking 1 or 2 and Right taking 1 or 3, from heap 5 up. Each is the game whose only Left option is nought and whose only Right option is the value three heaps below — checked at every heap rather than asserted, and the two heaps where it fails are the two below the seeds.

A sequence with a rule and no period

The values of the subtraction game where Left takes one or two and Right takes one or three never repeat — thirty-one heaps, thirty-one different values. They are nonetheless completely described: three seeds and the rule v(k + 3) = {0 | v(k)} generate every one of them, which is what a pattern without a period looks like.

positions · Partizan subtraction Where sente stops, by what the answer costs. The largest ambient temperature at which a local move is still answered, sorted by how deep the fight below the answer runs. When the answer ends the fight the crossover is the follow-up's temperature; when the answer starts another fight it is exactly half of it, and a third level does not halve it again.

The answer that starts another fight

A local move is answered while the ambient temperature stays below the follow-up's — and that rule, which this site has carried since the anchor opened, is exact only when the answer ends the fight. When the answer starts another one the crossover is exactly half the follow-up's temperature, on every position tested, and a third level of fight does not halve it again.

temperature · Sente Moore’s rule, reversed. Moore’s Nim under the misère convention at three values of k, with the normal-play rule and the same rule plus a clause about heaps of one. The patch is the one Nim takes, with the modulus the normal-play rule already carries, and it is right on every position swept.

The patch that generalised

Misère Nim takes a one-line patch: play the normal-play strategy until every heap holds a single counter, then invert. Moore's Nim, where a move may take from up to k heaps at once, takes exactly the same patch with exactly the same modulus — and the two rules disagree on six positions out of 923.

impartial · Moores-nim How two genus symbols make a third. The composition rule for genus symbols, stated with its cases and checked on every pair of heaps of nine games. The base exclusive-ors, the sum is fickle only when every component is, and the symbol follows from those two.

The rule the symbols follow

Two genus symbols make a third by three lines and no lookup table: the base exclusive-ors, the sum is fickle only when every component is, and the symbol follows. Checked on 252 pairs across nine games it is right on 238 — and the fourteen failures are exactly the fourteen pairs with a wild heap in them, which is the boundary the genus is defined up to arriving as a measurement.

limits · Genus

Named alongside it

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

Exhaustive searchBirthdayStar (∗)Canonical formDay threeDyadic rationalInfinitesimalOutcome classRecursionTemperatureClosed formCounterexample

All concepts