Where the impartial theory stops

The Sprague–Grundy theorem is the strongest result in the impartial theory and it has one hypothesis: both players must have the same moves from every position.

Drop it and the theorem does not weaken. It fails completely.

What is being claimed, precisely #

For impartial games, every position $P$ has a number $g(P)$ such that $P$ and the Nim heap of size $g(P)$ are equal as games: their difference is a second-player win, so either may replace the other in any sum whatsoever without changing any outcome.

For partizan games, the corresponding claim would be that every position equals some nimber. The figure tests it directly on three positions and finds nothing equal to anything.

The three are chosen to fail in different ways, and the pattern along each row is the content.

Three ways of not being a number #

A position worth ½ — Left may move to 0, Right may move to 1 — is above every nimber. That is a clean failure: ½ is a positive number, every nimber is confused with zero, and a positive number beats anything confused with zero.

Up is above 0 and above ∗2 and ∗3 and the rest, and confused with ∗. So it is not merely unequal to the nimbers; it is not comparable with one of them.

A switch — Left to 1, Right to −1 — is confused with every nimber. Nothing in the row is a comparison at all.

Three positions chosen to fail in three different ways is an argument with an obvious objection in it: they were chosen. The reply is to run the identical comparison on positions nobody selected — the values of ordinary Domineering boards, computed from the rules of the game and only then compared with anything.

What impartial means, and how easily it is lost #

The hypothesis sounds like a mild regularity condition and it is extremely strong.

Impartial: from every position, both players have exactly the same set of moves. Not similar moves, not symmetric moves — the same ones.

Nim qualifies: whoever is to move may take from any heap. Sprouts qualifies. Kayles and the octal games qualify. And that is close to the end of the list of games anybody plays.

Domineering does not, because Left places vertical dominoes and Right horizontal ones. Hackenbush does not, because the edges are coloured and each colour belongs to a player. Go does not, and neither does chess, draughts or anything else with two kinds of piece.

Domineering is the one to keep hold of, because it is as ordinary a game as this subject contains and the hypothesis fails at its very first position rather than somewhere deep in an analysis. Nothing subtle is going wrong: the two players are simply doing different things with the same board.

So the theorem covers a family that is mathematically natural and, as games go, unusual. The subject’s centre of gravity is on the other side of the hypothesis.

Why “confused” is the fatal word, not “unequal” #

If partizan positions were merely unequal to all nimbers but comparable with them, there would be a repair available: locate each position between two nimbers and see how much of the theory survives.

Confusion kills that. Two games that are confused are not ordered relative to each other at all — the difference between them is a first-player win, so whoever moves in it wins, and neither is “bigger”. A structure with confused elements is a partial order, and the nimbers do not sit inside it as a spine along which everything else can be located.

That is the precise sense in which one number per position stops working. It is not that the right number is hard to find. It is that the target — a totally ordered set of values that every position is equal to a member of — does not exist.

The repair worth running rather than dismissing is the obvious one: if the nimbers are the wrong totally ordered family, try a better one. The numbers are the family every reader already has, they are dense where the nimbers are sparse, and they are what a score would be measured in.

Both halves of that matter. A value that is squeezed between numbers without being one is an inconvenience — the theory would need limits, and limits are a thing mathematics knows how to build. A value that is confused with a whole interval is not squeezed anywhere, and no refinement of a totally ordered set reaches it.

What impartiality does give: a position that is its own negative #

There is a structural fact underneath the collapse that makes it feel less arbitrary, and it is worth getting exactly right because the tempting version of it is false.

An impartial position is symmetric between the players, so swapping their options changes nothing: $-G = G$. Adding $G$ to both sides gives $G + G = 0$. Every impartial position is its own negative, and that much is immediate from the definition — no recursion, no mex, no theorem.

The tempting next step is to say that the values with that property are exactly the nimbers, and to conclude that impartiality has pinned the position down before the theorem is invoked at all. It is a tidy argument and it does not survive contact with the third row of the hero figure.

Partizan positions are in general not self-negating, are not forced anywhere, and the set of values they can take is the whole structure. The question is what the exceptions do, and the section below is about one of them.

Negation is the mirror: swap the two players’ options and negate them, recursively. A star comes back where it started, because an impartial position is symmetric between the players. A switch $\{2 \mid 0\}$ goes to $\{0 \mid -2\}$ and $\uparrow$ goes to $\downarrow$, which is what a partizan position ordinarily does under the mirror — and the section below is about the positions that ordinarily do not.

The failure is not gradual #

It is worth being clear that partizan games are not “less impartial” by degrees with a correspondingly degraded theory.

A position where the two players’ moves differ in one place, deep in the tree, is fully partizan: the Grundy value does not approximately work, it does not work. There is no measure of how impartial a game is and no theorem that says nearly-impartial games have nearly-nimber values.

The presence of some nimber-valued positions inside a partizan game is worth noticing precisely because it is the thing that could mislead. A reader who computed a few values of a partizan game and found ∗ and 0 might reasonably conclude the impartial machinery applies. It does not, and the next position computed will show it.

The sharper form of the claim is available by construction rather than by survey, and it settles the word gradual directly. Start with a Nim heap, which is as impartial as a position gets, and take away one of Right’s moves. Then rebuild the heap above it with that damaged position in place of one of its options, so that everything a player can see for the first move, or the first two, or the first three, is still perfectly symmetric and the single missing option sits further and further down.

Nothing degrades along that sequence. The third row’s asymmetry is two moves down a tree whose top two levels are indistinguishable from Nim, and its value is as far from a nimber as the first row’s — confused with three of them, above the rest, equal to none. There is no quantity here that gets smaller as the flaw gets deeper, which is what “not gradual” means and why no approximate version of the theorem exists to be looked for.

What had to be built instead #

The replacement is not a better number. It is a larger object: a value that is itself a game, written $\{L \mid R\}$ from the values of the options, reduced to a canonical form, and compared with others by playing the difference.

That structure is a group under the disjunctive sum with a partial order on top, and the nimbers sit inside it as one small family among many. Numbers are another family. The infinitesimals are a third. And most values belong to none of the named families and are written out as brace expressions.

The reduction that makes such a value well defined is canonical form: dominated options removed, reversible options replaced, and the result unique whatever order the steps are taken in. That machinery is most of what the partizan theory costs, and the impartial theory needs none of it, because a nimber is already canonical.

What survives the crossing #

The collapse is total for the value, and several other things cross over intact, which is worth recording because it explains why the partizan theory was buildable at all.

The disjunctive sum survives. Games still add, the sum of partizan games is a partizan game, and the operation is still associative and commutative with 0 as identity.

Negation survives, and does more work than before: $-G$ is $G$ with the two players’ options swapped, and $G + (-G) = 0$ for every $G$. That is what makes the values a group and makes comparison a subtraction.

Termination survives, so the recursion still bottoms out and values are still finite objects.

So a sum of three partizan components with values of three kinds — a number, a nimber, an infinitesimal — is combined by exactly the operation the impartial theory uses. The operation is unchanged. What changed is that the things being combined are no longer single integers.

What does not survive is the compression. The impartial theory’s achievement is not that games add; it is that a position collapses to one small number. Partizan games add just as well and collapse to a tree, and the whole difference in cost between the two theories is there.

The self-negation argument, and why it is not the proof #

The shortcut is worth following to its end, because the place it breaks is the most informative thing on this page and it breaks on a position already drawn above.

The first two steps hold. An impartial position $G$ has the same options for both players, so swapping them changes nothing and $-G = G$. Adding $G$ to both sides gives $G + G = 0$: every impartial position is its own negative under the sum.

The third step is the one to refuse. Which values satisfy $x + x = 0$? Not only the nimbers — and the counterexample is the switch in the bottom row of the hero figure.

Take $\pm 1$, the position where Left may move to $1$ and Right to $-1$. Negating swaps the options and negates them, which turns $\{1 \mid -1\}$ into $\{1 \mid -1\}$: the switch is its own negative, exactly as an impartial position is. So $\pm 1 + \pm 1 = 0$, and the second player really does win it — Left takes one switch to $1$, Right takes the other to $-1$, the total is zero and Left has nothing left.

And $\pm 1$ is not a nimber. It is confused with every nimber, which is what its row in the hero figure says: no cell in it reads “=”, and no cell reads “≥” or “≤” either.

So self-negation is necessary and not sufficient. It is a property the nimbers have and share, not a property that picks them out; the same holds for $\pm 2$, and for $\pm 1$ added to a star, and for an unbounded family beyond them. Impartiality does not pin a position to the star family in one step, and any account saying it does has proved the theorem by assuming it.

What does the real work is that impartiality is hereditary. A follower of an impartial position is impartial, and so is a follower of that, all the way to the end of the game. So the induction has something to stand on: assume every option is a nimber, note that the option set is the same for both players, and the mex of their indices is forced. Self-negation is true at every step of that induction and decides nothing at any of them.

That is why the theorem is a theorem. The symmetry is visible in one line and gives a large, badly behaved class; the nimber comes out of a recursion over the whole tree, and the switch is the reminder that the line and the recursion are not the same argument.

The check that refuses the shortcut #

A false step of that shape is not caught by looking at pictures, because the picture it draws is correct: the star really is its own mirror image, and every cell the mirror figure shows is right. What was wrong was a sentence next to it, and a sentence is exactly what nothing on this site reads.

So the shortcut is now something the machinery refuses rather than something a reader has to notice. Three claims are asserted against the same evaluator every other value on this site comes from.

That $\pm 1$ is its own negative. Negate it and compare, and the comparison comes back equal — so the premise of the shortcut is genuinely satisfied by a position that is not a nimber.

That $\pm 1 + \pm 1$ is zero. Built as a sum and compared against the empty game, it is, so the conclusion drawn from that premise is genuinely available and genuinely useless.

That $\pm 1$ equals no nimber in the drawn range, which is the hero figure’s third row re-asserted as a claim rather than as a picture.

Together those three are the refusal: a value satisfying $x + x = 0$ that is not in the star family, produced by the same recursion that produces every other number on this page. The same three hold for $\pm 2$ and for $\pm 1$ added to a star, so the counterexample is not a single awkward game but a family, and the check is fed all three.

Which makes it drawable, and drawing it is worth more than asserting it, because the whole force of the shortcut is that its premise looks like a description of the nimbers. Put the three switches in the same table as two stars and the premise is visibly common property.

What the check cannot do is notice the next sentence of its kind. It can only refuse this one, which is the ordinary limit of turning a correction into a test.

Where the model stops #

The comparison is exhaustive over a range. The hero figure checks against nimbers up to ∗8, and the claim that no nimber equals these positions is a claim about that range. The general statement — no nimber at all — follows from the self-negation argument above rather than from the table.

And the collapse is one-directional. Every impartial game is a partizan game, so the larger theory covers everything; there is no loss. What is lost is the cheapness: an impartial position has a small integer where a partizan one has a tree.

What the picture cannot show #

The table of relations is a grid of four symbols and it makes the four look equally weighted. They are not.

Three of them — above, below, equal — say the two positions are on a common scale. The fourth says they are not. Drawing all four as cells of the same size in the same grid gives no sense that one of them is a different kind of answer from the other three, and the essay has to carry that.

Who found it, and when #

The gap sat open from 1939 to about 1970. That is a long time for a subject to have a complete theory of half of itself and nothing for the other half, and the reason is the one the notation essay makes: there was no way to write a partizan value, so there was no object to have a theory of.

Conway’s construction supplies the object, and everything else follows from having something to write down.

Why the gap took thirty years, mechanically #

The notation essay gives one reason — there was nothing to write down — and there is a second, which is about what was being looked for.

The natural extension to try is: keep one number per position, but let the number be from a richer set. Rationals, perhaps, or pairs of numbers, or a number with a sign convention for which player it favours.

Every version of that fails for the same reason, and it is the reason the hero figure draws: the values have to be partially ordered, because confusion is real and any totally ordered set of values cannot represent it. A pair of numbers is totally orderable lexicographically; so is any tuple; so is anything anybody would reach for first. The table of comparisons against the numbers, above, is that search run to its end on the richest ordered family anybody would try first, and the rows of ‖ in it are what every later attempt would have found.

The obstruction is in the comparison itself. A relation between two positions is decided by playing their difference and reading off who wins, and the difference has four outcome classes rather than three; the fourth is a first-player win, which is confusion, and no arrangement of numbers produces that answer.

So the search had to be for a structure that is not a set of numbers at all, and there was no reason to look for one until it was clear nothing simpler could work. Establishing that takes as long as it takes.

The one place a number does come back #

There is a partial consolation, and it is the closest thing the partizan theory has to a Grundy value.

For positions that are all-small — where a player has a move exactly when the opponent does — there is a single number, the atomic weight, which measures roughly how many copies of ↑ the position is worth. It behaves a great deal like a Grundy value: it adds, it decides outcomes in most cases, and it collapses a tree to an integer.

It is not complete. Atomic weight decides the outcome of a sum only when the weight is large enough in absolute value, and near zero the theory needs the full value again. So it is a compression that works most of the time, which is a weaker claim than Sprague–Grundy makes and is the strongest available on the partizan side.

What it is measuring against is the infinitesimals ordered among themselves, which is a scale rather than a line: the tinies sit above nought and below every multiple of ↑, so a number of ups is a coarse reading of a family it cannot separate. A single number summarising a position does reappear on the partizan side, then, and unlike a Grundy value it arrives with conditions on when it may be trusted.

What the impartial theory keeps that the partizan one wants #

Running the comparison the other way is worth a paragraph, because the impartial theory is not simply a special case with less in it.

Its values are totally ordered by nothing at all, which sounds like a loss and is a simplification: every pair of distinct nimbers is confused, so there is no ordering to maintain, no comparison to compute, and no partial order to reason about. A Grundy value is an index and behaves like one.

Its canonical form is free. A nimber is canonical; there is no reduction step, no dominated options to remove, no reversibility to detect. The reduction machinery that the partizan theory needs simply has no work to do.

And its addition is a machine instruction. Exclusive-or, on integers, at whatever width the values need.

All three of those are one cell in a table this page has now drawn six times. Run the identical comparison on impartial positions and every row has an equality in it, in the column the mex rule names, with confusion in every other column of the row — which is the ordering that is not there, the canonical form that needed no reduction, and the number the exclusive-or operates on, all at once.

That one cell per row is the whole of what Sprague and Grundy give, and it is the cell the partizan tables above have none of. It is also why the impartial theory feels like arithmetic and the partizan theory feels like algebra: with an equality in hand, a position is a number and the rest of the row can be forgotten; without one, the row is the position.

So the impartial theory is not a fragment. It is a case where the general theory’s objects collapse to something a computer does in one cycle, and the reason to state the collapse carefully is that anybody meeting the subject through Nim will assume the general case is a slightly harder version of it. It is a different order of thing.

Where the ladder goes next #

This anchor runs from the theorem, through why the mex was forced, to here — the boundary. Past it the ladder is not about impartial games any more: it is about what a value has to be when a number will not do, which is what the notation was for and what the rest of this site is about.