When the ups add

How many ups left an interval rather than a number. Measure an all-small position against the multiples of ↑ — the largest n it is at least, the smallest n it is at most — and what comes back is a bracket: [1, 1] for ↑, [−1, −1] for ↓, and [−2, 2] for ∗, which comparison cannot pin down at all.

That is a measurement of one position. The whole reason to have it is that real endgames are sums, and the sum is the object this subject is built to handle. So the question the next rung has to ask is whether the measurement survives the operation: given the bracket of G and the bracket of H, what can be said about the bracket of G + H?

The expectation going in was that the brackets would mostly add, and that the interest would lie in the cases where a sum came out worse determined than its parts. The computation says otherwise, and it says so in a way that admits no exceptions.

The family, and the bracket each member gets #

The family fixed for the whole essay is fifteen all-small games, small enough to compute exhaustively and varied enough that nothing is being proved about ups alone: ↑, ⇑, ↓, ∗, ∗2, ∗3, ↑∗, ⇑∗, ↓∗, the positions {∗ | ↓} and {∗, ↑ | ∗, ↓}, three Clobber boards, and two green Hackenbush edges stacked. Every bracket quoted below is that game measured against the multiples of ↑ from −8 to 8.

Four of the fifteen are pinned — their bracket has width zero, a single integer with no slack in it. Those four are ↑, ⇑, ↓ and the Clobber position 1×3 xxo, which is worth ↑ exactly. Everything else gets an interval, and the reason is always the same: a star somewhere in the position, confusing it with the multiples of ↑ that ought to have bounded it.

The Clobber boards are in the family because they are not constructed from ups and stars at all. A Clobber move takes one of a player’s own stones onto an adjacent enemy stone and removes it, and since adjacency is symmetric, a player has a move exactly when the opponent does. That is what makes Clobber all-small everywhere, and it means the family contains games whose values were discovered rather than written down.

The bound that cannot be violated #

The first question to settle is whether the bracket of a sum can ever come out wider than the sum of the brackets. There is no such case in the family, there is none in a wider check, and there cannot be one.

The argument is two lines. A bracket’s lower end is a statement of the form G ≥ a·↑, and its upper end a statement of the form G ≤ b·↑. Greater-than in this subject is defined by playing the difference and asking who wins moving second, and that relation is preserved by addition: if G ≥ a·↑ and H ≥ b·↑ then G + H ≥ (a+b)·↑ directly, because the two differences can be played side by side and the second player wins each. The same holds for the upper end with the inequality reversed. So the added interval always contains the computed one.

The sum of the brackets is therefore an upper bound on the sum’s bracket and never a lower one — a containment, not an equation. The word “add” in this essay’s title is an over-claim in one direction, and the whole finding is what happens in the other.

The exhaustive search puts the count at 56 of 120. Fewer than half the pairs add exactly, the remaining 64 are strictly tighter than the arithmetic would allow, and nothing is wider. A wider family of twenty-five games, run below, gives 325 pairs and the same zero.

Where the sum is sharper than its parts #

The interesting question is therefore not where additivity fails upward but where it fails downward: where two vague parts make a sharp whole.

The clearest instance is the smallest. ∗ has bracket [−2, 2], four wide. Two copies of it add to a bound of [−4, 4], eight wide — and ∗ + ∗ is zero, whose bracket is [0]. Eight ups of slack disappear. Nothing about either part predicts it; the collapse happens because the two stars annihilate, and the bracket of a part has no way to record which star it was confused by.

That is the sharpest narrowing this family of fifteen produces, and it happens in 18 of the 120 pairs. The histogram of narrowing, in ups gained, is 56 pairs exact, 9 tighter by one, 2 by two, 25 by four, 10 by six and 18 by eight — better than half improve on the bound, and a seventh by the maximum the family allows.

One pinned part is enough #

The split between the 56 and the 64 is not a scatter. It has a rule, and the rule is short enough to state without qualification.

Every pair with at least one pinned part adds exactly — 54 of 54, no exceptions. And of the remaining 66 pairs, in which neither part is pinned, exactly 2 add exactly.

Both of those two are the same sum arriving twice: ∗2 + ∗3 = ∗, and ∗3 + green EE = ∗, since two stacked green edges are worth ∗2. Each part brackets to [−1, 1], the bound is [−2, 2], and ∗ brackets to [−2, 2] as well. The addition is exact by coincidence rather than by structure — the sum happens to be the one member of the family whose bracket is as wide as the bound allows.

So the honest statement of additivity is conditional, and the condition is about one part rather than both. If either component’s bracket has width zero, the sum’s bracket is the sum of the brackets and there is nothing left to compute. If neither does, the bound is almost certainly loose, and the only way to find out how loose is to add the games.

A rule that holds on 54 pairs of fifteen games is a rule with one family behind it, and the way to find out whether the family was doing the work is to change the family. Ten more all-small positions were added: zero, ⇓ and ⇓∗, ∗4, a single green edge, 3·↑∗, two more Clobber rows, and two positions written in brace form — one of which brackets five wide, a width the first family never produced.

Two things survived the enlargement and one did not. The containment survived, as it must. The pinned-part rule survived exactly — 54 of 54 became 135 of 135, with the accidental exactness still confined to nimbers that happen to sum to ∗. What did not survive is the proportion: the larger family is exact on 42 per cent of its pairs rather than 47, because the ten new members are mostly unpinned and unpinned pairs are where the bound goes loose.

A single star is the widest thing in the family #

One fact in the bracket table a reader who knows the subject would guess wrong explains the shape of the whole census.

The bracket of ∗ is [−2, 2], four wide. The bracket of ∗2, ∗3, ∗4, ∗5 and ∗6 is [−1, 1], two wide. Every nimber above the first is bracketed twice as tightly as ∗ itself. The simplest star in the game is the hardest one to measure.

The reason is a single pair of comparisons. ∗ is confused with ↑ and confused with ↓ — the difference ↑ − ∗ is ↑∗, a first-player win, so neither is at least the other. That kills the multiples −1 and 1 as bounds, and the bracket has to run out to ±2 to find something that works. But ∗2 is not confused with ↑: the difference ↑ − ∗2 is {0 | ∗3}, a win for Left, so ∗2 < ↑ strictly. Symmetrically ∗2 > ↓. The bounds at ±1 hold, and the bracket stops there.

A larger nimber is a bigger position and a smaller obstruction. That inverts the intuition that confusion grows with the value, and it is why the site’s up-bracket figure states a rule about stars that holds only for the positions it draws. What is true in general is narrower: the star costing four ups of slack is ∗ specifically, and it costs exactly that wherever it is placed. The bracket of n·↑∗ is [n−2, n+2] for every n from 0 to 4 — width four, always — while the bracket of n·↑ for the same n has width zero. The star is the whole of the difference.

The midpoint, and the one bracket of odd width #

A bracket’s midpoint is the number a player wants — 0 for ∗, 1 for ↑∗, 2 for ⇑∗ — and it is tempting to treat that midpoint as the atomic weight and ask whether it adds even where the interval does not.

It very nearly does. The midpoint is additive in 111 of the 120 pairs. All nine exceptions involve the same game: {∗ | ↓}, whose bracket is [−2, −1], the fifteen-game family’s only bracket of odd width, and whose midpoint is therefore −1.5 rather than an integer at all. Two copies of it have midpoints summing to −3, and the sum’s bracket is [−3, −2], midpoint −2.5.

That is a satisfying failure, because it is of exactly one kind and it is visible in the object rather than in the arithmetic. Every bracket in the fifteen whose width is even has a midpoint that behaves; the one whose width is odd does not, and it takes eight other pairs down with it. Widen the family and the pattern widens with it rather than dissolving: the twenty-five carry four odd-width brackets and forty-three broken midpoints, which is the same rule counting more objects.

It is also a warning against the obvious shortcut. The midpoint is not an atomic weight, and this essay does not call it one. It agrees with the atomic weight wherever both are known — the pinned positions and those of the form n·↑∗ — and everywhere else it is a summary statistic of a comparison result. A quantity that is additive 111 times out of 120 is a good heuristic and not a theorem, and the difference is the error term — the same lesson outcomes teach one class further out, where three pairs of first-player wins produce a Left win, a second-player win and a first-player win and the summary of the parts settles nothing about the sum. A bracket is a coarser summary than an outcome class; a midpoint is coarser still.

Every one of the nine failures is {∗ | ↓} in one of its pairings, so the whole exception can be drawn by fixing that one game and varying what it is added to.

What the solver computed, and how #

Every number above is a run of comparisons and a count, with no formula anywhere.

A bracket is computed by building n·↑ for each n from −8 to 8, subtracting it from the position, and asking who wins the difference moving second. That is the definition of the partial order rather than an approximation to it, and it is the same routine that decides whether two positions are equal in every company. The largest passing n on the ≥ side and the smallest on the ≤ side are the two ends, and the range is wide enough that no bracket in the family runs off it — a bracket touching ±8 would mean a truncated answer.

The census is then an exhaustive search over unordered pairs with repetition: 15 × 16 / 2 = 120 of them. For each, the two brackets are added coordinatewise and compared against the bracket of the summed game. Three counters accumulate — exact, narrower, wider — and the narrowing is recorded in ups, so the histogram falls out of the same pass.

The assertion is what makes it a test rather than a report. Containment is checked on every row, and the routine throws if a sum’s bracket ever escapes the added one. Since the containment is a theorem that assertion should never fire, and an assertion that can never fire proves nothing — so the reverse direction is also exercised, by feeding the machinery a position that is not all-small and requiring it to refuse to bracket at all. The exhaustive search over the wider twenty-five game family, 325 pairs, is the same routine at larger scale, and returned the same zero.

What the picture cannot show, and what the bracket is not #

The figures here draw brackets as bars on an axis of integers, and the drawing asserts two things it has no right to.

The first is spacing. There is no distance between ↑ and ⇑, only an ordering, and the even spacing on the axis is a convention with nothing behind it. A bracket that is “eight ups wide” is a count of failed comparisons, not a length.

The second is specific to a sum. When a row shows [−4, 4] narrowing to [0], the picture makes the narrowing look like a measurement that got better. It is not: the two brackets being added were each complete and correct statements about their own position, and the sum is a different position about which a sharper statement happens to be true. Nothing was refined. The picture cannot show the mechanism — that two stars cancelled — because the mechanism lives in the games and the bracket has already thrown it away.

Nor can any figure here show what lies between the marks. There are all-small games strictly between ↑ and ⇑, infinitely many, and games not comparable with any multiple of ↑ at all. Every gap in these drawings is densely occupied and every one is drawn empty.

Three further limits belong in the same section, because this rung is a measurement and is easy to read as more.

There is no atomic weight calculus in the code behind these figures. The calculus proper is a recursion on a position’s options with a correction term for the remote star, it produces a single number rather than an interval, and none of it is implemented here. What is computed above is what comparison alone can see, and comparison alone cannot see past a star. Where this essay says “bracket” it means the interval; where it says “atomic weight” it means the quantity the calculus would produce, which the bracket contains and does not determine.

The containment is a theorem and the narrowing is a census. That 0 in the wider column is not a lucky sample — it follows from ≥ surviving addition and would hold over any family whatever. The 56, the 64, the 54 and the 18 are all properties of these fifteen games, and a different family would give different counts while giving the same zero.

Normal play throughout. Comparison is defined by who wins a difference moving second, which is a statement about who moves last, and the whole of the additivity above is built on it. Misère play has no such ordering: the difference of two positions decides nothing there, so there is no bracket to add and no theorem to preserve. The rules of Clobber and Hackenbush are unchanged under the misère convention and every result in this essay is gone.

Who found it, and when #

Atomic weight and its calculus are from Winning Ways — Berlekamp, Conway and Guy, 1982 — where the ups are the atoms and a position’s weight is how many of them it amounts to.

The additivity question is the reason the calculus exists at all. Atomic weights were introduced to decide sums, and a quantity that decides sums has to relate to addition in a stated way. The book’s answer is more precise than the census above: it gives conditions under which atomic weights add exactly, with a correction where they do not, and the remote-star machinery that makes the correction bounded rather than merely usually-small.

What the computation here recovers independently is the shape of that answer. The one-sided bound is forced by the definition of the ordering, so it belongs to whoever wrote the ordering down. The observation that a pinned part suffices for exactness — in all 54 such pairs and only twice otherwise — is the crude form of the book’s theorem, arrived at by counting rather than by proving.

Where the ladder goes next #

This anchor started with the infinitesimals themselves, measured them with the up-bracket, and has now asked whether the measurement survives a disjunctive sum. The answer is that it bounds rather than adds, and the bound is loose in 64 of 120 pairs. The rungs above are the ones the bracket cannot reach.

The atomic weight calculus proper, which replaces the interval with a number by recursing on options rather than comparing against multiples of ↑ — the step this rung’s whole limitation is waiting on.

The theorem on when atomic weights add exactly, of which the pinned-part rule above is the empirical shadow. The interesting content is the correction term where they do not, and its size.

Positions whose atomic weight is not an integer. {∗ | ↓} is the family’s warning shot: an odd-width bracket whose midpoint is −1.5, and nine broken midpoint sums behind it.

And the infinitesimals below the reach of the ups. Tiny and miny are positive and smaller than every multiple of ↑, so the bracket comes back [0, 1] for all of them and distinguishes none. That is worse than it sounds for a rung about sums: the whole census above rests on brackets being informative enough that adding them says something, and on a scale where every member gets the same bracket the addition is vacuous — [0, 1] plus [0, 1] is [0, 2], and it is right, and it is worth nothing. Deciding a sum down there needs a smaller unit, and the tower does not stop at one floor either.

The practical residue of this rung is one sentence, and it is worth carrying into any endgame that has fallen apart into all-small parts. Which part to move in is decided by the total, the total’s bracket is at worst the sum of the parts’ brackets, and if any part is pinned that bound is exact — so a player who can pin one component has already done the arithmetic, and a player who cannot has to add the games.