An outcome with no value behind it

Three positions in a ring, each one a move from the next. Nobody is ever stuck, nobody ever wins, and the game goes round for ever.

The ordinary theory has nothing to say about that position. Not because the answer is hard to compute — the analysis takes a few rounds — but because the answer is not a value, and the machinery on the rest of this site produces values.

Four outcomes, and the fourth is new #

Under normal play with the ending condition, every position falls into one of four classes: the previous player wins, the next player wins, Left wins whoever moves, or Right wins whoever moves. Those four are what an outcome is, and each of them says who wins.

Loops add a fifth possibility that is not in the list: neither player can force a win. Both can avoid losing, and the game continues indefinitely.

That is a genuine outcome of the game, in the sense that it is what happens, and it is not any of the four. Nor is it a value: there is no game object $D$ such that “worth $D$” means “drawn”. The whole value apparatus is built by recursion on options, and the recursion needs the options to bottom out.

What replaces the recursion #

Since the recursion cannot start, the analysis proceeds from the other end. Retrograde analysis begins at the positions where somebody has already lost and works outward in rounds.

The two rules are asymmetric, and the asymmetry is where the draws come from.

• A position is a win for the mover as soon as one of its moves leads to a position the opponent loses from.
• A position is a loss for the mover only when every one of its moves is known to lead to a position the opponent wins from.

So a win can be settled by a single piece of evidence, and a loss requires the whole option list to be settled first. Positions keep getting labelled while either rule fires, and when nothing more can be deduced the process stops.

The draws are the residue #

Whatever is still unlabelled when the rounds stop is drawn.

That is worth stating as a definition rather than as an observation, because it is how the analysis actually works: a draw is not detected, it is what is left over. No rule fires on it, no round settles it, and the fixed point of the labelling process has holes in it exactly where neither player can force anything.

It also explains why the label is stable. A position is unlabelled because every escape from it leads to a position that is also unlabelled or that the opponent would win — a mutual support among the drawn positions that no single move can break. The drawn set is closed under exactly the property that made it undecidable by the rounds.

What a value would have to do, and cannot #

Suppose someone proposed a value $D$ meaning drawn, to be slotted into the existing arithmetic. Two requirements immediately conflict.

Values compose. The point of a value is that the sum’s value is the sum of the parts’. So $D$ plus a positive number ought to be computable — and the answer depends on details $D$ has thrown away. A drawn position where Left can force the loop and Right cannot behaves quite differently in a sum from one where both can.

Values are compared by play. $G \ge H$ is decided by who wins $G - H$, and if $G - H$ is drawn then neither $\ge$ nor $\le$ nor fuzzy applies. The four-way comparison becomes five-way, and the fifth relation does not fit into an ordered abelian group.

The loopy theory’s actual answer is not a value but a richer set of objects — on, off, dud and their relatives — which record how a position loops rather than merely that it does. Those compose better than a single symbol would, and they are still not numbers, and the arithmetic on them is not the arithmetic on the rest of the subject.

A game that could have looped and does not #

The contrast worth drawing is a graph with the same shape of analysis and no cycles in it at all.

Everything gets a label here, and the rounds stop because there is nothing left rather than because nothing more can be deduced. Two very different reasons for stopping, and the difference between them is the whole subject of this rung.

That also says what retrograde analysis is, more precisely than “working backwards”. It is a method that agrees with the recursion wherever the recursion applies, and keeps working where it does not. Run it on a game with an ending condition and it produces the outcome classes the ordinary theory produces; run it on a loopy one and it produces those classes plus a residue. Nothing about it is a special case for loops, which is why the draws fall out as a leftover rather than as a rule.

The cost is what changes. The recursion evaluates a position and whatever it can reach; retrograde labelling needs the whole position set in memory before it starts. On a small graph that is nothing, and on a large one it is the difference between an analysis and an impossibility.

Why this is not a cost problem #

It is worth separating this failure from the ones the complexity field is about, since both are described as the theory running out.

A hard game is one whose answer exists and is far away. The whole apparatus of counting routes, positions and depth is about that situation, and every number it produces presumes a value at the end of the search. Every theorem on this site holds for it; the value is well defined; nobody can compute it. The remedy is more computation, better algorithms, or a theorem — all of which are the same kind of thing.

A loopy game is one whose answer does not exist in the form the machinery produces. No amount of computation makes a drawn position have a value, because the definition of value was never applicable. The remedy is a different theory.

The three-cycle above is the sharpest demonstration available: it has three positions, the analysis takes microseconds, and the result is that the ordinary apparatus has nothing to say. Difficulty is not what went wrong.

Naming the loops rather than counting them #

The loopy theory’s own vocabulary is worth a paragraph, because it shows what a compositional account of drawing looks like and how far it is from a single label.

On is the game in which Left may move for ever and Right may not — a position Left is delighted to hold, since it supplies an inexhaustible supply of moves. Off is its mirror. Dud — deathless universal draw — is the game in which both players may move for ever, which is the three-cycle above and the closest thing to a plain draw the theory has.

The point of the distinction is what happens in sums. Add on to a finite game and Left wins, whatever the finite game was, because Left can simply keep moving in the loop until Right runs out. Add dud to the same game and the total is drawn. Both components are “drawn” as positions on their own, and they behave completely differently in company — which is exactly the distinction a single symbol would have destroyed, and exactly why values are defined by behaviour in sums rather than by what a position does alone.

So the loopy theory is not a patch that adds a fifth outcome. It is a set of objects rich enough that the ordinary questions can still be asked, and it pays for that richness by not being an ordered group any more.

The ending condition, made visible #

All of this is one requirement failing, and it is a requirement so quiet that it usually goes unnamed.

Every game elsewhere on this site has some quantity that falls with every move. Counters in Nim, free squares in Domineering, unused vertices in Geography, stones in Clobber. That falling quantity is what guarantees play ends, and the recursion defining a value is an induction along it.

Take it away and two things break at once. Play may not end, so who wins has a third answer. And the induction has no base, so what is it worth has no answer at all.

The two are the same failure seen from two sides, which is why draws and undefined values arrive together and never separately.

Where real games meet this #

Games people actually play are full of loops, and the conventions that handle them are worth looking at as engineering rather than as theory.

Chess repeats positions constantly, and the threefold-repetition rule declares a draw. Go forbids the immediate recapture that would repeat a position, which is the ko rule. Checkers has a forty-move counter. In each case a rule outside the game’s move definition converts a potential loop into a terminating game, and the reason is practical: an unending game is not playable, whatever the theory says about it.

Those conventions are not free. A repetition rule makes the history part of the position — two boards that look identical are different positions if one has occurred twice before — which multiplies the state space and changes what a solver has to store. The ending condition is restored, and the price is paid in the size of the position set.

The theoretical treatment goes the other way: keep the game as it is, admit the loops, and build objects that can describe them. That keeps the position set small and gives up the ordinary arithmetic. Neither is the right answer in general; they are answers to different questions, and knowing which one is in force is most of understanding what a draw means in any particular setting.

Worth noticing too: the repetition convention is what makes a chess endgame table possible, and the table is built by exactly the retrograde method above. The two approaches meet in the machinery even when they diverge in the theory.

What the pictures cannot show #

Three limits.

A drawn position is not a stalemate. Nothing is frozen: both players have moves, play continues, and the game simply never ends. Real games use conventions — repetition rules, move limits — to convert this into a declared draw, and those conventions are outside the theory rather than part of it.

The analysis is over an explicit graph. Retrograde labelling needs every position enumerated in advance, so it is affordable exactly when the position set is small enough to hold. That is a much stronger requirement than the recursion has, and it is why the method belongs to endgame databases rather than to general search.

The outcome depends on who is to move, and the figures fix that. Each drawing here is labelled for one player to move; the other side is a second analysis, and a position can be settled with Left to move and drawn with Right to move. The site’s figures take the side as a parameter for that reason, and a claim about a loopy position that does not say whose turn it is has not said enough.

Nothing here handles loopy games in sums. A drawn component added to a hot one is a genuine question with an established answer in the loopy theory, and it is beyond the machinery these figures use. This site’s loopy figures analyse single positions, and say so.

Reading the rounds #

The number printed in each settled position on these figures is the round it was settled in, and the sequence repays attention because it is the proof laid out in order.

Round one settles the positions with no moves: whoever is to move there has lost, by the convention the whole subject rests on. Round two settles every position with a move into one of those — a win for the mover, established by a single option. Round three settles positions all of whose moves lead into round-two wins, which are losses. And so on, alternating in character: wins appearing as soon as one option is known, losses only when every option is.

Reading the numbers in order is therefore reading a proof by induction on the round, and the induction is on how many rounds a forced win takes rather than on the length of play. A position labelled at round seven is one where the winner can force a finish within a bounded number of moves, and the bound is what the round number records.

The drawn positions have no number because no such bound exists for them. That is the technical content of the fifth outcome and it is stronger than “the game might go on”: in a drawn position, neither player can force a finish within any bound, however large — and the absence of a round number is exactly that statement.

And where it happens in a real game #

Nothing above is hypothetical. A drawn position class occurs in tournament Go, has a name, and is scored as no result.

Who worked it out #

The retrograde method predates the theory it is used with here — it is the standard way of building endgame tables, and the two-rule labelling above is exactly what a chess or checkers tablebase does over its own position set.

The loopy theory proper is Conway’s, with the games named on, off and dud introduced in On Numbers and Games and developed considerably since. What that work provides is the thing this rung says a single “drawn” label cannot: a compositional account, in which loopy positions can be added to each other and to ordinary games and the totals mean something.

The lesson worth carrying is about where a theory’s boundary actually lies. It is tempting to read the recursion assumes play ends as a technical footnote. It is not: it is the load-bearing assumption, and the moment it fails the subject acquires an outcome with no value behind it, an analysis that runs the other way, and a definition of “drawn” that is a hole in a table rather than an entry in it.

Where the ladder goes next #

The loopy anchor has three rungs to here: the games that never end, the analysis that runs backwards, and now the outcome with no value behind it.

The rung above shows the arithmetic failing rather than the classification. One part that never ends takes the game on, whose only move is back to itself, and finds that adding anything to it — a star, a point, its own mirror image — leaves the whole board drawn. So off is exactly the negative of on and their sum is not nought, which is the group law failing for a reason that has nothing to do with who is winning.

When never ending is a win then takes this page’s central point and sharpens it into a measurement. Retrograde analysis labels a position won when somebody can force the opponent to be stuck and leaves everything else blank; calling the blanks drawn is a rule from outside the game, and two other rules are available. Under all three the labelling does not change at all — only the residue does — and on a three-cycle that residue is every position on the board.

That is the strongest form of this page’s argument. The draw is not a fourth verdict computed alongside the other three; it is what the procedure has nothing to say about, and a rulebook decides what to call it.

The one outcome that adds closes the anchor by asking whether anything survives. Loopy play has seven outcome classes rather than four, so the addition table has twenty-eight cells, and eleven of them hold several answers — worse than the finite case rather than better. Two cells are determined: a second-player win added to anything leaves the outcome where it was, and a draw added to a draw is a draw. A draw added to anything else is not.