Two hundred and fifty-six ways to write twenty-two things

Day zero has one game in it: the position with no moves at all, worth zero. Day one has four, built by giving Left and Right each a subset of what day zero contains — the empty set or $\{0\}$ — which yields $0$, $1$, $-1$ and $\ast$.

Day two is built the same way, from the four. Left may be given any of the sixteen subsets of them, and so may Right, so there are $16 \times 16 = 256$ positions to write down.

There are not 256 values. There are twenty-two.

The gap between 256 and 22 is the whole content of this essay, and it is easy to describe wrongly.

It is not that 234 of the forms are mistakes, or badly written, or redundant in some clerical sense. Every one of them is a perfectly good position: a real game somebody could play, with its own option lists and its own tree. What is true is that many of them are indistinguishable inside every larger game — swap one for another anywhere, in any sum, and nobody’s winning chances change.

That relation is what “the same value” means here, and it is defined by subtraction: $G = H$ exactly when $G - H$ is a second-player win. It quantifies over nothing — no “for every larger game” appears in the test — and yet it certifies a statement that does.

Nothing in that test mentions a larger game, and it certifies a statement about all of them — which is why two forms in one of the bars above are interchangeable everywhere and not merely equal in isolation. A Hackenbush stalk and an abstract game can land in the same bar, and either may then stand in for the other inside any position at all.

So a value is a class of forms, and the census counts the classes. What the bar chart adds is that the classes are wildly different sizes: sixty-four of the 256 forms are worth $1 \mid -1$, the switch, while exactly four are worth $\ast 2$. Nothing about the construction suggests that in advance.

The reduction, and the choices inside it #

The mechanism that collapses a form to its class representative is the canonical form, and it has two rules.

A dominated option goes. If Left has two options and one is at least as good as the other, the worse one can be deleted — Left would never take it, so its presence changes nothing.

A reversible option is bypassed. If a Left option $G^L$ has a Right answer $G^{LR}$ with $G^{LR} \leq G$, then Left moving there can be answered so as to leave Right no worse off than before the move started. That option is replaced by the Left options of $G^{LR}$: the move is reversed through it.

Now the observation this essay exists for. At a given moment several options may be dominated and several reversible. The rules say what may be done; they do not say what to do first. Somebody carrying out the reduction has to choose, and the textbook statement of the theorem — every game has exactly one canonical form — is silent about whether the choice matters.

Uniqueness is a claim about the process #

It matters a great deal, and the claim it amounts to has a name borrowed from rewriting: confluence. Whatever choices are made, the reduction ends in the same place.

The trails in that figure differ by two whole steps. One route reaches $\ast$ in three; the other takes five, passing through forms the short route never sees. If the answer depended on the route, “the canonical form of $G$” would not name anything, and the practical consequence would be severe: two positions could be equal and have different canonical forms, so equality could no longer be decided by comparing forms, and the compression the whole apparatus buys would be gone.

Uniqueness is two claims, not one #

Borrowing confluence from rewriting is exactly right, and the borrowing brings a second word with it that the theorem also needs. Every game has exactly one canonical form decomposes into two independent statements, and neither implies the other.

Termination. The reduction stops. That is not obvious here, because one of the two steps can make the form bigger — a bypass removes one option and inserts a whole list, and 60 of one census’s forms end up with canonical forms wider than they started. What actually falls is the node count: a bypass replaces a subtree by pieces that were already inside it, so the total strictly decreases, and a strictly decreasing count of nodes cannot decrease for ever.

So the width is free to move and the node count is not, and the question that leaves is whether the width ever ends up higher than it started. It is a count rather than an argument, and it depends on which forms are counted.

Which is not the same as saying it never happens: the sixty above are forms whose options are day-three values, one level below the pool swept here, and how wide a form can get is where the two counts are reconciled. The point that survives either way is the one termination needs — the falling quantity is the node count, and the width is not being promised anything.

Confluence. Wherever it stops, it stops in the same place. That is this essay’s subject, and it is what the twenty-six orders test.

Neither is a consequence of the other, and both failures are easy to picture. A system can be confluent and non-terminating — every route agrees and none of them ever finishes, so there is no canonical form to be unique. And it can terminate and not be confluent — every route finishes and different routes finish differently, so “the canonical form” names several things and equality can no longer be decided by comparing forms.

So the textbook sentence is doing two jobs, and this site now checks them separately: the node count for one, the twenty-six orders for the other.

Which is why the width can grow without alarming anybody #

That decomposition also settles a tension between this essay and the one about reversibility, which a reader meeting both will feel.

The reduction is a simplification and the reduction can make the form wider look like they cannot both be true. They are both true, and they are about different quantities. Width is not the measure the termination proof uses, and nothing in the theorem ever claimed it was.

What the reduction guarantees is a unique stopping point, reached by any route, with strictly fewer nodes than it started with. What it does not guarantee — and does not need to — is that every step, or even the whole journey, makes the option lists shorter.

And that is why watching the width is the wrong way to be reassured. The trails in the figure above pass through forms of different sizes and different shapes; what makes them trustworthy is not that they shrink monotonically but that they agree at the end and that something else was falling all the way.

That is the ordinary condition of a rewriting system, and it is worth having the vocabulary for, because “simplification” is a word that suggests monotone shrinking and this reduction does not do that. It normalises. The two are different, and only one of them is what the theory needs.

Width is still worth measuring, for a reason that has nothing to do with reassurance: the canonical form is the smallest form of its value, so the number of options it carries is a fact about the value rather than about anybody’s notation.

Every form born by day two, in every order #

One figure is one position. The claim is about all of them, so the site’s gate reduces all of them.

Each of the 256 forms is put through twenty-six different orders: first-available, last-available, and twenty-four pseudo-random choosers driven by a fixed seed so that a failure is reproducible and the build is deterministic. Every run must finish at the same form, and that form must be the one canonical() produces by its own route.

Two things came out of running it, and the second was a surprise.

234 of the 256 had something to reduce. The other twenty-two were already canonical when written, which is what one would expect: writing a position down with no dominated and no reversible option is not hard when there are only four options to draw from.

Not one of them took a different number of steps depending on the order. At day two the reduction is not merely confluent — it is confluent with a fixed step count, which is a stronger and quite unnecessary property. It is also not general. The position in the figure above is one rung deeper, and its two routes take three steps and five.

There is a second thing true of all 256 that the orders do not see, and it is what makes “already canonical” the interesting category rather than a technicality.

That is worth pausing on as a lesson about checking. The first version of this gate reduced one form per value rather than every form — and the first form built for a given value is almost always one that is already canonical, so it reduced twenty-two games that had nothing to reduce and reported a pass. The test that caught it was the one sitting beside it asking whether any reduction had happened at all. An assertion that has never had anything to assert is indistinguishable from one that works.

What the collapse is for #

It is worth being blunt about why anybody would want 256 things to become 22, because “tidier” is not the answer and would not be worth a theorem.

Equality between positions is defined by a condition that quantifies over every game in the universe: $G$ and $H$ are equal when they are interchangeable inside any larger position. Checked directly that is not a computation at all — there is no way to try every larger position. The canonical form turns it into a finite one twice over. First, equality reduces to a single outcome question: $G = H$ exactly when the second player wins $G - H$. Second, and more usefully, two games are equal exactly when their canonical forms are identical trees, so the test becomes a comparison of two small strings.

Both reductions call that first test rather than the second. A dominated option is one that loses a comparison against a sibling, and a reversible one is an option whose answer loses a comparison against the whole position — and a pair that comes back confused, with neither direction holding, is exactly the pair where neither option dominates the other and both survive into the canonical form.

That second form of the test is what makes the rest of the site possible. Adding two positions produces a tree whose size is the product of the summands’, and without a reduction at every step a sum of six components would be unmanageable. With one, the sum stays the size of its value rather than the size of its history — which is why a Domineering board can be broken into regions and the regions added up, and why a value can be quoted at all.

Why the counts are so uneven #

The bar chart’s shape is worth an explanation, and it is a consequence of what the two reductions actually delete.

The largest class, at sixty-four forms, is the switch $1 \mid -1$. Any form whose Left options include $1$ and whose Right options include $-1$ reduces to it, because $1$ dominates both $0$ and $-1$ on Left’s side and $-1$ dominates both $0$ and $1$ on Right’s — so all four of the other option choices on each side are simply deleted. Four free choices on the left and four on the right: sixty-four forms, one value.

The smallest classes, at four forms each, are the ones needing a specific option set that nothing else reduces to. $\ast2$ is $\{0, \ast \mid 0, \ast\}$ and nothing collapses onto it; the four forms are the ways of writing the same two option sets with a redundant copy that deduplication removes.

Fifteen of the twenty-two are not numbers. Two are nimbers, four are up-and-down values, two are a number with a star added, and nine have no short name at all and are printed as brace expressions. That ratio is the reason this subject exists: if every position were a number the theory would be arithmetic with extra steps.

The day after that was thought to be out of reach #

Day three is built from day two the same way day two was built from day one: choose any subset of the twenty-two for Left and any for Right. That is $2^{22} \times 2^{22}$, which is about $1.8 \times 10^{13}$ forms.

Reducing eighteen trillion positions is not a build step, so this essay left the published count of values born by day three — 1,474, Conway’s figure, from the same census that gives 1, 4, 22 for the first three days — as a quotation rather than a computation.

It need not have been. The enumeration that skips forms is the one this paragraph asks for, and it is the reduction itself that supplies it: a canonical form has no dominated option, so each side of one is an antichain of the day-two order, and there are only 98 of those. Ninety-eight choices a side is 9,604 forms rather than eighteen trillion, and the site now computes 1,474 in a quarter of a second.

That gap between 22 and 1,474 is worth looking at beside the gap between 4 and 22. The values are growing far faster than the days, and the forms faster again: the number of ways to write a position down is doubly exponential in the birthday while the number of things worth writing is merely enormous. The whole point of a canonical form is to work in the second quantity rather than the first.

What the solver computed, and how #

The census is a double loop over the sixteen subsets of the day-one games, building game(L, R) for each pair and taking name(canonical(...)). Nothing is skipped and nothing is cached across the loop except the interning that game() does anyway.

The confluence check needs more than canonical() provides, because canonical() runs the reductions to a fixed point internally and hands back the answer. So the site carries a second, slower implementation that exposes the steps: stepsOf lists every reduction legal at this instant, applyStep carries one out, and a chooser decides which. That is the only place on the site where a piece of machinery is deliberately reimplemented, and the justification is that the two implementations are checked against each other — every trail must end where canonical() says it ends.

The random choosers use a fixed-seed generator rather than the clock. A confluence failure found by an unreproducible random walk would be a report that something is wrong and no way to look at it.

Where the model stops #

Everything here is at day two. The gate reduces 256 forms and one deeper position. Confluence is a theorem for all games and this is evidence at one size.

“The same number of steps” is an observation, not a result. It holds at day two, fails one rung deeper, and nothing here says where the boundary is or whether there is one.

The forms counted are forms over a fixed pool. A “form born by day two” here means one whose options are day-one games. A position of birthday two can also be written with options that are themselves written redundantly, and counting those is a different and much larger question.

Duplicated options are removed silently. game(L, R) interns on the sorted option identities, so writing $\{0, 0 \mid 1\}$ and $\{0 \mid 1\}$ produces the same object before any reduction happens. That is a third collapse, sitting underneath the two the theory names, and it is why the smallest classes come out at four forms rather than one — the four are genuinely different subsets that happen to describe the same two option sets. A census that counted written strings rather than option sets would give larger numbers everywhere and would be counting typography.

Who found it, and when #

The reduction and its uniqueness are Conway’s, from On Numbers and Games (1976), where the canonical form is introduced precisely so that equality can be decided. The census 1, 4, 22, 1474 is his as well; the day-four count was established much later by computer, and is a number with twelve digits in it.

The word confluence comes from the study of rewriting systems, where it names the property that makes a normal form well defined, and it was not part of the original presentation. Borrowing it is useful here because it moves attention from the answer to the process, and the process is where the choices are.

It also names the thing that goes wrong when it fails, which is worth knowing since it fails elsewhere in this subject. Misère play has no canonical form of this kind: the reductions that work under the normal-play convention are not sound when the loser is the player who cannot move, and what replaces them is a quotient computed separately for each game rather than a normal form that works everywhere. That is the clearest measure of what is being bought here. Uniqueness is not decoration on top of a value theory; it is most of what makes one.

Where the ladder goes next #

This is the second rung on the canonical-form ladder. The first introduces the two reductions and shows one position before and after; this one asks what the reductions are doing to the whole population of positions and whether the order they run in matters.

The rung after asks the question this essay’s last section dodges: what does the canonical form cost to compute? Both reductions call comparison, comparison is subtraction followed by a search, and the search is over the sum of two game trees. The complexity of that is not the complexity of deciding who wins, and the difference between the two is a rung of its own.