Combinatorial Game Theory
who wins, and by how much
Concept

Day two — where it appears

The twenty-two values the construction has produced after two days, small enough to draw and large enough to contain every kind of value. Fifty-two of its 231 pairs are incomparable, and the four games born the day before separate all twenty-two.

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

How much company equality needs. Each row restricts the quantifier in the definition of equality to the games named, and counts how many of the 22 values born by day two survive as distinct. The bar is the same number drawn; the jump from nine numbers to four games is the whole argument.

Equal in this company

Equality quantifies over every game there is, and the quantifier can be made smaller. Restricted to a company of nine numbers, the twenty-two values born by day two collapse to seventeen; restricted to four games — nought, one, minus one and star — they stay twenty-two, and no three of the four will do. The company that decides equality is tiny, and it has to contain a star.

limits · Universes One option list, as the order it is. The four options above, with an arrow from each option to every option it is at least as good as. Deleting keeps the one nothing points at and removes the rest, so the reduction takes three of them — a number read off the shape and not off the values.

How much a list of options can lose

Deleting a dominated option is the reduction with no surprises, and how many options it takes is decided by the shape of the order rather than by the values in it: the survivors are the maximal elements, and the count is the length of the list less the number of them. The essay separating the two reductions closed by predicting that the longest chain would give the number. It is a lower bound, exact on 3,859 of the 7,315 four-option lists and wrong on the rest.

values · Dominance How many options a value needs. The canonical form is the smallest form of its value, so the number of options it carries is a property of the value. Three days of the construction, with the widths that occur and the widest value of each.

How wide a form can get

Bypassing a reversible option replaces it with a whole option list, so a form grows in the middle of its own reduction. Whether it can come out wider than it went in is the question that leaves standing, and over 64,515 forms built from day-two options the answer is no, not once — the growth is real, it is transient, and the widest canonical form reached is exactly as wide as the widest form that reaches it.

values · Reversibility 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 Adding two thermographs. Every pair drawn from the 15 values born by day two that are not numbers — 120 sums — with the two walls added pointwise and compared against the true diagram of the sum. The added walls are always an outer bound and the means always add; the whole diagram is right for 92 of the 120, and the 28 it is wrong for are exactly the pairs in which both components are hot.

When two thermographs can be added

The temperature of a sum is not the sum of the temperatures, and the natural repair is to add the whole diagrams instead. Over every pair of hot values born by day two the added walls always bound the true ones and the mast always comes out right — and the whole diagram is right exactly when at most one of the two components is hot, which is precisely the case a reader has no use for.

temperature · Thermograph 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 a wider pool rescues. The misère outcome table built four times over, on pools of 10, 22, 100, 113 positions. A cell holds the set of outcomes that sums of its row class and column class actually took. Fifteen of the sixteen cells are short of all four outcomes on the smallest pool and none is on the largest, so every near-miss in the original table was a statement about the pool rather than about misère play.

What a wider pool rescues

The misère outcome table has sixteen cells, and over a pool of ten positions fifteen of them hold fewer than four outcomes — which looks like structure and might be a shortage of positions. Thirteen values further on there is nothing left: every pair of outcome classes takes every outcome, so the near-misses were the pool, and the prediction the rung below made was right.

limits · Misère play How hot a background has to be. Every pair of values born by day two that share a reduced canonical form, added to backgrounds of seven temperatures and three means — 609 comparisons in all — with the count of pairs whose outcome the swap changes. Safety is not monotone in the background's temperature, so the threshold the question asks for does not exist; every one of the 48 changes is at a position with a stop exactly on nought.

How hot a background has to be

The reduced canonical form throws away infinitesimals, and the rung below asked for a bound: how hot must the rest of the board be for the discarded part not to matter? There is no such bound. Safety is not monotone in the background's temperature — an eighth is safe, a quarter is not, two is safe again — and the quantity that does decide it is not a temperature but a stop.

sums · Reduced form The identity that would join the order to the addition. Every pair of the twenty-two values born by day two, asked whether the join plus the meet equals the sum. It holds on all 201 comparable pairs, where the join is the larger and the meet the smaller and it cannot do otherwise, and on none of the 52 incomparable ones.

Where the order and the sum disagree

Day two is a lattice, and day two is a group, and it is not a lattice-ordered group. The one identity that would join the two structures — the join plus the meet equals the pair — holds on exactly the 201 pairs where it cannot fail and on none of the other 52, and the errors split thirteen high, thirteen low and twenty-six confused.

values · Lattice What a day of canonical forms costs, written out and written once. Three costs for the values born by each of the first three days: every node written every time it occurs, every distinct subposition of a single form, and every distinct subposition of any form of the day. The last is one node per value, and the gap between the first and the last widens as the construction goes on.

The same position, written once

Writing out the canonical forms of day three takes 24,940 nodes. Naming each distinct subposition once inside each form takes 10,102, and naming each distinct subposition once across the whole day takes exactly 1,474 — one per value, because nothing appears inside a canonical form that is not itself a value of the day.

values · Reversibility Fifty-two errors, put to four instruments. The fifty-two discrepancies the lattice identity leaves on day two, counted by what distinguishes them. As values no two are the same; as pairs of stops there are seven; as means three and as temperatures three. Not one of them is a number, and only three are values born by day two.

Fifty-two errors and seven sizes

Day two is a lattice and a group and not a lattice-ordered group, and the fifty-two incomparable pairs it fails on leave fifty-two different error terms. Measured rather than listed, the fifty-two collapse: seven pairs of stops, three means, three temperatures, and a rule that predicts the temperature from the pair on forty-four of them.

values · Lattice What a finite closed company is made of. The finite closed companies found by the search, counted by the properties they share. Every one of them consists of games equal to their own negatives and has a size that is a power of two, and not all of them are made of nimbers.

The company that is closed

Restricted equality licenses substitution only inside a company closed under addition, and none of the five companies this site computes in is closed — day two keeps a quarter of its own sums. Searching for companies that are closed finds seven, at one, two, four and eight members, and every member of every one of them is its own negative.

limits · Universes How much of the value the colon respects. Every form whose option lists are antichains of day-two values, grouped by the value it reduces to, and each group asked whether all its forms give the same ordinal sum with star. On 636 of the 640 groups they do.

What the colon respects

The ordinal sum reads the form of its base rather than its value, which is why the colon principle is stated for positions and not for values. Built over 9,604 forms it turns out to read the value on 636 of the 640 values that have more than one form, and the four it can tell apart are zero, one, minus one and star — the values born by day one, and no others.

sums · Ordinal sum Star's fibre, described. The fourteen antichains whose mirror value is star, with the two conditions that pick them out of the ninety-six.

A mex with no impartial game in it

The rung below described the zero fibre of the mirror map and left star's fourteen undescribed. Star's fibre is 'some element is at least nought, and none is at least star' — and the two rules are one rule: the mirror value is the least nimber no element of the set reaches. That is a mex, in a construction built entirely from partizan values.

sums · Negation The order one day out. Whether the values born by day three still form a lattice. Twice as many pairs are incomparable as at day two, and every incomparable pair still has a least upper bound and a greatest lower bound — so the order becomes more tangled without becoming ragged.

One of four questions

Three rungs of this ladder rest on sweeps of day two — 22 values, 253 pairs. Day three is 1,474 values and over a million pairs, and only one of the four questions can be asked of it. The order can: twice as many pairs are incomparable and every one of 1,606 sampled still has a least upper bound and a greatest lower bound, none of them a value day two already had. The other three compare sums of day-three values, which are born on day six, and sixty of those exhausted an eight-gigabyte heap.

values · Lattice Where the two diagrams part. Pairs of hot day-two values with the true thermograph of their sum against the one made by adding the components' walls. Every pair parts, and every pair parts at the lower of the two temperatures.

The second bend is the boundary

Adding two thermographs wall by wall gives a diagram that is right at the mast and wrong below it. Over every pair of hot values born by day two, the added walls sit outside the true ones at every height — an outer envelope with the truth somewhere inside — and the two pictures separate at exactly the lower of the two temperatures, on all twenty-eight pairs. Above that height both components are still fights and the addition is exact; one sixteenth below it, every pair has parted.

temperature · Thermograph Writing a board as a sum, and as the value it is. Every sum of two, three and four games born by day two, written as the parts joined by plus signs and as the single value the sum equals, with the number of distinct values, the share that can be written without a brace, the share longer as one value than as a sum, the middle length each way and the longest single value. The single value is shorter in the middle and far longer at the top, and needs a brace more often the more parts there are.

A board is written as a sum

Every measurement of the brace notation so far has been of a single position, and nobody writes a single position. A board is several parts, and it can be written as the parts joined by plus signs or as the one value they add up to. Over every sum of up to four games born by day two, the one value is usually the shorter — and the share of boards that need a brace climbs with every part added, until the longest value is four times its sum.

history · Notation A position Left always wins, and not always. Values grouped by the outcome class alternating play assigns them, with the range of probabilities the coin gives Left inside each class. A class that alternating play calls a win for Left every time holds no position the coin makes certain.

Left always wins, and loses more often than not

Alternating play answers with one of four classes and the coin answers with a chance, and the two do not have to agree. Over the twenty-two values born by day two they never disagree and the margin is exactly nothing — the lowest chance on a position Left wins whoever moves is a half. Over the 1,474 born by day three, seven of them sit at seven sixteenths, and seven mirror them on the other side.

limits · Bidding Every chance the coin gives, by day 2. The probabilities the coin produces over all the values born by a given day, drawn on the unit interval. They fall on a grid of dyadic fractions, every interior point of it is reached, and the two ends never are — so no position is ever a certainty under random turns.

Every chance but a certainty

The coin's number lands on a grid of dyadic fractions, and which points of that grid arrive is a count rather than a guess. Over the 1,474 values born by day three it reaches every one of the fifteen interior sixteenths and neither end — no position is ever certain. The groups sharing a chance run 1, 2, 4, 8 on the small pool, which looks like doubling, and 1, 2, 4, 20 on the large one, which is not.

limits · Bidding Every region of three positions, counted. The 262,144 graphs on three positions reduced to the regions that are genuinely three positions with a cycle in them, and then split by whether the two-position vocabulary has a name for both of their sides.

Four thousand nine hundred regions with no name

Two positions give 256 regions and ten names cover every side of all of them. Three positions give 262,144 graphs, 110,934 genuine loopy regions — and 4,931 of those have a side that no name in the two-position vocabulary reproduces, with 3,990 of them named on one side and blank on the other. The count the earlier essay left open comes back in the affirmative.

history · Notation

Named alongside it

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

Canonical formEnumerationExhaustive searchStar (∗)Day threeDisjunctive sumPartial orderAdditivityBirthdayComparisonCounterexampleInfinitesimal

All concepts