What is left when the small change is thrown away

Three essays on this site name the reduced canonical form as a later rung and none of them writes it. This is the rung.

Canonical form answers the question which positions are equal?, where equal means interchangeable inside any larger game whatever. That is the right question and it is a demanding one. $\uparrow$ and $0$ are different games, and exhibiting a sum that tells them apart requires a background made of nothing but infinitesimals — a sum of ups and downs and stars, with no fight anywhere in it.

A player in a real endgame does not have one. The rest of their board is hot, and against anything hot an infinitesimal difference cannot change who wins. So there is a second, coarser question — which positions are equal for practical purposes? — and it has an exact answer.

$$G \approx H \quad \text{when} \quad G - H \text{ is infinitesimal}$$

The reduced canonical form is the simplest representative of each class under that relation.

The clause #

The reduction is the ordinary one with a first clause added.

$$\text{RCF}(G) = \begin{cases} x & \text{if } \text{LS}(G) = \text{RS}(G) = x \\ \text{reduce}\{\,\text{RCF}(G^L) \mid \text{RCF}(G^R)\,\} & \text{otherwise} \end{cases}$$

The condition in the first line is that the two stops agree. A stop is what a player gets by moving first and fighting on until somebody is left facing a number, and if the two agree there was nothing to fight over: the position sits infinitesimally close to that number, and the replacement discards precisely the infinitesimal.

It is the same condition as temperature zero or below, stated in a different vocabulary — the rung at the bottom of the temperature scale is exactly the set this clause fires on. Three hundred and thirty-seven of the day-three values are in it.

The order it reduces against is not the game order #

The recursion above hides the part that matters, and getting it wrong produces something that passes every obvious check and is not the reduced form.

Recursing into the options and then applying the ordinary canonical reduction gives a game infinitesimally close to the original. It satisfies the definition of $\approx$ perfectly: the difference is infinitesimal for all 1,474 values, with no exceptions. What it is not is the simplest such game, and two values in the same class come out with different answers — so the map is not a function of the class, and the whole point of a canonical form is gone.

The repair is to reduce against the coarser order. Write

$$A \trianglelefteq B \quad \text{for} \quad A \le B + x \ \text{ for every positive number } x$$

which holds exactly when the left stop of $A - B$ is at most zero. It is coarser than $\le$: it holds whenever $\le$ does, and also in the cases where $\le$ fails by an infinitesimal.

Under $\trianglelefteq$ more options are dominated and more are reversible, so more comes off. That is the whole reason the reduced form is smaller than the canonical one, and it is why “canonical form, plus a clause about numbers” is not a correct description of the algorithm.

What it collapses #

The seven day-two values that reduce to zero are $0$, $\ast$, $\uparrow$, $\downarrow$, $\uparrow\!\ast$, $\downarrow\!\ast$ and $\ast 2$. Every infinitesimal on the list, together with zero itself.

That is exactly right and it is the point. Against a background with a fight in it, none of those seven can be told from any of the others — they differ by amounts smaller than every positive number, and a fight is worth a positive number. A player who has decided to ignore the small change should ignore all seven together.

Five of the ten day-two classes hold a single value: $2$, $-2$, $\tfrac12$, $-\tfrac12$ and $\{1 \mid -1\}$. The first four are numbers, which the reduction has no work to do on; the fifth is the only genuine fight born by day two, and it survives untouched because its stops are a whole unit apart and no number stands between them.

The other four non-zero classes are the interesting ones, because each is a value with its own infinitesimal neighbours gathered around it. $1$ and $1\!\ast$ reduce to $1$; $-1$ and $-1\!\ast$ reduce to $-1$; $\{1 \mid 0\}$, $\{1 \mid \ast\}$ and $\{1 \mid 0, \ast\}$ all reduce to $\{1 \mid 0\}$, and their negatives likewise. In every case what comes off is a star somebody could not see.

At day three the picture is the same shape and much more extreme: 1,474 values, 61 classes, 292 of them reducing to zero and another 350 reducing to $\{0 \mid -1\}$ or $\{1 \mid 0\}$. Eighteen classes hold a single value.

Whether a sum may be reduced part by part #

An operator that throws away information is only useful if it survives addition, because the whole reason to compute a value is to add it to another one.

It does, and the true statement is not the one a reader writes down first.

$$\text{RCF}(G + H) = \text{RCF}\bigl(\text{RCF}(G) + \text{RCF}(H)\bigr) \quad \text{always}$$

$$\text{RCF}(G + H) = \text{RCF}(G) + \text{RCF}(H) \quad \text{not always}$$

The second fails because the sum of two reduced forms need not itself be reduced. A Left option of $G + H$ is $G^L + H$ or $G + H^L$, and one of those can be dominated by the other in the sum while neither part had anything to dominate it. So there is genuinely something to remove at the top level, and the outer reduction is what removes it.

That is not a subtlety of this operator. It is the general shape of a quotient map: $\approx$ is a congruence, so the class of $G+H$ is determined by the classes of $G$ and $H$, and choosing the simplest representative is a separate step that has to be done after the addition rather than before.

The ordinary canonical form needs the second pass too #

It is worth adding that the two-pass requirement is not a peculiarity of this operator, because a reader meeting it here for the first time will take it as a sign that the reduced form is worse behaved than the ordinary one.

It is not. Take $\ast$, which is its own canonical form, and add it to itself. The sum, written out, is $\{\ast \mid \ast\}$ — a perfectly good form, and not canonical: its two options are reversible and the reduction takes it to $0$.

So $\text{canonical}(G) + \text{canonical}(H)$ is not canonical either, and every essay on this site that adds two values and quotes the answer has silently run the outer reduction. Nobody remarks on it because the evaluator reduces on every construction, so a form is never seen in its unreduced state.

The reduced canonical form inherits exactly the same discipline and no more. What makes it look like a new problem is only that the essay wrote the two statements down side by side, which the ordinary case never bothers to do.

The compression, end to end #

Setting the two reductions in a line gives the whole chain from what can be written to what has to be distinguished, and the numbers are worth having together.

Day three’s option sets produce 9,604 forms. Canonicalisation takes those to 1,474 values — a factor of six and a half, and the thing it is throwing away is spelling: two forms of one value are two ways of writing the same position.

The reduced canonical form takes 1,474 to 61 classes — a further factor of twenty-four, and what it throws away is a difference smaller than every positive number.

Together: 9,604 written forms, 61 things a player with a hot board has to tell apart. A factor of a hundred and fifty-seven, in two steps that discard two completely different kinds of surplus.

The day-two column is worth reading beside it, because the two steps scale quite differently. Canonicalisation gets less effective as the day grows — 11.6 forms per value at day two against 6.5 at day three — since the larger pool of options makes more genuinely different values rather than more spellings of the same ones. The reduction goes the other way: 2.2 values per class becomes 24.2, because each new day builds a fresh crop of infinitesimals around every value it already had, and those are exactly what the clause throws away. A player who ignores small change is buying more with each day that passes.

And the two steps are not comparable in status, which the chain makes easy to see. The first is free: two forms of one value are interchangeable everywhere, so nothing whatever is lost and any essay may use either. The second is a decision — it is exact about what it discards and the discarded thing is real, and there are sums in which it decides, which is what the next section is about.

So the right way to read the chain is that only one of its two factors is a saving. The other is a choice of question, and the twenty-four is the price of asking the coarser one — paid in positions that can no longer be told apart, and worth paying exactly when the board has a fight on it.

The company in which it is safe #

The reduction is exact about what it discards, and the honest question is when the discarded thing decides anyway.

Against a cold background the two members of a class part company eight times in fifteen, which is what the infinitesimal was for. $\uparrow$ beside $\uparrow$ is a Left win and $0$ beside $\uparrow$ is a Left win, but $\ast$ beside $\uparrow$ is a first-player win and $\downarrow$ beside $\uparrow$ is a second-player win — four values from one class, four different answers, against a background of a single up.

Against a hot background they usually agree, and the four exceptions are the interesting part. All four are cases where the total comes out balanced on a knife edge: $-1$ and $-1\!\ast$ both added to $\{1 \mid -1\}$ give a first-player win and a Right win, because $\{1 \mid -1\}$ has stops at $1$ and $-1$ and adding $-1$ lands the total exactly on a stop.

So the safe statement is narrower than “hot backgrounds are safe”:

The reduced form is safe against a background whose fight is large enough that the total is not left balanced. A hot background that happens to cancel the position exactly is a cold background in disguise.

The two coarsenings side by side #

There are now two operators on this site that take a value to something simpler by throwing information away, and they are easy to confuse.

Chilling charges a tax of one on every move and freezes what the tax overtakes. It takes every position of temperature at most one to a number, and it takes 1,474 day-three values to 29.

The reduced form replaces a position whose stops agree by the number they agree on and leaves everything else with its shape. It takes every position of temperature at most zero to a number, and it takes the same 1,474 values to 61.

So the reduction is the gentler of the two, and it is gentler in a principled way: it discards only what no number can see, whereas chilling discards whatever a tax of one can reach, and one is a number chosen because Domineering mostly runs there.

The other difference is what happens afterwards. A chilled value has to be warmed back to mean anything in the currency of the game; a reduced value is already in that currency, because the reduction never changed the scale. That is why the reduced form can be handed to a reader as an answer and a chilled value cannot.

What the picture cannot show #

A reduced form looks like a value and carries no record of what was thrown away. $0$ as a reduced form may have been $0$, or $\ast$, or $\uparrow\!\ast$, or any of 292 things at day three, and nothing in the symbol says which.

That is the same information loss chilling inflicts, arrived at by a different route, and the two are closely related without being the same. Chilling charges a tax and freezes what the tax overtakes; the reduced form asks whether the stops agree and replaces if they do. Chilling by one takes every position of temperature at most one to a number; the reduction takes every position of temperature at most zero to a number and leaves the rest with their shape.

The second thing the picture cannot show is that the reduction is relative to a class of backgrounds that is never written down. “Practical purposes” means “sums containing something hot”, and no definition on this page says how hot. The definition given is exact — $G - H$ infinitesimal — and the justification is a claim about the sums a player meets, which is a claim about games rather than about values.

Reading a reduced form as an answer #

The practical use is worth spelling out, because it is what distinguishes this reduction from a piece of bookkeeping.

Take a board that has fallen into six regions, five of them settled and one still a fight. The exact value of the whole is a sum of six canonical forms, and it is a large object. The reduced form of the same sum is a number plus, at most, one fight — and if the fight is worth $\{1 \mid 0\}$ then the answer to who wins and by how much is a sentence a player can hold.

What the player gives up is the ability to answer a question about a cold board. If the fight is settled and the five remaining parts are all infinitesimal, the discarded small change is the entire content of the position, and the reduced form says $0$ and means nothing by it. The reduction is a tool with a stated domain, and the domain is boards with something at stake.

Who found it, and when #

The reduced canonical form is Dan Calistrate’s, from the mid-1990s, and the theorem that makes it a canonical form at all — that each class has a unique simplest member, reachable by the reduction above — is his. Grossman and Siegel later gave a corrected and complete treatment, which is worth knowing about because the original algorithm had a gap of exactly the kind this essay’s third section is about: the reduction has to be carried out against the coarse order and the details of doing so are fiddlier than they look.

The motivation was thoroughly practical and it came from Go. Berlekamp’s endgame method chills a board, adds the chilled values, and reads the total back; the values it produces are numbers plus small change, and the small change is often irrelevant to the point count. A canonical form that keeps every infinitesimal is keeping bookkeeping the method has already decided to ignore.

That the object turned out to have a clean theory — a congruence, a unique representative, a homomorphism — was not obvious in advance. A coarsening chosen for convenience usually fails to be one of those.

The convention this rests on #

Everything here is normal play, and the dependence is total rather than incidental.

The relation $G \approx H$ is defined by $G - H$ is infinitesimal, which needs subtraction, which needs every game to have a negative. Under misère play no game but zero has one, so the relation cannot even be written down, let alone shown to be a congruence.

The coarse order $\trianglelefteq$ needs the same thing twice over: it is defined by a comparison with $B + x$, and it is decided by a stop, and stops are defined by playing a difference out. Take away the group and there is nothing left of the definition.

So this is one of the reductions that does not transfer. The misère theory’s analogue of “positions that are interchangeable for practical purposes” is the misère quotient, which is built by a completely different route — by finding which positions are indistinguishable within a stated universe of games, rather than by subtracting one from another.

Where the ladder goes next #

The first rung is the class of backgrounds made explicit. “Infinitesimally close” is exact and “safe in practice” is not, and the quantity that would join them is a bound: how hot must a background be, in terms of its temperature and its stops, for a class’s members to be interchangeable in it? The four hot exceptions above are the data such a bound has to accommodate.

The second is the sum’s reduced form computed from the parts’ — an arithmetic on reduced forms rather than a reduction of a sum. The homomorphism says such an arithmetic exists; nothing here says what it looks like, and it would be the analogue of adding thermographs.

And the third is the same coarsening applied one level up. The reduced form ignores infinitesimals; there is a further reduction that ignores everything below a stated temperature, which is what an endgame with a coupon stack does implicitly, and it has a whole family of canonical forms indexed by the tax.