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.

The smallest members of the class are the ones the previous rung drew against a number and found nothing: $\uparrow$, $\Uparrow$, $\uparrow\!\ast$, $\ast$ and $\downarrow$ are each strictly less than $1/1024$, and so is every other member, which is precisely why that comparison is the wrong one to make here. This essay makes the other one.

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.

Three cases is a pattern and not yet a rule, so here is the same family carried out to a fourth, on an axis wide enough to hold it.

Why the star costs two and not one, and not three #

The figure reports a width of four and the report is worth converting into an argument, because both halves of it are two lines of play and neither needs the calculus.

One up is not enough. $\uparrow$ and $\ast$ are confused, which is to say $\uparrow \ast$ is a first-player win. Left moving first plays the star away and leaves $\uparrow$, which is positive. Right moving first plays $\uparrow \to \ast$ and leaves $\ast + \ast = 0$ with Left to move, and Left loses a game worth nought moving first. So neither $\uparrow \ge \ast$ nor $\uparrow \le \ast$, and the bracket cannot close at one.

Two ups are enough. $\Uparrow \ast$ is a win for Left moving second, so $\Uparrow > \ast$. Right’s only moves are into the star, leaving $\Uparrow > 0$, or into one of the ups, leaving $\uparrow + \ast + \ast = \uparrow > 0$. Every reply Right has hands Left a positive game, which is the whole proof.

So the width is four exactly: two in each direction, and the same argument runs unchanged with $n\!\cdot\!\uparrow$ in place of nothing, which is why $\uparrow\!\ast$ brackets to $[-1,3]$ and $\Uparrow\!\ast$ to $[0,4]$. Adding a star translates nothing and widens by four.

And it is worth noticing what the argument does not depend on. It never mentions how large the position is, so the cost of a star is a constant rather than a proportion — a bracket of width four around an atomic weight of forty is a good measurement and one around an atomic weight of one is useless. That is the precise sense in which the calculus’s error term is bounded, and the precise reason a position whose atomic weight is $0$ or $\pm 1$ is not decided by it.

Two stars cost nothing at all, because $\ast + \ast = 0$ and the position is back where it started. The obstruction is not the presence of a nimber; it is the presence of an odd one.

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.

The distinction the unit has to respect is the one the four outcome classes already draw. Three of the four are comparisons with zero — Left wins, Right wins, the second player wins — and the fourth is not: a first-player win sits nowhere on the line. $\uparrow$ is in the first group and $\ast$ is in the fourth, and that single fact is the whole reason one of them is the yardstick and the other is what obstructs it.

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 $-N$ to $N$, records the largest $n$ passing $G \geq n\!\cdot\!\uparrow$ and the smallest passing $G \leq n\!\cdot\!\uparrow$, and reports the pair. $N$ is the half-width of the axis each figure draws — four here, six where a bracket needs the room — and a bracket that ended on the axis edge would be a measurement of the axis rather than of the position, which is why every one above stops short of it.

The two counting figures are the same routine run over a game instead of over a list. Every one-row Clobber position of each length is enumerated, evaluated, and bracketed; the pair census then takes every unordered pair of the rows up to six squares and compares the verdict the two brackets give with the verdict compare gives, which is 7,875 comparisons done twice.

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.

The word “approximation” is doing work there and can be given a number. Take every Clobber row up to six squares, form every pair of them, and ask two questions of each pair: what the two brackets say about the ordering, and what the comparison itself says.

Neither number on its own is the interesting one. That the bracket is never wrong is a theorem restated; that its silence is mostly silence about pairs with no answer is a fact about Clobber rather than about the measurement, and it is the reason a coarse instrument is usable here 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.

Everything bracketed so far was written down as a sum of ups and stars, which is the case the measurement was designed for. The interesting test is a value nobody chose.

That row of widths — nought, one, two and four — is the honest range of what comparison returns, and only two of the four were predictable from the essay so far. A bracket is not a pinned answer or a four-wide band; it is whatever the comparisons happen to establish.

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.

And a width can be counted rather than admired. Every row of Clobber up to seven squares has a bracket; how many of them are pinned to a single multiple of up is a question with an answer.

A width of five is the useful entry in that last column, because it is a width no constructed position in this essay produced and it arrives at six stones. The bands comparison returns are not drawn from a small vocabulary of nought and four — a real game hands out nought, one, two, three, four and five, and it does so within seven squares of a row.

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.

The rungs above take the two things this one leaves open. Tiny and miny goes below the reach of the ups entirely — an empty two-by-four Domineering board is worth less than nothing and more than every negative number, and is not a multiple of down but a miny, one of an ordered family sitting under a floor no number and no count of ups reaches. All-small games supplies the class a real board produces: Clobber is all-small everywhere by the shape of its rule, three stones in a row are worth exactly up, and the whole apparatus stops being a curiosity about constructed values.

And when the ups add settles the “very nearly” this page has been careful with. Over all 120 pairs from a fifteen-game family, the sum’s bracket is exactly the sum of the parts’ brackets 56 times, strictly narrower 64 times, and wider never — so a bracket is a genuine bound on a sum rather than an approximation to one. The line separating the two cases is short: every one of the 54 pairs with a pinned part is exact, and only two of the other 66 are. Which is the star’s cost again, seen in a sum rather than in a single position.

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.