Start at the end and work backwards

Three positions. From the first, Left may move to the second or to a position where the game ends; Right may only move to the second. From the second, either player must move back to the first.

Every value on this site is defined by recursion on the options, and the recursion needs somewhere to bottom out. Here it does not have one: asking what the first position is worth requires knowing the second, which requires knowing the first.

What replaces the recursion is not a cleverer recursion. It is retrograde analysis, and it runs in the other direction.

Start from what is known without any theory at all: a position in which the player to move has no move is a loss for them. That is the normal-play convention and it needs nothing else.

Then propagate. Two rules, and the asymmetry between them is the whole algorithm:

A win is settled as soon as one move is known to lead to a loss for the opponent. One good move is enough; the rest do not matter.

A loss is settled only when every move is known to lead to a win for the opponent. All of them, without exception — so a loss cannot be declared until the last option has come back.

That difference is implemented with a counter. Each position keeps a tally of how many of its moves are still unlabelled; a win is pushed out the moment a losing successor appears, and a loss when the tally reaches zero.

The draws are what is left over #

Run the propagation until nothing more can be deduced. Some positions will still be blank.

Those are the draws — positions from which neither player can force a win, so the game goes on for ever. And the point worth stopping on is that nothing tested for that. There is no draw rule, no cycle detection, no check for repetition. A position is drawn precisely when the propagation never reaches it, which is a fact about the algorithm rather than a property anybody looked for.

That is a satisfying thing for an algorithm to do. The definition of a draw is negative — neither player can force a win — and negative definitions are usually awkward to compute. Here the negation is free: it is the complement of what the propagation reached.

It also explains why loopy games needed a fifth outcome rather than a fourth. The four classes — previous, next, Left, Right — are the four combinations of “does Left win moving first?” and “does Right win moving first?”, and they are exhaustive only if each question has an answer. A drawn position is one where the honest answer to both is neither, which is a third value for each question and not a fifth combination of two. The vocabulary was built assuming a total outcome and has to be extended rather than filled in.

Why a loss cannot be settled early #

The asymmetry between the two rules is the part worth being careful about, because getting it the wrong way round produces an algorithm that looks right and is not.

Suppose losses were settled as soon as one move led to a win for the opponent. Take the three-cycle: from A, the only move goes to B, and B’s only move goes to C. Nothing is known about any of them, so nothing would fire — which is correct here by accident. Now take the loop with an exit. Right, at the top position, has one move, into the loop; the loop leads back. Settling a loss on one bad-looking move would declare Right lost the moment the loop position was tentatively labelled, and the loop position is never labelled at all.

The rule as stated cannot make that mistake, because “every move leads to a win” is a claim that requires every move to be known, and in a drawn region no move ever becomes known. The counter is what enforces it: it starts at the number of moves and only ever decreases when a genuine label arrives.

A win, by contrast, is a positive claim — there exists a good move — and one witness settles it. So the two rules are not an implementation trick; they are the difference between an existential and a universal quantifier, and the algorithm is that distinction made into a data structure.

A game that never ends and still has a winner #

The obvious inference from all this is that loopy games are drawn games, and it is wrong.

That position is called off in the literature, and its mirror is on. They are the simplest loopy games there are, and they show that “the play never ends” and “nobody wins” are different statements. The player who never runs out of moves wins under the normal-play convention, because the convention is about being stuck, not about finishing.

The first figure’s graph is the mixed case: from its top position Left can either loop for ever or step out into a position that ends. Left, moving first, takes the exit and wins. Right, moving first, has only the loop, and neither player can force anything — so the position is a win for Left moving first and a draw otherwise, which is an outcome class normal-play theory has no letter for.

The control case, where it agrees with the recursion #

An algorithm reporting draws is only worth something if it can also report their absence.

The site’s gate requires exactly that. Four games are run: two whose draw counts are known by inspection, one loopy game with no draws, and one acyclic game whose draw count must be zero. If the acyclic case ever reported a draw, every draw on this page would be suspect.

That is the standing habit here, applied to an algorithm rather than to a value. An assertion that has never rejected anything proves nothing, and an algorithm that reports draws is in particular danger of it: a bug that simply failed to propagate would produce a page full of dashes and a caption that sounded profound.

The leftover is not merely leftover #

The drawn set is described above as the complement of what the propagation reached, which is true and makes it sound like a residue — the positions the algorithm ran out of things to say about. It is more than that: it is closed, and the closure is what makes it an answer rather than an absence.

The argument is one line, and it is the two rules read backwards. Take an unlabelled pair — a position with a player to move. If every one of that player’s moves led to a labelled pair, the position would be labelled: a win if any of them was a loss for the opponent, and a loss if all of them were wins. It is unlabelled, so at least one move leads to another unlabelled pair.

That holds for every unlabelled pair, for whichever player is to move. So inside the drawn set both players always have somewhere to go that stays inside it.

Which means the drawn set is a trap. A player who has decided to draw plays to stay in it and never runs out of moves, because a move within it always exists; the opponent playing the same way keeps the play there for ever; and neither is ever stuck, so neither ever loses. The set is not what is left after the answer has been computed — it is the answer, with its own strategy attached.

Which gives a draw a certificate #

That is worth pressing, because a draw looks like the one outcome that cannot be demonstrated.

A win is demonstrated by exhibiting play: a strategy tree, finite because the winning line ends, which anybody can walk. A draw is a statement about a play that never finishes, and there is no finished object to hand over.

The trap is the object. To prove a position drawn, exhibit a set of pairs containing it such that from every pair in the set the mover has a move back into the set. That set is finite whenever the graph is, checking it is a pass over the set’s own edges, and it establishes an infinite fact without anybody having to play for ever.

So the negative definition is not merely free to compute — it is free to certify. Neither player can force a win is a statement with two quantifier alternations in it, and the trap collapses them into a property a reader checks locally, one position at a time.

Least and greatest #

The pair of facts has a name worth having, because it says why the algorithm could not have been arranged the other way round.

The propagation computes the least set closed under the two rules: it starts from the terminal positions, which are forced, and adds only what is forced by what is already there. Nothing enters the labelled set without a reason, so the labelled set is the smallest one consistent with the rules.

The drawn set is therefore the largest set with no reason in it — the largest trap, the biggest region in which both players can keep going indefinitely. And the two are complements by construction, which is the sense in which one computation delivers both.

Turn it round and the asymmetry the essay makes so much of falls out again. A win is an existential claim and existentials are established from below, by exhibiting witnesses until no more can be found; a draw is a universal claim about an infinite play and universals of that kind are established from above, by finding the largest region nothing has been able to refute. The algorithm runs upward from the terminals because that is the direction the smaller of the two sets grows in, and it gets the larger one for nothing by looking at what it did not touch.

What the analysis costs, and what it gives up #

Retrograde analysis visits each position once and each edge once, so it is linear in the size of the position graph. That is cheap — for a graph anybody can hold.

The catch is that it needs the whole graph in advance. The ordinary recursion explores from a starting position and never builds the parts it does not need; retrograde analysis must enumerate every position first, because a loss cannot be settled until all its predecessors are known. For a game with a large state space that is the difference between feasible and not.

There is a second thing it needs that the recursion does not: the predecessors. A recursion walks forwards along moves, which is the direction the rules are written in. Retrograde analysis walks backwards, and the reverse of a move relation has to be built explicitly — for a game defined by rules rather than by a table, that means enumerating every position and every move first, just to know which positions lead where. The cost of enumerating a game’s positions is the thing that separates the tractable families from the rest, so this is not a small requirement.

It also gives something up that the recursion provides for free: a value. Retrograde analysis returns an outcome class and nothing more. It cannot say what a position is worth, cannot be used to compare two positions, and offers nothing that adds. The whole apparatus of values needs the recursion, and the recursion needs play to end.

That is the real cost of losing the base case, and it is much larger than the algorithmic one. A theory of outcomes is a theory of single positions; a theory of values is a theory of positions that can be put together.

The gap shows up the moment two loopy components are placed side by side. Outcome classes do not determine the outcome of a sum even for ordinary games — that failure is why values were invented — and adding a drawn component makes it worse rather than better: a drawn component in a sum can be ignored, or can poison the whole thing, depending on details the outcome class does not record. Retrograde analysis run on the sum answers the question, and it has to be run again from scratch for every sum, which is precisely the situation the value theory was built to escape.

What the solver computed, and how #

retrograde takes a game as a list of positions with Left-moves and Right-moves, and labels each (position, player to move) pair.

It begins by finding every pair with no moves and marking it a loss, then walks a queue. For each settled pair it looks at its predecessors — computed once, up front, by inverting the move lists — and applies the two rules: a predecessor of a loss is immediately a win, and a predecessor of a win has its counter decremented and becomes a loss when the counter empties. Whatever is unlabelled when the queue drains is a draw.

The round number in each circle is the queue generation the label was settled in, which is what makes the propagation visible rather than merely reported. A position labelled in round zero had no moves at all; round one is one step out from that, and so on.

Nothing in the code looks for a cycle. That is deliberate and is the essay’s claim stated as an implementation detail: the drawn set is what the propagation did not reach, and a separate cycle detector would be a second, redundant, disagreeing answer to the same question.

Where the model stops #

Outcomes, not values. Everything on this page reports who wins. There is a theory of loopy values — with objects called stoppers, and a procedure called sidling that finds them — and none of it is here.

Small graphs. Every game drawn has at most four positions. Retrograde analysis is used in practice on endgame tablebases with tens of billions, and the algorithm is the same one; what changes is the engineering around holding the table.

Two players and no repetition rule. Real games with loops usually have a rule about repetition — a draw by threefold repetition, a ko rule — that makes the position graph acyclic again by adding history to the position. That is a legitimate and very common escape from everything on this page, and it works by changing what a “position” is.

Only the normal-play convention. Everything here assumes the player who cannot move loses. Under misère play the propagation starts from the same positions and assigns them the opposite label, and the rest of the algorithm is unchanged — which makes loopy misère outcomes easy in exactly the way loopy misère values are not.

The fifth outcome has no letter. The essay writes “a win for Left moving first, otherwise a draw” in words because the four-letter vocabulary does not extend cleanly. The literature has notation for it; the notation is not obviously better than the sentence, and this site prefers the sentence.

Who found it, and when #

Retrograde analysis is older than combinatorial game theory and comes from a different tradition: it is how chess endgame tablebases are built, and Ströhlein computed the first ones in 1970 by exactly this propagation. The win-early, lose-late asymmetry is the standard formulation and is what makes the algorithm linear.

The loopy game theory it is being applied to here is Conway’s, in On Numbers and Games (1976) and Winning Ways (1982), where on, off and the drawn games are given values in a theory that extends the ordinary one. The two traditions meet awkwardly: the tablebase builders had an algorithm and no algebra, the game theorists had an algebra and mostly finite games, and the loopy chapter of Winning Ways is where somebody put them together.

The chess connection is worth taking seriously rather than treating as an anecdote. A tablebase is exactly this algorithm run on a position graph of billions, and the reason it is possible at all is that chess with the fifty-move and repetition rules has a finite position graph — the rules that stop the game looping are what make the analysis terminate. Strip them out and chess becomes a loopy game with a large drawn region, which is the situation every essay on this page is describing at a scale of four positions instead of a trillion.

Where the ladder goes next #

This is the second rung on the loopy ladder, after the observation that the recursion has nothing to stand on. That rung says what breaks; this one supplies what replaces it, and finds that the replacement answers a smaller question.

The next rung is the one this essay declines: stoppers, and the values that survive. A loopy game has no canonical form of the usual kind, but some loopy games have a stopper — an equal game from which play does end — and sidling is the fixed-point procedure that finds it. That would restore comparison and addition to part of the loopy world, which is the thing this page most conspicuously does without.