How many ups

A close game ends in a position where nobody is ahead by anything a number can express. Every component is smaller than every positive number and larger than every negative one, the total is somewhere in the same territory, and the question of who wins is entirely open.

Numbers are useless there, and not by a small margin — every number is either an upper bound on the whole position or a lower one, so comparing against numbers separates nothing. The values are still exact and still add; they simply have no numerical size, and something else has to be the yardstick.

All-small #

The class in question has a clean definition and an unhelpful name.

A game is all-small when either player having a move implies the other has one too, all the way down. Zero is all-small. $\ast$, $\uparrow$, $\downarrow$ and every sum of them are all-small. A number other than zero is not, because one player has a move in it and the other does not.

The name is unhelpful because it suggests smallness of value, and what it actually describes is a structural symmetry of the option lists — a condition on the shape of the position rather than on what the position is worth. The consequence is smallness: every all-small game is an infinitesimal, strictly between $-x$ and $x$ for every positive number $x$. The consequence is what matters and the definition is what can be checked.

$$G \text{ all-small} \iff G = 0 \text{ or } (G^L \neq \varnothing \text{ and } G^R \neq \varnothing \text{ and every option is all-small}).$$

That is decidable by recursion, and the machinery on this site decides it that way rather than by trying to recognise a value.

Up as the unit #

If numbers cannot separate these positions, something inside the class has to. The natural candidate is $\uparrow$ itself: it is positive, it is all-small, and its multiples $n\!\cdot\!\uparrow$ march steadily upward through the class.

So the question becomes: how many ups is a position worth? And the honest first answer is that comparison can bracket it.

For a game $G$, let $\ell$ be the largest integer $n$ with $G \geq n\!\cdot\!\uparrow$, and $h$ the smallest with $G \leq n\!\cdot\!\uparrow$. Both are found by testing — build $n\!\cdot\!\uparrow$, subtract, ask who wins the difference moving second — and nothing about the answer is assumed in advance.

For $\uparrow$ itself the bracket is $[1,1]$. For $\Uparrow$ it is $[2,2]$. For $\downarrow$ it is $[-1,-1]$. Those are exact, and they are what a reader would expect.

For $\ast$ the bracket is $[-2, 2]$.

The star, and the four ups it costs #

$\ast$ is confused with zero, so it is not $\geq 0\!\cdot\!\uparrow$ and not $\leq 0\!\cdot\!\uparrow$. Comparison against zero therefore fails in both directions, and the bracket has to widen until it finds multiples that do work.

It finds them at $\pm 2$. $\Downarrow < \ast < \Uparrow$, both strictly, while $\downarrow$ and $\uparrow$ are both merely confused with $\ast$. So the bracket is four wide, centred on zero.

The same thing happens to every position with a star in it. $\uparrow\!\ast$ brackets to $[-1, 3]$ — four wide, centred on $1$. $\Uparrow\!\ast$ brackets to $[0, 4]$ — four wide, centred on $2$.

That is a pattern and it is worth stating carefully, because the centre of each bracket is the number a player would want:

$$\ast \to 0, \qquad \uparrow\!\ast \to 1, \qquad \Uparrow\!\ast \to 2.$$

The number in the middle is the atomic weight, and what the figure shows is that comparison against multiples of up locates it to within two in each direction and no better. The star is what blocks the last two: adding one to a position makes it incomparable with everything within two ups, and comparison has no way to see past that.

Why up and not something else #

Choosing $\uparrow$ as the unit looks arbitrary until the alternatives are tried, and they are worth trying, because the reason it works is the reason the whole measurement is possible.

The obvious first candidate is $\ast$. It fails immediately: $\ast$ is confused with zero, so it is not positive, and multiples of it do not increase — $\ast + \ast = 0$, and the whole family collapses to two elements. A yardstick has to be ordered and the nimbers are not.

The second candidate is a very small number, $2^{-k}$ for large $k$. That fails for the opposite reason: every all-small game is smaller than every positive number, so a scale made of numbers puts the entire class in one bin however fine the numbers are made.

$\uparrow$ works because it is the smallest thing that is both strictly positive and inside the class. Positivity gives it a direction; membership gives it resolution. Both are needed, and nothing simpler has both.

There is a satisfying symmetry in the fact that the thing which makes the measurement possible and the thing which limits it are both consequences of the same partial order. Up is measurable because it compares with zero; star breaks the measurement because it does not; and both facts are the partial ordering doing what it does.

What the solver computed, and how #

Every bracket in the figures is a run of comparisons and nothing else.

Building $n\!\cdot\!\uparrow$ is repeated addition of $\uparrow$, or of $\downarrow$ for negative $n$. Comparison is the site’s ge, which computes $G - H$ and asks whether Right, moving first, can win it — the definition, not an approximation to it. The loop runs $n$ from $-6$ to $6$, records the largest $n$ passing $G \geq n\!\cdot\!\uparrow$ and the smallest passing $G \leq n\!\cdot\!\uparrow$, and reports the pair.

Before any of that, the generator checks that each position is all-small and refuses to draw a bracket for one that is not. A number would produce a bracket running off the end of the range, and reporting that as a measurement would be worse than reporting nothing.

The site’s gate makes both halves of the pattern into a claim that can fail. Positions with no star — $\uparrow$, $\Uparrow$, $\downarrow$, $\Downarrow$ — must bracket to a single value, exactly. Positions with a star must bracket to a range exactly four wide, centred on the expected atomic weight. Either being wrong fails the build, and the two requirements pull in opposite directions, so a bug that widened everything or narrowed everything would be caught by one of them.

The all-small test is separately given a number and required to reject it.

Where the model stops #

A bracket is not an atomic weight. The atomic weight is a single number produced by a calculus with its own rules — a recursion on the options with a correction for the star. What comparison gives is the evidence for it, and where a star is present the evidence is two short at each end. This essay reports the bracket, because the bracket is what the code here computes.

The unit is a choice, and a good one, not the only one. Multiples of $\uparrow$ are not the only infinitesimals; there are all-small games strictly between $0$ and every $n\!\cdot\!\uparrow$, and games not comparable with any multiple at all. Measuring in ups works for a large and practically important part of the class and does not exhaust it.

All-small is not the same as infinitesimal. Every all-small game is an infinitesimal; the converse fails. $\{0 \mid \uparrow\}$ has values smaller than every positive number without both players having moves everywhere, and atomic weight is defined for the all-small class specifically.

Normal play, and the ordering it depends on. Comparison is defined by who wins a difference playing second, which is a statement about who moves last. Under misère play there is no ordering to bracket in, and none of this survives.

What it is for #

The point of counting ups is the same as the point of counting anything: to decide sums.

In a position that is a sum of all-small components, the total’s atomic weight is very nearly the sum of the components’ atomic weights, and the sign of that total decides the game — which is the same service the nim-sum performs for impartial positions, one class further out — a position with strongly positive atomic weight is a win for Left, one with strongly negative for Right. That is the same service ordinary numbers perform for ordinary positions, and it is available exactly where ordinary numbers are useless.

The words “very nearly” and “strongly” are load-bearing and are the price of the star. Atomic weights add exactly when no star interferes; when one does, the sum can be off by a bounded amount, and a position whose atomic weight is $0$ or $\pm 1$ is not decided by it at all.

So the honest summary is that atomic weight is a good approximation to a hard exact quantity, with an error term of a couple of ups, in a class of positions where every alternative is no approximation at all. That is a much stronger claim than it sounds, because the exact computation is exponential in the size of the position and the atomic weight is not.

Where it shows up #

The class is not exotic. Games in which both players always have the same availability of moves, even when the moves themselves differ, are all-small by construction, and several well-studied games are of exactly that kind.

Toads and Frogs produces all-small positions readily, and it was the game that made the infinitesimals feel necessary rather than decorative. Hackenbush with green edges produces them. Clobber, in which every position has both players able to move or neither, is all-small everywhere and is where atomic weight is a working tool rather than a curiosity.

The general situation is a close endgame. Once the large fights are settled and the numbers have been counted, what remains is a pile of components each worth nothing in the accounting sense, and the game is decided by how many ups are in the pile. A player who stops counting when the numbers run out has stopped one layer too early.

What the picture cannot show #

The bracket figure is a row of bars on a line of integers, and that drawing quietly asserts something it has no right to.

It puts the multiples of up on an axis, evenly spaced, as though they were positions on a ruler. They are not spaced at all in any metric sense — there is no distance between $\uparrow$ and $\Uparrow$, only an ordering — and the even spacing is a drawing convention with nothing behind it. Nothing in the theory says $\Uparrow$ is “twice as far from zero” as $\uparrow$; it says only that it is greater.

The figure also cannot show what lies between the marks. There are all-small games strictly between $\uparrow$ and $\Uparrow$, infinitely many of them, and the axis has no room for any. Every gap in that picture is densely occupied and the drawing represents each as empty.

What the bracket figure does show honestly is the width: which positions comparison pins down and which it does not, and by how many steps of the ordering. That is a statement about the number of successful comparisons, and it is the only thing the picture is entitled to say.

The generalisation #

Atomic weight is one step in a tower and it is worth seeing the shape of the tower.

Numbers measure positions that are settled. Temperature measures positions that are hot. Atomic weight measures positions that are all-small — infinitesimally close to zero, where both of the first two report nothing.

Each layer is a different yardstick applied where the previous one has no resolution, and each comes with its own error term. The pattern continues below: there are infinitesimals too small for atomic weight to see, measured against still smaller units, and the tower does not terminate.

That is a genuinely unusual feature of this subject. Most theories have one notion of size. This one has a sequence of them, each exact in its own range and blind outside it, and a complete analysis of a position may need several at once.

Who found it, and when #

Atomic weight, and the calculus for computing it, is from Winning Ways — Berlekamp, Conway and Guy, 1982 — where it appears under the heading of the “atomic weight calculus” and is developed alongside the theory of all-small games.

The name is a deliberate joke with a point in it. The ups are the atoms; a position’s atomic weight is how many of them it amounts to; and the analogy extends far enough that the authors were able to talk about positions being “heavier” or “lighter” and have that mean something exact.

The remoteness of the star — the fact that a star costs precisely two ups of precision in each direction and no more — is the technical heart of the calculus and is what makes the approximation bounded rather than merely usually-good.

The ladder from here #

This anchor began with the infinitesimals themselves: what they are, that they exist, and that they are not zero. This rung asks how to measure them, and finds that comparison alone gets within two.

Later rungs: the atomic weight calculus proper, which closes the gap the bracket leaves. The theorem on when atomic weights add exactly. Positions whose atomic weight is not an integer, and what the calculus does with them. The infinitesimals below the reach of ups, and the units used there. And the practical question of when a close game is decided by atomic weight and when it is not, which is the difference between a tool and a theorem.

What this rung establishes is the measurement and its limit. The bracket is exactly what comparison can see, the star is exactly what blocks the rest, and both facts are printed on the figure rather than argued for.