Infinitesimals

$\uparrow$ is the position $\{0 \mid \ast\}$. Left can move to zero; Right can move to star.

It is greater than zero — Left wins it whoever moves first. It is also less than $\tfrac{1}{1000000}$, and less than every positive number there is. Both statements are provable and neither is a figure of speech.

Why up is positive #

Show that Left wins $\uparrow$ moving second, and that Left wins it moving first.

Left moves first. Left moves to $0$. Right now has no move, and loses.

Right moves first. Right moves to $\ast$. Left then moves in $\ast$ to $0$, and Right has no move, and loses.

Both branches are Left wins, so $\uparrow$ is in outcome class L, which is greater than zero. Nothing subtle happened; it is two lines of play.

Why up is smaller than every positive number #

Take any positive number $x$ and show $\uparrow - x < 0$, that is, Right wins $\uparrow - x$ whoever moves first.

Right’s strategy: move in $-x$, repeatedly. Since $x$ is a positive number, $-x$ is negative, and Right has moves in it that keep it negative or take it to zero. Meanwhile Left’s moves in $\uparrow$ run out after two plies, and Left’s moves in $-x$ only make it more negative.

The essential point is that $x$ is a number, so moving in it is never urgent and its value is a fixed reserve. Right spends that reserve one move at a time; Left, having exhausted $\uparrow$, has nothing left to spend. Right makes the last move.

So $0 < \uparrow < x$ for every positive number $x$, however small. That is the definition of an infinitesimal, and it is a plain consequence of the two-move structure of $\uparrow$ set against the arbitrarily long reserve of a number.

The corresponding negative is $\downarrow = \{\ast \mid 0\}$, which is $-\uparrow$, and is negative and larger than every negative number.

Star, which is neither #

$\ast = \{0 \mid 0\}$ is not positive, not negative and not zero. Whoever moves first wins it, so it is confused with zero.

That makes $\ast$ a different kind of small from $\uparrow$. Up has a sign; star does not. Star is an infinitesimal in the sense that it is smaller in magnitude than every number, but it cannot be placed on the line at all.

The relation between them is worth holding onto:

$$\ast \parallel 0, \qquad \uparrow > 0, \qquad \uparrow \parallel \ast, \qquad \uparrow + \uparrow > \ast$$

The last one is the useful fact and the one that surprises. A single up is confused with star, so a player holding $\uparrow$ against $\ast$ is in a first-player-wins situation. Two ups beat star outright. So $\uparrow$ is a unit of something, and it takes two of them to overcome a star.

Where they come from #

Infinitesimals are not exotic constructions. They are what ordinary positions are worth when both players are nearly out of useful moves.

Consider a Hackenbush position of a blue edge on a red edge, next to a red edge on a blue edge. Each part is worth a fraction, and the parts nearly cancel — the remainder is an infinitesimal, and which infinitesimal decides the game.

More strikingly, there is an entire class of games in which every position is infinitesimal. These are the all-small games: games in which, at every position, either both players have a move or neither does. Since neither player can ever be the only one with moves, no position can accumulate a numerical advantage, and every value is smaller than every positive number.

Clobber is all-small, and so is Cutthroat. In those games numbers never appear at all, the whole of the numeric machinery is idle, and infinitesimals are not a refinement — they are the only values there are.

Toads and Frogs is not all-small, which makes it the more instructive example. A strip of toads with empty space ahead of them gives Left moves and Right none, so its value is a plain integer. But arrange the pieces so that both sides are equally cramped and the infinitesimals appear immediately: the six-cell strip T.TFF is worth exactly $\\uparrow$, and TTF.F is worth $\\downarrow$. Both were found by enumerating every strip up to seven cells and evaluating it.

Counting ups #

Once infinitesimals dominate, the practical question becomes how to compare them, and the answer is a rough count.

$\uparrow$ is the unit. A position worth $\uparrow\uparrow$ (two ups) beats one worth $\uparrow$, which beats $0$. Star sits confusedly among them: $\uparrow \parallel \ast$ but $\uparrow\uparrow > \ast$, so a star is worth somewhat less than two ups and not comparable with one.

The rough count is called atomic weight — approximately, how many ups a position is worth, ignoring differences of less than a star. A position of atomic weight two or more is a win for Left regardless of any stars floating around; a position of atomic weight zero is close and needs exact analysis.

That approximation is what makes all-small games playable. Exact infinitesimal values are unwieldy, and a single integer that says “about three ups, so comfortably winning” is what a player can actually use. It is the same move that temperature makes for hot games: replace an exact value with a number that answers the question at hand.

The other scale: tiny and miny #

There is a second family of infinitesimals, and it is smaller than the first by as much as the first is smaller than the numbers.

Tiny-$x$, written $\Uparrow_x$ in some notations and $+_x$ in others, is $\{0 \mid \{0 \mid -x\}\}$. It is positive, and for positive $x$ it is smaller than $\uparrow$ — very much smaller. Tiny-two is smaller than tiny-one, and tiny-a-million is smaller than anything anybody would write down.

So the infinitesimals are not a single scale. They stratify, and the stratification is infinite: below every infinitesimal there is a smaller positive value, and the ordering of the tinies mirrors the ordering of the numbers upside down.

The practical consequence is that “infinitesimal” is not a synonym for “negligible”. A position worth tiny-one and a position worth $\uparrow$ are both infinitesimal, and one of them beats the other decisively. In a close game the difference is the game.

The ordering, drawn #

The relations between the smallest values are easy to state and hard to hold, so here they are laid out.

Zero sits at the origin. Every positive number sits above it, however small, and every negative number below. Between zero and all the positive numbers is an infinite region, and $\uparrow$ lives there; symmetrically for $\downarrow$.

Star does not live anywhere. It is off the line, confused with zero, and also confused with $\uparrow$ and with $\downarrow$ — but not confused with $\uparrow\uparrow$, which strictly exceeds it, nor with $\downarrow\downarrow$, which it strictly exceeds.

So the picture is a line with a gap above and below zero, a cloud of nimbers off to one side of the origin, and the two clouds interpenetrating in a way that no diagram can quite show. Every figure of the small values on this site is therefore an approximation, and the approximation it makes is to draw confusion as a sideways offset — which is a convention, not a fact about the values.

$$\downarrow\downarrow < \ast < \uparrow\uparrow, \qquad \ast \parallel \uparrow, \qquad \ast \parallel 0$$

The middle relation is the one worth remembering. A star and an up together are a first-player win, which means a player holding exactly that much is not safe and not lost, and needs the move.

The switch that is not hot #

A small aside that catches people out.

$\{0 \mid 0\}$ looks like a switch: both players have a move, and the moves go to the same place. Under the simplicity rule’s hypotheses it fails the test, since Left’s option is not strictly below Right’s — they are equal.

But it is not hot either. A hot position is one both players are eager to move in because moving there gains something, and here neither gains anything: both moves lead to zero. What $\ast$ is, instead, is a position where having the move is worth exactly the move itself and nothing more — the minimal unit of tempo.

That is why $\ast$ has temperature zero while being confused with zero. Temperature measures how much is at stake, and in $\ast$ nothing is at stake except who is left standing. Positions like this are why temperature and outcome are separate questions.

A word on notation #

The arrows are unusually good notation and it is worth saying why, because notation is the standing hazard in this subject.

$\uparrow$ is a single character that names a specific two-node game, and $\uparrow\uparrow$ means $\uparrow + \uparrow$ rather than anything iterated. $\ast n$ names the nimber, $\ast$ alone means $\ast 1$. A position worth three ups and a star is written $\uparrow\uparrow\uparrow\ast$, which is compact and unambiguous once the conventions are in hand.

What the notation hides is the position. $\uparrow\uparrow\ast$ is four characters and the Toads and Frogs strip worth it is a row of pieces that takes a picture to convey. This site’s rule is that where brace or arrow notation appears, the position appears beside it — the compression is convenient and the position is the thing being talked about.

What the solver computed #

Every claim above is checked rather than asserted. lib/cgt.js constructs $\uparrow$ as game([ZERO], [STAR]), canonicalises it, and assertValue confirms it names as $\uparrow$.

The comparisons are computed by the definition — build the difference, ask who wins moving second — not by a table of known relations. So $\uparrow > 0$ is verified by playing out $\uparrow - 0$; $\uparrow \parallel \ast$ by playing out $\uparrow - \ast$ and finding the first player wins; $\uparrow + \uparrow > \ast$ by playing out $\uparrow + \uparrow - \ast$ and finding Left wins moving second.

The claim that $\uparrow$ is smaller than every positive number cannot be checked exhaustively, since there are infinitely many. What the build checks is the finite family that appears in the figures — $\uparrow < 1$, $\uparrow < \tfrac12$, $\uparrow < \tfrac{1}{1024}$ — each by the same difference computation. The general statement is the proof above; the figures show instances.

For the Toads and Frogs strips, values come from the position recursion and are cross-checked against outcome: a strip whose value canonicalises to a positive infinitesimal must be in outcome class L, and the build asserts it.

Why they decide close games #

A game that ends with a large numerical advantage is over before it is over — the arithmetic settles it and the last moves are formality.

A close game is one where the numbers cancel. What remains is the infinitesimal part, and that is where the outcome lives. So the practical role of $\uparrow$, $\downarrow$ and $\ast$ is that they are the residue after the visible advantages have annihilated, and they decide games that look drawn.

This is the reverse of the usual intuition, in which small quantities are safely ignored. Here small quantities are ignorable exactly when something larger is present, and when nothing larger is present they are everything. A Go endgame in which both sides have equal territory is decided by infinitesimals, and professional players have a vocabulary for these positions that predates the theory by centuries.

Infinitesimals in Hackenbush #

Hackenbush gives the cleanest picture of where these values come from, because the position can be read directly.

A stalk of one blue edge is worth $1$. A stalk of one green edge is worth $\ast$. A blue edge with a green edge on top is worth $\{0, ? \mid ?\}$ once the options are worked out, and reduces to $1 + \ast$ — the integer part and the star part simply add.

The interesting case is a green edge with a blue edge on top. Left can cut either edge; Right can only cut the green one, which takes the whole stalk. The value is $\uparrow$ — the position where Left has slightly more than nothing, and slightly less than any amount worth writing as a fraction.

That is the point at which the picture explains the value better than the algebra does. The blue edge is Left’s, and it is worth something; but it is standing on a green edge that Right can cut out from under it, so it is not worth a whole move, or half a move, or any fraction of one. It is worth an up.

Who found it, and when #

Up, down and star are Conway’s, and the notation is from Winning Ways — the arrows are Berlekamp, Conway and Guy’s, and they have been standard since 1982.

Atomic weight is developed in Winning Ways as the “uppitiness” of a game, a name that has not entirely survived into the literature but that captures what it measures. The theory of all-small games and their infinitesimal values is largely from that book, and the analysis of Toads and Frogs in it is one of the earliest worked cases.

The tinies came later in the exposition and are the part most often skipped, which is a shame, because the discovery that the infinitesimals stratify infinitely is a better illustration of what the recursion produces than any single value is.

Where the model stops #

Normal play. Under misère play none of this holds. The infinitesimals are creatures of the normal-play ordering.

Atomic weight is approximate. It ignores differences of less than a star, so two positions with the same atomic weight can differ in outcome when everything else is exactly balanced. It is a tool for deciding comfortable positions, not close ones.

Infinitesimal is not negligible. The tinies make this vivid. The word describes a comparison with numbers, not a claim of unimportance.

These values are small and the positions are not. $\uparrow$ has a two-node canonical form; the Toads and Frogs strip worth $\uparrow$ has a much larger tree, and reducing it is the expensive part. The figures use strips short enough to reduce exactly.

The ladder from here #

Nearby: atomic weight properly defined and computed; the tinies and minies with their ordering; all-small games as a class and the theorem that characterises them; and the specific analysis of Clobber, which is all-small and unsolved.

Then outwards to temperature, which is the opposite regime — positions so hot that infinitesimals are invisible — and the observation that a real game passes from one regime to the other as it ends, with the infinitesimals taking over exactly when the last hot move has been played.