Combinatorial Game Theory
who wins, and by how much
Concept

Form — where it appears

A particular way of writing a position down, as two lists of options, of which the canonical one is the smallest. Many forms carry one value: 256 built from the first day's games carry twenty-two between them.

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

What is left when the copies pair off. For each position, the difference between n copies and n times the mean, reduced to canonical form. The first two are drawn and the last column says what the sequence does after them: half of these settle into a short cycle and the rest produce a new leftover every time, all of them the same bounded size.

What is left when the copies pair off

A pile of n copies stays within a bounded distance of n times the mean, and the distance never grows. The difference is a game rather than a number, and what it actually is has a much better answer: for a plain switch it alternates between one fight and nothing at all, and for a fight with a follow-up it is different every time — bounded in size and unbounded in complexity.

temperature · Temperature 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 What a value costs to write down. Every one of the 1,474 values born by day three, grouped by the width of its canonical form, with the number of symbols the form takes when it is written out. Each count was obtained by walking the canonical form and counting its nodes, so a subposition appearing twice is counted twice — which is what writing it out does. The widest values of the day are not the longest to write.

What a value costs to write down

The canonical form is the smallest form of its value, and it is smallest in the one currency the reduction happens to spend: options. Counted in symbols it is nothing of the kind — the widest value born by day three is not the longest, the longest has six options rather than seven, and every canonical form on the day except the seven integers writes some position out twice.

values · Reversibility 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 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

Named alongside it

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

Canonical formDay threeBirthdayDay twoExhaustive searchNotationWidthDepthEnumerationGame treeIntegerMemoisation

All concepts