Which part to move in

The additivity theorem is the reason this subject exists. A position that breaks into independent parts has a value equal to the sum of the parts’ values, so a dozen small regions can be evaluated separately and added rather than searched as one enormous tree.

It is worth being exact about what that buys, because it is less than it first appears. The theorem is about values. It says nothing whatever about moves.

The smallest example #

$\uparrow$ is positive. Left wins it whoever moves first, and it is smaller than every positive number but genuinely greater than zero.

$\ast$ is confused with zero. Whoever moves first wins it, and it is worth nothing in the sense that nobody is ahead.

Add them. $\uparrow + \ast$ is $\uparrow\!\ast$, which is confused with zero — so whoever moves first wins the sum. Left, moving first, has exactly two options, and they can be listed in full.

Move in the up. $\uparrow$ is $\{0 \mid \ast\}$, so Left’s only option there is $0$. The sum becomes $0 + \ast = \ast$. It is Right’s turn, $\ast$ is a first-player win, Right takes it and Left has lost.

Move in the star. $\ast$ is $\{0 \mid 0\}$, so Left’s option there is $0$. The sum becomes $\uparrow + 0 = \uparrow$. It is Right’s turn, $\uparrow$ is positive, Left wins whatever Right does.

One of two moves wins, and it is the one in the component that was worth nothing. A player reasoning that the up is the asset and should be developed would lose. A player reasoning that the star is worth nothing and should be left alone would lose.

Now ask Right the same question. The sum is confused with zero, so Right moving first also wins it, and Right also has exactly two moves to choose between — one in each component. If the lesson were play in the worthless component it would apply to both players, and it does not.

Neither player is following a rule about values. Each is following the only thing that decides a move, which is what the whole position becomes afterwards, and the two players get opposite answers because the two components offer them different things.

What went wrong with the intuition #

The intuition being violated is that a component’s value measures how much a player should care about it. It does not, and the reason is worth stating precisely.

Moving in a component changes it, and the change is what matters, not the level. Left’s move in the up takes it from $\uparrow$ to $0$ — a loss of $\uparrow$. Left’s move in the star takes it from $\ast$ to $0$ — a change of $\ast$, which is not a loss at all because $\ast$ is not positive.

So the correct accounting is by differences, and a component’s value tells nothing about what its options do. A component worth a great deal may offer only moves that destroy that value; a component worth nothing may offer a move that costs nothing.

That impartial case is the familiar one and is worth setting beside the partizan one, because in the impartial world the rule is readable off the values: take the nim-sum and equalise it. The winning move is computed from the parts by a formula.

The partizan world has no such formula, and the reason is structural. The nim-sum works because impartial values live in a group where every element is its own inverse, so “which component to change, and to what” has an arithmetic answer. Partizan values live in a partially ordered abelian group with no such property, and the move has to be found by asking each option what it does to the whole.

Three components #

With two components the listing is short enough to be unconvincing. Here is a sum with three, and it is a sum a real position could produce: an infinitesimal, a settled point, and a fight.

The move in the number loses for the reason numbers avoid numbers gives: it spends a turn on a component with nothing at stake. That much is a theorem and could have been predicted.

The move in the up loses for a different reason and no theorem covers it. The up was the entire margin — the difference between the fight resolving in Left’s favour and against — and giving it away leaves the fight decided the wrong way. There is no rule that identifies the up as load-bearing except computing what happens without it.

The same problem in a game somebody plays #

The examples so far are written in braces, which makes them easy to check and easy to dismiss as constructions. The situation is not a construction.

Take a Hackenbush drawing of four separate sprigs: blue over red, red over blue, a single green edge, and two green edges stacked. Their values are $\tfrac12$, $-\tfrac12$, $\ast$ and $\ast 2$, so the two coloured sprigs cancel exactly and the total is $\ast 3$ — confused with zero, and a win for whoever moves.

Four sprigs, four values, one total. A player with the total knows who wins. A player deciding what to cut has to work out, for each of the five cuts, what the total becomes — and the values of the individual sprigs do not shortcut that, for the same reason they did not in $\uparrow + \ast$.

The green sprigs are the interesting ones, and they are worth naming because they are where the decision sits. A green edge is one either player may cut, so a lone green edge is worth $\ast$ — which is to say worth nothing, in the sense that neither player is ahead in it. Stack a second green edge on top and the sprig is worth $\ast 2$: still worth nothing in the same sense, and a completely different component, because it now offers a cut that leaves $\ast$ behind rather than only a cut that leaves nothing.

That difference is the whole of the winning move. The coloured sprigs cancel and contribute no options worth having; the two sprigs worth “nothing” contribute every option that matters; and only one of the five is the one that balances the picture. Two sprigs that differ by one edge can have values that differ by a nimber, and the nimber can be the entire content of the position — while the blue-over-red sprig, worth half a point and the largest value on the ground, offers no cut worth making.

Why the impartial rule works, exactly #

Impartial values live in a group where every element is its own inverse is the reason the essay gives for the nim-sum being a formula, and it is not quite the reason. Self-inverseness makes the arithmetic tidy; what makes the move readable is a different property, and naming it says precisely what the partizan case is missing.

A Nim heap of $n$ has options worth $\ast 0, \ast 1, \ldots, \ast(n-1)$ — every value below it, with none missing. That is the mex construction seen from the other side, and it holds for every impartial position, not only for heaps.

So the winning move has somewhere to aim. Compute the exclusive or; if it is $\ast k$ with $k \neq 0$, find a component whose value has the top bit of $k$ set, and ask that component for the option that fixes the total — which exists, because a component realises every smaller value.

A partizan component offers nothing of the kind. $\uparrow$ is $\{0 \mid \ast\}$: Left’s only option is $0$, and the values strictly between $0$ and $\uparrow$ — every tiny, for instance — are not on offer at all. A component’s options are an arbitrary antichain, not an interval, so there is nothing to aim at and no target to compute.

That is the missing ingredient, and it is about option sets rather than about the group. Sprague–Grundy hands over a component whose options are dense below it; the partizan theory hands over a component whose options are whatever the position happens to offer.

The formula’s other half is the case where it reports that there is nothing to aim at, and that half is worth seeing because the partizan theory has no counterpart to it either.

That is the sharpest statement of what the impartial rule buys. It does not merely find the move faster than the listing does; it answers the prior question of whether there is one, from the values alone, and the listing here exists to confirm the answer.

Which makes the decision cheap, but not a formula #

That diagnosis corrects something the essay says a little too strongly. The values of the individual sprigs do not shortcut that is true of the components’ values and false of their options’ values, and the difference matters because it decides what a solver has to do.

Given each component’s value and the values of that component’s options, choosing a move is easy. For each option in turn, replace one component’s value by the option’s value, add — addition of values is exact and free — and read the outcome of the total. A move wins when the resulting total is one the opponent cannot win from.

The cost is one addition per option, so linear in the total number of options on the board, not exponential and not a re-search. Four sprigs offering ten cuts between them is ten additions.

So the honest statement is not that the move is expensive. It is that there is no closed form — no expression in the components’ values that names the move — while there is a perfectly cheap procedure, provided the options have already been evaluated.

And they have been. Evaluating a component means building its value from its options’ values, so anybody who knows a component’s value already computed the options’ values on the way. The information the move needs is a by-product of the information the value needed, thrown away by anybody who stores only the total.

That is the practical residue of the whole essay. Store a board’s value and the move is unavailable; store the components with their option lists and the move is ten additions away. The theorem that values add is not the whole of what a decomposition buys, and the part it does not mention is the part a player uses.

What the solver computed, and how #

The figures on this page are listings, not arguments, and every verdict in them is the output of the same recursion.

The construction is direct. Each component is built from its written form; the sum is built by add; the canonical form of each component supplies its option list. For each option in turn, the sum is rebuilt with that component replaced by that option, and the resulting position is asked one question: can the opponent, moving next, win it? A move that leaves the opponent unable to win is marked as winning, and every other move is not.

That question — rightMovesFirstWins of the position after the move — is the definition of a good move and not an approximation to it. There is no search depth, no evaluation function and no cut-off, because the positions are small enough to unroll completely.

The listing is exhaustive rather than filtered. The figures show every option each component has, including the ones that lose, because a figure that showed only the winning move would be asserting the conclusion instead of demonstrating it.

The site’s gate makes the general claim these figures instantiate. It builds sums of a number and a non-number, finds every winning move by the recursion, and requires that at least one of them lies in the non-number component — the number-avoidance theorem, checked rather than quoted. And it separately requires the check to come out false on sums of two numbers, where no component offers a free move, so that a test which passed everything could not masquerade as a test that passes.

Where the model stops #

Exhaustive listing is exactly as far as these positions go. Every figure here has fewer than a dozen options. A real position has hundreds, and listing them is not a method — it is what a method has to replace. Temperature is the replacement, and it is approximate.

A verdict is about optimal play from both sides. “This move wins” means it wins against every reply. Against a fallible opponent, moves that lose to perfect play may be better, and nothing here has anything to say about that.

The decomposition is assumed, not derived. Every figure starts from a position already written as a sum of independent parts. Establishing that a real position decomposes — that no move in one region affects another — is a separate piece of work, and in some games it only becomes true partway through.

Normal play, and the components are loopfree. A component from which play can return has no value in this sense and cannot be added to anything, which is a restriction with its own consequences.

What replaces the listing #

The practical answer is temperature, and it is worth saying exactly how much it delivers.

Compute each component’s temperature. Play in the hottest. That rule is not correct, and it is correct up to a bounded error: a player following it finishes within the largest temperature of the position of what optimal play would have achieved. For a game with many components of widely varying sizes that is a good bound; for a game that comes down to two components of equal temperature it is no bound at all.

The bound is where the infinitesimals come back. When two components have equal temperature, the hottest-first rule cannot separate them and the decision falls to a quantity smaller than any number — which is why $\uparrow$ and $\ast$ are not curiosities but the tie-breakers of a close game.

That is the honest summary of what this subject offers a player. The values reduce an intractable search to arithmetic. The arithmetic identifies who wins. Finding the move needs one more layer, that layer is approximate, and the error term is made of exactly the objects that look too small to matter.

Why the difference cannot be arranged away #

A natural response to all of this is to look for a better invariant — some quantity attached to a component that would determine the move. It is worth explaining why the search fails rather than merely reporting that it has.

Suppose such a quantity existed: a function $\mu$ on positions with the property that the right move in $G_1 + G_2 + \ldots$ is always the move that maximises some combination of the $\mu(G_i)$ and the $\mu$ of the options. Then two components with the same $\mu$ and the same $\mu$ on their options would be interchangeable for the purposes of choosing a move.

They are not. $\uparrow$ and $\ast$ both have a single Left option worth $0$. Whatever $\mu$ assigns to that option, it assigns the same thing to both, so any rule of the shape above treats Left’s two moves in $\uparrow + \ast$ identically — and one of them wins while the other loses.

The escape would be to let $\mu$ depend on the rest of the position as well as the component, and at that point it has stopped being a property of the component and become a re-description of the original problem.

There is a second obstruction and it is worth naming, because it rules out the whole family rather than one candidate. A quantity that ranked every component on a line would be imposing a total order on the components, and the order these objects have is not total: $\ast$ is neither above nor below nor equal to nought, and $\uparrow$ and $\ast$ are confused with each other. The confused pairs are exactly the ones where the choice of component is a real decision, so any ranking has to invent an answer precisely where the honest answer is that there is none.

What survives is temperature, and it survives by being explicitly approximate. It ranks components on a line, it is a property of each component alone, and it comes with a stated error rather than a claim of correctness. That is the most a local quantity can do, and the theorem that says so is a bound rather than an equality.

The generalisation #

There is a general principle here that has nothing to do with games, and it is worth naming because it explains why the subject’s central theorem is so easily over-read.

Additivity of a value under composition is a strong and useful property. Additivity of the argmax — of the decision that produces the value — is a much stronger property, and it almost never holds. A function can decompose beautifully while the choice that optimises it does not decompose at all.

In this subject the gap between the two is unusually visible because both sides can be computed exactly and compared. In most places it is invisible, and a decomposition theorem gets quietly used as though it licensed local decisions.

The one case where the argmax does decompose is the impartial one, and it decomposes because the value group is $\mathbb{Z}_2^{\,\infty}$ under exclusive-or, where changing one component to fix the total is always possible and always unique. That is a fact about the group, and it is the reason Sprague–Grundy is as strong as it is and why nothing like it exists for partizan games.

Who found it, and when #

The additivity theorem is Conway’s, and so is the recognition of its limits. On Numbers and Games is careful throughout to state results about values rather than about play, and the temperature theory that follows exists precisely because values are not enough for a player.

The practical version came from Go. Berlekamp’s endgame work in the 1990s is a sustained attack on exactly this problem — the values of the regions are known, and the question is where to play — and the machinery it produced is considerably heavier than the additivity theorem that motivates it.

The impartial case had been settled forty years earlier by Sprague and Grundy, and the contrast between the two is instructive. The impartial answer is a formula anybody can execute; the partizan answer is a research programme, and the reason for the difference is one algebraic property of the value group.

The ladder from here #

This anchor began with the disjunctive sum and the additivity theorem, which is the reason a position can be broken up at all. This rung says what breaking it up does not buy.

Later rungs: the temperature bound stated and proved, with the error term made explicit. Sums with many components of equal temperature, where the bound is worthless and the infinitesimals decide. The reduced canonical form, which is what happens when a value is stripped of everything that does not affect play against a large background. And the algorithmic question — finding an optimal move in a sum is hard even when every component is trivial, which is a result about sums rather than about any game in them.

The thing to carry is the distinction the essay is built on. Knowing what a position is worth and knowing what to play in it are different pieces of information, both computable, and the theory computes the first far more cheaply than the second.