The reduction that always shrinks

Canonical form is always introduced as one procedure with two clauses. Delete the options nobody would take; bypass the options that backfire; repeat until neither applies. The two clauses arrive together, they are motivated together, and they are almost always run together, because canonical() runs both to a fixed point and hands back the answer.

They are not the same kind of operation, and the difference is visible in a single line of the definition. Deleting a dominated option removes one option from a list. Bypassing a reversible one replaces an option with the entire option list of the position that answers it — a list that may be longer than one, and whose members were never options of the original position at all.

So one of the two reductions is monotone by construction and the other is not. This essay is about what the monotone half is worth on its own.

The two clauses, and what each one may look at #

A Left option $A$ is dominated when Left has another option $B$ with $B \ge A$. The comparison is between two options of the same player and involves nothing else. Delete $A$ and the position is unchanged, because a Left who would have played $A$ plays $B$ instead and is no worse off.

A Left option $A$ is reversible when Right has a reply $A^R$ from it with $A^R \le G$, where $G$ is the position itself. The comparison is between an option’s option and the whole position, which is a different shape of claim: it reaches down two levels and back up to the top. The repair is to replace $A$ by the Left options of $A^R$ — to let Left, in effect, take the two moves at once.

The asymmetry follows immediately. Deleting compares two things a player already has, so it needs the player to have two. Bypassing compares one thing the player has against the position, so it works on a player with exactly one option, and it is the only reduction that does.

The census #

Building the forms out of the games born by day one gives 256 of them — every pair of subsets of $\{0, 1, -1, \ast\}$ — which is the pool two hundred and fifty-six ways to write twenty-two things is about. Running the deletions to a fixed point on each and comparing the result with the canonical form gives the three counts.

Twenty-two forms need no reduction at all: they are already canonical, and the coincidence with the number of values born by day two is a coincidence — a value’s canonical form is one form, and 22 of the 256 forms happen to be those.

Two hundred and twenty-five are finished by deleting. That includes the 22 that needed nothing, so 203 of them are reduced to canonical form by deletions alone.

Thirty-one are not. Those are the forms this essay is actually about.

What the thirty-one have in common #

Twenty-eight of the thirty-one contain a star.

That is not a curiosity about this pool, it is the mechanism. Deleting needs a comparison between two options of the same player, and the whole reason the values are a partial order rather than a total one is that some pairs have no comparison between them. Star is the smallest such obstruction there is: it is confused with $0$, larger than every negative number and smaller than every positive one, and so it sits beside $0$ in an option list with nothing to be said about which is better.

A player holding $\{0, \ast\}$ therefore has an option list that deletion cannot touch, whatever else is true of the position. The list is an antichain — a set of mutually incomparable elements — and deleting a dominated option is exactly the operation that shortens a list until it is an antichain. Once it is one, deletion is finished, and whether the form is canonical is somebody else’s business.

How much deletion can ever do is therefore a fact about the order rather than about the reduction. The twenty-two values born by day two make 253 pairs between them, and 201 of those pairs are comparable while fifty-two are not — and every option list drawn from an incomparable set is a list deletion leaves exactly as it found it.

Fourteen of the thirty-one are that at its most complete: not a single option in them is beaten by a sibling, so deleting removes nothing at all and the form that comes out of the deletion pass is the form that went in.

The three forms in the thirty-one with no star are the other case, and it is the simpler one: $\{\,\mid 1\}$, $\{-1 \mid \,\}$ and $\{-1 \mid 1\}$, each with one option or none on each side. There is nothing to compare, so deletion has no purchase, and the reduction that does the work is the one that compares an option with the position.

Between them the thirty-one carry only seven values — $0$, $\pm 1$, $\pm \tfrac12$, $\uparrow$ and $\downarrow$ — which is a small enough set to look at directly, and every one of them is a value whose canonical form is narrower than the form that produced it.

Deleting is monotone and bypassing is not #

The count that matters is the width. The 256 forms carry 1,024 options between them. After every available deletion has been made, 544 remain; after the whole reduction, 504.

So deleting removes 480 options and bypassing removes 40, and the second number is a net figure. A bypass can put more options in than it takes out — it substitutes an option list for an option — and the day-two pool is precisely the pool in which it never does, because no game born by day one has two options on the relevant side. One day later it does, and the same census run there reports a reduction that sometimes makes a form wider on the way to making it narrower.

That is the sharp form of the asymmetry:

Deleting a dominated option always removes exactly one option. Bypassing a reversible one removes a number of options that can be zero, or negative.

A reader meeting the reduction for the first time reasonably assumes it is a shrinking process throughout, because the language is the language of simplification. Half of it is.

Why the order does not matter anyway #

None of this threatens uniqueness. The canonical form is unique, and it is unique regardless of the order the two reductions are applied in — a property that is worth stating in the vocabulary of rewriting, where it is called confluence, and worth checking rather than quoting.

What the split does affect is what a reduction by hand feels like. Deleting is local, mechanical and safe: compare, cross out, repeat, and the form is smaller every time. Bypassing requires holding the whole position in view while looking two levels down, and it can leave more written on the page than before. Somebody working an example who has only ever deleted will conclude that canonicalisation is bookkeeping. The 31 forms are where it stops being bookkeeping, and they are 12 per cent of the pool.

A second pool, and what moves #

The pool decides the numbers, so the honest thing is to change the pool and look.

Take the six values $0$, $-1$, $-2$, $1$, $\ast$ and $\tfrac12$ — the first six born by day two, which is a set with one incomparable pair in it and five ordinary numbers — and build every form from them. That is 4,096 forms carrying 24,576 options.

The share of forms that deletion finishes rises from 88 per cent to 96, and the share of options it accounts for rises from 92 per cent to 99. Both move the same way and for the same reason: the pool is five numbers and a star, numbers are totally ordered among themselves, and a long list of mutually comparable things collapses to its best member in as many deletions as there are members to lose.

That is the general shape of the answer and it is worth stating as a prediction rather than as a result. Deletion’s share of the work is a function of how comparable the option lists are, and nothing else. A pool of numbers gives deletion everything; a pool of infinitesimals, which are mutually incomparable in great quantity, would give it almost nothing. The values born by day three are neither, and where the ratio settles there is a measurement nobody has made.

What the count cannot say #

The figure at the head of this essay reports one pool, and the pool is not neutral. Building forms from the four games born by day one gives option lists of length at most four drawn from a set with exactly one incomparable pair in it. Almost everything about the balance between the two reductions is a fact about that.

A pool built from the values born by day three has 1,474 members and a great many incomparable pairs, so there is far more for deletion to fail to do and far more for it to succeed at, and the ratio between the two moves. What the two censuses above establish is not a proportion that will hold at scale — they disagree with each other, and the direction they disagree in is exactly the direction the comparability of the pool predicts. What they establish is that the proportion is not one or zero: deleting alone is neither the whole reduction nor a negligible part of it, and both of those are the sort of thing a reader might assume.

A third thing they cannot say is anything about a form nobody would write down. Every form in both pools is an arbitrary pair of subsets, and almost none of them is the value of a position in a game anybody plays. The values real rulesets actually produce are a different and much stranger list, and whether deletion does more or less work on those is a question with a different answer and no reason to have the same one.

The second thing the count cannot say is anything about cost. Both reductions are decided by comparisons, and a comparison of two games is itself a search — it means playing the difference of the two positions out. The 480 deletions and the 40 bypasses were not equally cheap, and nothing here measures that. What is measured is how many options each clause is responsible for removing, which is a statement about the result and not about the work.

The convention this rests on #

Everything above is normal play. Under misère play the reduction to canonical form does not work at all — not because the two clauses are harder to apply, but because the theorem that licenses them is false. Deleting a dominated option is justified by “Left plays the better one instead”, which needs the order on games, which needs the group structure, which misère play does not have. The reduction is one of the several things there that has to be rebuilt rather than adjusted.

Within normal play the reduction is also relative to what counts as equality, and equality here is the demanding kind: two positions are equal when neither player can tell them apart inside any larger game whatever. Loosen that — ask only for positions that play the same against anything with a fight in it — and a coarser reduction becomes available, with a coarser order to delete against, and a great deal more comes off. That is the reduced canonical form, and it is the same two clauses applied against a different comparison.

Who separated them, and when #

Both reductions are in On Numbers and Games, and Conway states them together as the two ways an option can fail to matter. The names are older than that in spirit — a dominated option is the game-theoretic sense of dominance, which is a phrase from decision theory, and reversibility is Conway’s own. Winning Ways gives the pair a slogan, “delete the dominated, bypass the reversible”, which is a good mnemonic and is exactly the arrangement this essay is complaining about: the slogan is a single rhythm, and it hides that the two halves have different shapes.

The place the difference is usually noticed is in a proof rather than in a count. Every proof that the canonical form terminates has to handle the two clauses separately, because the deletion argument is one line — the form gets smaller — and the bypass argument is not. Siegel’s Combinatorial Game Theory sets out the termination proof carefully for exactly that reason, and the induction it runs is on the birthday of the position rather than on the size of the form, because the size of the form is not what decreases.

So the separation is well known to anybody who has proved the theorem and invisible to anybody who has only applied it. The count above is an attempt to make it visible from the applying side.

Where the ladder goes next #

One thing this page’s own claim gains from the rungs above, and it is worth stating before them. Deletion is called the reduction that always shrinks, and the six rungs establish in what currency that is true: it shrinks the count of options monotonically and by an amount fixed by the order’s shape, and it shrinks nothing a reader can see from the board without doing the comparisons. Those are different guarantees, and only the first is the theorem.

dominance opens here, and the six rungs above it follow one question all the way down: how many options does deletion take, and can a reader predict which ones survive without running the comparisons?

How much a list can lose answers the counting half exactly. The survivors are the maximal elements of the order on the option list, so the number deleted is the length of the list less the number of maxima — a fact about the shape of an order rather than about the values sitting in it. It also tests the guess this page ends on. The longest chain is a lower bound on the deletions and not the number: exact on 3,859 of the 7,315 four-option lists swept, and wrong on the rest.

Then the ladder leaves the abstract lists for a board, where the options are moves and a player might hope to recognise the survivors by looking. Which option the reduction keeps scores two descriptions over 1,586 Domineering option lists: one is right 47 per cent of the time and the other 90, and the winner is not the one a player would guess — it is leave the opponent fewest replies.

The last four rungs are that rule being cornered. The margin a count needs weakens it into a bound: over 57,879 pairs of options, the one leaving the opponent fewer replies is the worse of the two 1,052 times at a margin of one, seventy-two times at a margin of two, and never at three. The weight that blunts the count tries the obvious repair — weigh a reply by whether it leaves the opponent anything — and it makes the rule worse in every direction, with all seventy-two of the pairs it was written for coming through unchanged.

The threshold was a fact about the census then looks at those seventy-two one at a time and finds they are not a class of shapes at all: they sit on the largest board of the census, at two depths, on sixteen positions up to symmetry — and one board larger the rule fails at a margin of three, which the ladder had been quoting as the point where it never does. A threshold is a detection limit closes it with eleven more sweeps: no property of a board orders the thresholds, the same board at two depths gives two of them, and what moves on every board measured twice is the depth rather than the size.

That is a ladder whose last three rungs are about the instrument rather than about the game, and it is worth knowing before starting it. Deletion is the reduction with no surprises; predicting it from a board turns out to have all of them.

And the direction the whole ladder runs in: the gift horse principle adds options rather than removing them, under a condition that is the negation of domination with the comparison turned around. Domination says an option beaten by a sibling may go; the gift horse says an option that does not beat the position may come. They are the same comparison read in the two directions, and between them they say exactly which option lists are the same position written differently.