Comparing two positions means playing a third

Two positions, drawn side by side. Which one would Left rather have?

There is no procedure that looks at them and answers. The definition of $G \ge H$ is not about the shapes of $G$ and $H$ at all: it says that Left does at least as well with $G$ as with $H$ in every sum whatever — an infinite family of comparisons — and the way that gets decided is to build a third game and solve it.

The move that makes it finite #

The definition quantifies over every sum, and quantifying over an infinite family is not something a computation does. The manoeuvre that rescues it is one line and it is the reason negation matters as much as it does:

$$G \ge H \quad\text{exactly when}\quad G - H \ge 0,$$

and $G - H \ge 0$ means Right, moving first in $G - H$, loses. So an infinite quantification becomes a single question about a single game — who wins $G - H$ — and that is decidable by the ordinary recursion.

The reason this works is that $-H$ is a genuine game whose play mirrors $H$’s with the players exchanged, so $H + (-H)$ is worth exactly zero for every $H$ there is. Subtracting is adding the mirror, and the mirror always exists.

That the mirror always exists is the fact doing the work, and it is not a small one. It makes the values a group rather than merely an ordered set, and a group is what turns compare these two into examine this one. Take the negative away — as misère play does — and the manoeuvre is unavailable, which is most of why comparison there is so much more expensive.

Four answers, not two #

Numbers compare in three ways: less, equal, greater. Games compare in four.

The fourth is fuzzy, written $G \parallel H$: neither is at least the other, and the difference $G - H$ is a first-player win. Star against zero is the standard example — $\ast$ is not better than nothing, not worse, and not the same.

The four relations line up exactly with the four outcome classes of the difference game, which is not a coincidence but the same fact stated twice. Games are only partially ordered, and the fuzzy relation is what partial means here.

What one comparison costs #

The cost of deciding a relation is the cost of solving the difference, and the difference is a game with its own position graph.

For the small cases in the figures here that is a few dozen positions each — the numbers are printed beside every row, computed by walking the difference’s own graph rather than estimated. For two Domineering boards, the difference is a game on both boards at once and its graph is the product of the two.

That last point is the one worth carrying. Comparing two positions is not cheaper than evaluating them; it is a search over a combined game, which is generally larger than either. The saving in practice comes from the same place it always does: once both sides have been reduced to canonical form, the comparison is over small objects rather than over boards.

One comparison, followed through #

Take $G = \{2 \mid 0\}$ and $H = \{1 \mid 0\}$ — two switches, one offering more to Left. The claim to settle is $G \ge H$.

Build $-H$ first: exchange the players’ options throughout, giving $\{0 \mid -1\}$. Now the difference is $\{2 \mid 0\} + \{0 \mid -1\}$, and the question is whether Right, moving first, can win it.

Right’s options are to move in either component: to $0 + \{0 \mid -1\}$, or to $\{2 \mid 0\} + (-1)$. In the first, Left answers by moving in the second component to $0 + 0 = 0$, leaving Right to move in a position with no moves — Right loses. In the second, Left moves to $2 - 1 = 1$, a positive number with no moves for Right, and Right loses again.

So Right moving first loses, $G - H \ge 0$, and $G \ge H$. The solver reports the same thing after walking the difference’s graph, and the count of positions it walked is printed beside the row in the first figure.

Two things are worth noticing from the worked case. The argument never compared the two positions to each other — it played a third game, and both original positions appeared inside it as components. And the answer came out as an outcome, which is then read back as a relation: the vocabulary of comparison is a translation of the vocabulary of who wins.

Why every reduction is built on this #

Comparison is not an occasional operation in this subject. It is the primitive that everything else calls.

Dominated options. An option is dominated when another option is at least as good, and removing it is the first half of the reduction to canonical form. Deciding at least as good is one comparison, and a position with $k$ Left options needs up to $k^2$ of them.

Reversible options. The test asks whether a reply to an option is at least as good as the original position — another comparison, and one made against the position currently being reduced.

Equality. Two positions are equal when each is at least the other, which is two comparisons, or one difference game whose outcome is a second-player win.

Simplification of sums. Every claim that a component can be replaced by a simpler one worth the same is a comparison, and the whole economics of computing with values rests on making those replacements.

The searches themselves are worth putting on the page, because the reduction above is usually shown as a result rather than as the work it took.

So the reduction that makes values small is itself built entirely out of searches. That is worth knowing when reading a claim that canonical forms make things cheap: they do, downstream, and they are not free to obtain.

What it costs to reduce one position #

Putting numbers on the previous section makes the situation concrete, and the numbers are not reassuring.

A position with $k$ Left options and $k$ Right options needs, for the dominance test alone, every ordered pair on each side: about $2k^2$ comparisons. Each comparison is a difference game whose graph is roughly the product of two option graphs. And removing an option changes the position, so the tests are re-run on what remains.

Reversibility is worse in one respect: the test compares a grandchild against the position currently being reduced, and the position is a moving target as the reduction proceeds.

Which raises the question the site’s own gate had to settle: does the answer depend on the order the reductions are taken in? It does not — the reduction is confluent, and every order reaches the same form — but the number of steps does, and one rung deeper the same position can reach its canonical form in three steps or in five.

So the practical rule is to reduce early and often. A component reduced before being added to anything keeps every later comparison small, and a component carried around unreduced makes every difference game it appears in bigger than it needed to be. That is a piece of engineering advice, and it falls directly out of comparison being a search.

An operation that is not an inspection #

There is a habit of thought worth breaking here, and it is the one that makes this rung necessary.

Numbers can be compared by looking at them. So can strings, dates and most things a person compares. It is natural to assume that two positions, written out as trees of options, can be compared by comparing the trees — that some structural test on the two objects settles the relation.

No such test is known, and there is a reason to expect none. Two positions with completely different shapes can be equal — 256 forms carry only 22 values at day two — and two positions with almost identical shapes can be incomparable. The relation is about behaviour in sums, and behaviour is not visible in structure.

The canonical form is the closest thing to a structural test available, and its status is worth stating exactly: it does not make comparison structural, it precomputes it. Two games in canonical form are equal exactly when they are the same object — but reaching canonical form required all the comparisons, so the structural test at the end is the cached result of the searches at the beginning.

The fuzzy relation, and why it is not a gap in knowledge #

It is worth insisting on the fourth relation, because the natural reading of neither is at least the other is that something has not been determined — and that reading is wrong.

$G \parallel H$ is a complete, definite answer. It says the difference is a first-player win, which is a fact about the game as sharp as any other. What it denies is not knowledge but comparability: there is no fact of the matter about which of the two Left would rather have, because the answer depends on what else is on the board.

That is exactly what a partial order is, and it is forced by the subject rather than chosen. Star against zero: in a sum where everything else is settled, $\ast$ is worth having when it is the mover’s turn and a liability when it is not. No single relation to zero could capture that, so the theory has a symbol for it.

The four-way outcome is also why the outcome of a sum is not determined by the outcomes of its parts. Two fuzzy components can add to a second-player win, or to a first-player win, depending on what they are — and if comparison had only three answers there would be no vocabulary to describe why.

Where the search stops working #

Two limits, and both are places this site’s machinery has to be careful.

The universe has to be all games. Under normal play the comparison is universal: $G \ge H$ means at least as good in every sum with every game there is. Under misère play that fails, and comparison has to be relativised to a restricted universe, which makes it contextual and much more expensive.

The difference has to end. The recursion deciding who wins $G - H$ needs play to terminate, and for loopy games it does not. Comparison in that setting needs the retrograde method rather than the recursion, and the answers are correspondingly coarser.

Numbers are the exception, and a useful one. When both sides happen to be numbers, the relation is the ordinary one on the dyadic rationals and can be read off — $\frac{1}{2} > \frac{1}{4}$ needs no search at all. That is worth knowing because a great many components in real positions are numbers by the time the endgame arrives, so a solver that tests for numberhood first skips most of its comparisons. It is also the reason the general case is so easy to underestimate: the familiar cases are exactly the ones where the shortcut exists.

There is also a practical caution the site’s own code observes. A comparison run on unreduced positions is a search over a needlessly large graph, and the fix is to canonicalise first — which costs comparisons of its own, on smaller objects. The ordering matters, and getting it wrong turns a fast operation into an intractable one on positions that are not large.

The clearest demonstration of that is an equality between objects with nothing structurally in common. A Hackenbush stalk of a blue edge with a red one above it and the number $\tfrac12$ are the same value, and no inspection of the two establishes it — one is a drawing and the other is a fraction. Their difference is built, played, and comes back a second-player win, and that is the whole proof. Equality means interchangeable in every sum, so the drawing may be substituted for the fraction anywhere, and nothing about the substitution is visible in either object.

Comparison at the top of the complexity field #

Everything the complexity essays here measure applies to this operation, and it is worth collecting the consequences in one place because comparison is where they compound.

Memoisation applies. A difference game is a game, so routes collapse into positions exactly as they do anywhere else, and the same table serves every comparison sharing a component.

Decomposition applies. $G - H$ is already a sum of two components, and its graph is the product of theirs — so a solver that keeps the two apart, evaluates each, and compares the values is doing the cheap thing rather than the obvious one.

The result is a certificate of a particular kind. These two positions are equal is exactly the claim a strategy would have to establish for the difference game, and there is no shorter proof of an equality than a way of winning the difference as second player.

Which puts comparison in an odd position in the theory: it is the most-used operation, it is a search every time, and it is the operation whose results make everything else cheap. The subject spends its computation here and collects the return everywhere else.

Who set it up this way #

Defining order by play is Conway’s, in On Numbers and Games, and it is the decision the whole theory turns on. The alternative — defining an order structurally, on the trees — would have produced a relation that did not respect addition, and a value system that did not respect addition would have been worthless for the thing values are for.

By making the order behavioural, the theory buys the property that everything downstream needs: if $G \ge H$ then $G + X \ge H + X$ for every $X$, automatically, because the definition already quantified over every $X$. The cost is that deciding the relation is a search, and this rung is the accounting for that cost.

The choice also explains a feature of the notation that looks like fussiness until this point. Writing $G = H$ for two positions that are visibly different objects is not sloppiness: equality here means interchangeable in every sum, which is the only sense in which a value is a value. Two positions with the same value are the same game as far as anything the theory says about them is concerned, and the difference in their drawings is a fact about how they were written down rather than about what they are.

It is a fair summary of the subject’s whole trade. Every convenience in it — values that add, forms that reduce, components that can be replaced by simpler ones — rests on a relation defined by play. The definitions are chosen to make the algebra work, and the computations are what pay for them.

What the search costs, against what it is asked #

There is one arithmetic worth doing explicitly, because it is the reason a solver’s cost profile looks the way it does.

A comparison is a search over $G - H$, whose position graph is the product of the two components’ graphs. So comparing two positions is not as expensive as evaluating one of them; it is as expensive as evaluating something the size of both multiplied together, before decomposition is applied. Applying decomposition brings it back to the sum, which is the whole reason a solver keeps the difference as a sum rather than building the combined tree — and it is why the advice above about canonicalising first is not a micro-optimisation but the difference between a product of two small graphs and a product of two large ones.

The number of comparisons is the other half. Reducing an option list of $w$ options to its maximal elements needs up to $w(w-1)$ comparisons, and each option is itself a game whose own reduction needed comparisons. So the count multiplies down the tree while the cost of each one multiplies across the sum, and both are happening at once.

That is why canonical form is worth its price and only just. It pays for every comparison once, in advance, and hands back an equality test that is a tree walk. A solver that skipped it and compared by playing every time would repeat the same difference games thousands of times over — and a solver that canonicalises without memoising pays for them thousands of times inside the canonicalisation instead.

Where the ladder goes next #

The comparison anchor has two rungs to here: what the relation means, and that deciding it is a search.

The rung above is the relation the search returns that a reader does not expect. Confused is not the same as unknown takes the fourth answer seriously: it is a fact about the pair rather than a limit of the method, it has its own symbol, and it is what makes a game worth playing at all — a position is a first-player win exactly when it is confused with nought.

How rare it is to be bigger then counts how often the search returns each answer, and the proportions are not the ones a reader carries in from the number line. On day two, 179 of 231 pairs are comparable and 13 of the 22 values compare with nought. One day out those shares fall to 60 per cent and 29, and the largest set of mutually incomparable values rises from four to at least twenty-three.

So the thing this page treats as the exceptional answer is the ordinary one, and it becomes more ordinary the deeper the construction goes. Comparison is the exception; confusion is what values normally do to one another — which makes the search on this page not merely expensive but expensive for an answer that usually declines to order anything.