Comparing positions

Asking whether one position is better than another sounds like a matter of judgement. It is not. There is a definition, it is short, and it turns the question into a computation:

$$G \ge H \iff \text{Left wins } G - H \text{ moving second.}$$

Everything else — equality, the ordering of values, dominated options, the whole apparatus — is built on that one line.

Why subtraction #

The definition looks indirect. Why not compare $G$ and $H$ directly, whatever that would mean?

Because the thing being asked is a statement about substitution. $G \ge H$ should mean that anywhere $H$ appears, replacing it by $G$ is never worse for Left. That is a statement about all possible contexts, and contexts are sums.

The difference $G - H$ is the smallest test that captures it. If Left can win $G - H$ moving second, then in any context $X$, Left playing $G + X$ can mirror the strategy from $H + X$ and use the surplus from $G - H$ to cover the gap. The single test implies the universal claim, which is the theorem that makes the definition worth having.

And it must be moving second. Requiring Left to win moving first would be a weaker and useless condition, since first-move advantage is exactly what the theory is trying to factor out. Winning moving second is winning without the tempo, which is what “at least as good” has to mean if it is to survive being added to something.

The four relations #

Applying the definition both ways gives four possible results, matching the four outcome classes of the difference.

$G > H$ — Left wins $G - H$ whoever moves first.

$G < H$ — Right wins it whoever moves first.

$G = H$ — the second player wins it, whoever that is.

$G \parallel H$ — the first player wins it, whoever that is. The two are confused.

The fourth is the one with no counterpart in arithmetic, and it is not an edge case. Confusion is common, it is what makes the order partial, and it carries real information: two confused positions are close enough that whoever gets to move decides between them.

Confusion, operationally #

The word suggests an absence of information, which is wrong. Confusion is a positive statement.

$G \parallel H$ means: from the difference, whoever moves first wins. Translated back, it means neither position is safely substitutable for the other — replacing $H$ by $G$ helps Left in some contexts and hurts in others, and which one depends on the tempo.

The standard example is $\ast$ and $0$. Neither is better; whoever moves first in $\ast - 0 = \ast$ wins. In a context where Left is desperate for a move, $\ast$ is better than $0$; in a context where Left would rather pass, it is worse.

That is genuinely what happens in games. A position that gives both players a move is not straightforwardly better or worse than one that gives neither — it depends on who has moves to spare, and the theory records the dependence as confusion rather than pretending it away.

A comparison, worked #

The definition is easiest to trust after watching it decide something non-obvious.

Compare $\uparrow$ with $\ast$. Which is worth more?

Build the difference. $-\ast = \ast$, since a nimber is its own negative, so the difference is $\uparrow + \ast$.

Left moves first. Left’s options are to move in $\uparrow$, reaching $0 + \ast = \ast$, or to move in $\ast$, reaching $\uparrow + 0 = \uparrow$. The second is a Left win — $\uparrow > 0$ — so Left moving first wins.

Right moves first. Right’s options are to move in $\uparrow$, reaching $\ast + \ast = 0$, or to move in $\ast$, reaching $\uparrow$. The first is a Right win, since $0$ is a second-player win and Left is now to move. So Right moving first wins.

Both first players win, so the difference is class N, so $\uparrow \parallel \ast$. Neither is worth more; they are confused.

Now compare $\uparrow + \uparrow$ with $\ast$. The difference is $\uparrow + \uparrow + \ast$.

Right moves first. Right’s best is to move in a $\uparrow$, reaching $\ast + \uparrow + \ast = \uparrow$, which is a Left win. Or to move in the $\ast$, reaching $\uparrow + \uparrow$, also a Left win. Every Right first move loses.

So Left wins moving second, and $\uparrow + \uparrow > \ast$.

Two ups beat a star and one does not. That is not a fact anybody would guess, it is not visible in the notation, and it falls directly out of four short recursions.

Why confusion is not indifference #

The word invites a misreading worth heading off: that confused positions are somehow equivalent, or that the theory has declined to choose between them.

Confused positions are as far from equal as the theory can express. $G = H$ means the difference is a second-player win — neither player can extract anything from it. $G \parallel H$ means the difference is a first-player win, so both players can extract something from it, and the one who moves does.

Operationally: if $G$ and $H$ are equal, a player offered the swap should be indifferent, and can accept or decline without consequence. If they are confused, the swap is worth exactly one tempo — accepting it when it is one player’s turn is a gain, and the same swap on the other turn is a loss.

So confusion is a statement that the difference between two positions is precisely the value of having the move. Nothing indifferent about it.

Comparison with zero #

Setting $H = 0$ recovers the outcome classes exactly, since $G - 0 = G$:

$G > 0$ is class L, $G < 0$ is class R, $G = 0$ is class P, and $G \parallel 0$ is class N.

So the four outcomes are not a separate concept from the ordering; they are the ordering, evaluated against zero. That collapse is one of the tidier facts in the elementary theory, and it means an implementation only needs one routine: decide who wins a position, then compare by deciding who wins a difference.

The algorithm #

The definition is directly executable.

To decide whether Left wins $G$ moving second: check that for every Right option $G^R$, Left wins $G^R$ moving first. To decide whether Left wins $G$ moving first: check that for some Left option $G^L$, Left wins $G^L$ moving second.

Two mutually recursive functions, terminating because every option is strictly smaller. Comparison is then: build $G - H$, ask the two questions, read off the relation.

That is what lib/cgt.js does. leftMovesFirstWins and rightMovesFirstWins are the two recursions, outcome combines them, and compare(g, h) builds the difference and classifies it.

The cost is the problem. The recursion visits every position reachable in the difference, which for a sum of two moderately sized games is the product of their state spaces. Comparison is the expensive primitive of the whole subject, and since canonicalisation calls it repeatedly, it is the bottleneck in every value computation on this site.

What the solver computed #

Two implementation facts, both learned by getting it wrong.

Memoisation is mandatory, not an optimisation. The reductions in canonical compare each option against each sibling and against the whole position, and the same comparisons recur constantly. Without a cache keyed on the pair of game identities, canonicalising a position with six options does not finish.

The cache key must be an identity, not a structure. The first implementation generated a structural key by recursing over a game’s options and concatenating their keys. For $\ast 3 + \ast 5$ that key grew to megabytes, and building the key cost more than the comparison it was meant to avoid. Games are now interned on construction — each distinct game gets an integer, keyed on the sorted integers of its options — so a key is two small numbers and structurally identical games are the same object.

With that in place, comparison is fast enough to run on every figure at every build. assertValue and assertOutcome both call it, and both throw rather than render a wrong label.

The relations quoted in these figures were computed, not recalled: $\uparrow > 0$ from the difference $\uparrow$; $\uparrow \parallel \ast$ from the difference $\uparrow + \ast$, which is a first-player win; $\uparrow + \uparrow > \ast$ from the difference $\uparrow + \uparrow + \ast$, which Left wins moving second. Each is one call.

Comparison is not a value #

A distinction worth keeping sharp.

Comparison answers a yes-or-no question about a pair. A value is an object attached to a single position that determines every comparison it could take part in.

The two are related — canonical form is the value, and it is computed using comparison — but they are not the same, and the direction of dependence matters. Comparison is primitive; values are derived. A theory could in principle stop at comparison and never build values, and it would be able to answer every specific question and would compose badly.

What values buy is reuse. Comparing two positions repeatedly is expensive; reducing each once to a canonical form and then comparing forms is cheap. The value is a comparison result cached against every possible opponent at once.

The order is not total, and cannot be made so #

A recurring hope is that some refinement would restore a total order — a tie-break, a secondary criterion, a numerical score.

It cannot be done, and the obstruction is not technical. The order has to be compatible with addition, because that is what makes it useful. A total order compatible with addition would place $\ast$ definitively above or below $0$. Suppose $\ast > 0$. Then $\ast + \ast > 0$. But $\ast + \ast = 0$, so $0 > 0$. Contradiction, and the same for $\ast < 0$.

So confusion is forced by additivity. Any ordering that is total is incompatible with the sum, and any ordering compatible with the sum has confused pairs. The partial order is not a stage the theory has failed to get past; it is the only thing that could have been true.

Transitivity, and what survives #

The order is well behaved where it can be.

$\ge$ is transitive, reflexive and antisymmetric with respect to equality. It is compatible with addition: $G \ge H$ implies $G + K \ge H + K$. It reverses under negation: $G \ge H$ implies $-G \le -H$.

What is not transitive is confusion. $G \parallel H$ and $H \parallel K$ say nothing about $G$ and $K$ — $\ast$ is confused with $0$ and with $\uparrow$, while $0 < \uparrow$. Confusion is a symmetric relation and nothing more, and treating it as an equivalence is a common early error.

Nor is the order a lattice in general. Two positions need not have a least upper bound, so there is no operation of “the best of both”.

The cost, and why it shapes the site #

Comparison is the primitive, and it is the reason this site draws small positions.

Deciding a comparison means playing out a difference, and a difference is a sum whose state space is the product of its parts’. Two positions of a hundred states each give a difference of ten thousand, before any branching. Memoisation caps the work at the number of distinct reachable positions, which is still a product.

Then canonicalisation calls comparison once per pair of sibling options, per pass, per level. The costs compound, and the compounding is why exact evaluation stops at a few dozen moves of depth rather than a few hundred.

Every figure here stays inside that ceiling deliberately. Where a claim depends on a position being small enough to evaluate, the essay says so, and nothing on this site quotes a value the code did not actually produce. That policy is cheap to state and it is the reason the small positions keep recurring — they are not chosen for simplicity of exposition, they are the positions an exact answer exists for.

Who found it, and when #

The definition by difference is Conway’s, from On Numbers and Games, 1976, and it is the first substantial definition in the book. Its placement is deliberate: the ordering comes before the numbers, because the numbers are defined by their position in the ordering.

The recognition that the order must be partial, and that confusion is a relation rather than a failure, was the conceptual step. Earlier treatments of specific games had noticed that some positions were hard to rank; the theory’s move was to make the difficulty a definition and prove things about it.

The notation $\parallel$, and the reading “fuzzy” as an alternative to “confused”, are from Winning Ways, 1982. “Fuzzy” has stuck in the impartial literature and “confused” in the partizan, which is a small unnecessary confusion of its own.

What the definition assumes #

One hypothesis is buried in the definition and worth surfacing.

“Left wins $G - H$ moving second” presumes the difference is a game that ends. If it does not, there is no winner and the relation is undefined — which is why loopy games need a different comparison entirely, built on fixed points rather than on play.

It also presumes the negation $-H$ is available, which it always is for short games and which is a substantive construction: swap the players at every level, recursively. For an impartial game that swap is the identity, so every impartial position is its own negative and $G + G = 0$ — the fact that makes two equal Nim heaps a second-player win.

Where the model stops #

Normal play, throughout. Under misère play the substitution theorem fails — winning the difference moving second no longer implies substitutability — and comparison stops being useful.

The comparison is exact and expensive. Every relation quoted on this site was computed on a position small enough to compute it. Large positions are beyond exact comparison, and no approximate version of the definition is available.

A comparison is not a move. Knowing $G > H$ does not say how to play either.

Confusion carries no magnitude. Two positions are confused or not; there is no measure of how confused. Approximate answers to that question are what temperature and atomic weight provide, and both are separate constructions rather than refinements of the order.

The ladder from here #

Next rungs: the substitution theorem proved in full; the incompatibility of totality with additivity, generalised; confusion intervals, which do quantify confusion for hot positions; and the algorithmic cost of comparison, which is where this meets complexity.

Then the applications: dominated and reversible options are comparison used twice, and the failure of outcome classes is what comparison exists to repair.