When never ending is a win

Retrograde analysis starts at the positions where somebody has already lost and works outwards. A position with a move to a loss is a win; a position all of whose moves lead to wins is a loss; and whatever is still blank when nothing more can be deduced is a draw.

That last clause is not a computation. It is a naming of the residue — and naming it a draw is a decision made outside the game, by whoever wrote the rules that say what happens when play goes on for ever.

The distinction is easy to miss because the three words sit in one list. “Win”, “loss” and “draw” read as three verdicts of the same kind, produced by the same procedure, and two of them are. The third is what the procedure has nothing to say about, given a name so that the table has no blanks in it.

Why nothing has to be recomputed #

The striking part is how little work changing the convention costs. Nothing is re-searched, because the two labels the propagation does produce never mention infinite play.

A win says: the mover can force the opponent into a position with no moves. That is a finite claim about a finite line of play, and it stays true whatever the rules say about games that go on for ever.

A loss says: every move the mover has leads to a position from which the opponent can do that. Also finite, also unaffected.

So the only pairs whose verdict can move are the ones with neither label — and for those, both players can avoid losing and neither can force a win. Declare infinite play a win for Left and every such pair becomes a win for Left: Left, to move or not, can keep the game going for ever, and Right cannot force a finite win or the position would have been labelled.

What the two labels actually assert #

It is worth writing the two claims out in the form the propagation proves them, because the form is what makes them convention-free.

W at a pair means: there is a move to a pair labelled L. Unrolled, that is a finite tree of moves in which every branch ends with the opponent facing a position with no moves at all — a strategy with a bound on its length, and the bound is what the round number in the second figure records.

L at a pair means: every move leads to a pair labelled W. Also finite, also a statement whose whole content is about positions the game reaches and stops at.

Neither sentence contains the word “for ever”. A rule that changed the value of an infinite run could not touch either of them, and that is the whole reason the three columns of the hero figure share their W and L entries exactly.

What the residue means, by contrast, is a negative: neither player can force the opponent to be stuck. That is a true statement about the position and it does not say who wins, because in a game that never ends nobody is stuck and the losing condition never fires. Somebody has to supply an answer, and the rulebook is where it comes from.

A board where the convention is everything #

The cleanest case is the one with no exits at all.

The three-cycle is where “a draw is not a value” bites hardest. It has no values, no stops, no temperature and no outcome — it has a rule about repetition, and everything about who wins is in that rule.

It is also the cleanest available demonstration that the propagation is not being lazy. There is nothing for it to find: no position on the board has a move to a position with no moves, because no position on the board has no moves. A better algorithm would return the same three blanks, and so would an exhaustive search of every line of play, because every line of play is infinite.

Compare that with the board in the hero figure, where the propagation settles four of the six pairs immediately and stops. The two boards look alike — a cycle in each — and they differ in whether anything anywhere leads out of it. What the residue measures is not difficulty. It is reachability of an ending.

The residue is a theorem, not a limit of the method #

The three-cycle makes it obvious that the propagation is not being lazy, because there is visibly nothing to find. On a large graph it is not obvious at all, and the claim needs stating properly: no algorithm returns fewer blanks.

What the propagation computes, for each player, is the set of pairs from which that player can force the opponent into a position with no moves — the attractor of the stuck positions. The construction is exactly the one on this page: start with the stuck pairs, and repeatedly add a pair when the mover has one move into the set, or when every move the mover has leads into it. It stops when nothing more can be added, and the round number the second figure records is the step at which each pair entered.

A pair left outside both attractors is a pair where neither player can force an ending. That is not a report that the search gave up. It says that from this pair the opponent has a strategy that never walks into the mover’s attractor, and the mover has one too, and both strategies are available at once because avoiding a set is exactly what being outside its attractor means. So the play they produce together is infinite, and no cleverer analysis of the same graph can make it finite.

The second half of the statement is the one that makes the table a table. Both strategies are positional — each is a choice of one outgoing edge at every node, with no reference to how the game reached it — because a reachability objective cannot be helped by remembering the past: if a move is safe once it is safe every time the same node comes round. That is why the object being labelled is a node and a side to move rather than a line of play, and it is the precise sense in which chess’s threefold-repetition rule sits outside this framework: it is a condition on the history, so it cannot be read off the graph the propagation runs on, and a game carrying one is a game whose real position includes a counter.

Real games make this choice #

The choice is not hypothetical, and the two commonest board games make it differently.

Chess declares a threefold repetition a draw, and does so with a rule about the history of the game rather than about the position: the residue is shared, and the sharing is triggered by a count. Go does not; its ko rule forbids the repetition instead, which removes the loop from the graph rather than labelling it — a third strategy, and the only one of the three that keeps the game finite.

A third option appears in the theory of infinite games, where a condition on the infinite play itself decides the winner. That is the convention this essay’s second and third columns implement, in its simplest form: whoever manages to keep the game going wins it.

The three are genuinely different designs rather than three ways of saying one thing, and each pays for something.

Sharing the residue — the chess answer — keeps the game symmetric and gives up decisiveness: a position can be worth nothing to either player with no way to break the tie.

Forbidding the repetition — the Go answer — keeps decisiveness and gives up the simple rule: the legality of a move now depends on the history of the game, so the position a player is looking at is not the whole state.

Awarding infinite play to a player keeps both, and gives up symmetry: one side has a way of winning that consists of doing nothing in particular, which is why real games rarely adopt it and why the theory of infinite games does.

None of the three is wrong. What the figure shows is that the choice is not cosmetic — on the three-cycle it decides every position on the board, and on the hero figure’s board it decides a third of them.

What the model stops short of #

The two one-sided conventions here are the crudest ones. “Whoever keeps the game going wins” is a Büchi condition of the simplest kind, and real conventions are more interesting: a win for whoever visits some position infinitely often, a draw only if a particular loop is traversed, a scoring rule that reads the whole infinite play. Nothing here computes any of those.

And they are not the same as a value. on and off are loopy games with genuine values in the extended theory, and their arithmetic — on + off is not zero — survives whatever convention is chosen for a particular board, because it is a statement about the games rather than about the rulebook. This essay is about the outcome table, not about the value theory that sits above it.

Every claim on this page is about position-and-mover pairs of one kind: a node, a side to move, and either a forced finite win, a forced finite loss, or nothing at all. Nothing else is computed and nothing else is needed.

What the solver computed, and how #

retrograde labels every pair by the standard backward induction with a counter: a pair is a loss when all of its moves have been shown to be wins, and a win as soon as one move is shown to be a loss. Nothing is ever labelled by default, and the order the labels are settled in is recorded, which is what the second figure draws.

The convention is applied afterwards, in five lines: a W stays a win for the mover, an L stays a win for the other player, and a D becomes a win for whichever side the convention favours, or stays blank. Three readings of one labelling, produced from the same call.

That structure is the argument. If changing the convention required a different search, “the draw is a convention” would be a claim about the rulebook; because it requires no search at all, it is a claim about the method — the propagation computes exactly the finite part of the answer, and the rest is filled in by fiat.

The counting is over position-and-mover pairs rather than positions, and that is not bookkeeping either. A loopy game is not a set of positions with verdicts attached: the same node can be a win for whoever is to move and a loss for the other, so the object being labelled has two components. The hero figure’s six pairs are three nodes and two sides, and the two sides come apart on one of them.

One further check runs in the background of all of this. The propagation is given a graph with no cycles at all and asked for its draws; it reports none, which is the assertion that the residue means something. A method that left blanks on a finite game would be reporting its own incompleteness rather than a property of the board.

Reading the two-column figures #

The columns in the comparison figures are counts of pairs, and the shape they make is worth reading rather than skimming.

On the board with a way out, six pairs: three settled as wins, one as a loss, two left blank. Move to the second column and the two blanks become wins for Left, so Left’s count rises from three to five and Right’s stays where it was. Move to the third and they become Right’s, so Right’s rises and Left’s returns to three. Nothing else in either column moves — and “nothing else moves” is a stronger statement than it looks, because it is a claim about every pair of a board whose regions the propagation settled in different rounds.

On the three-cycle, six pairs and six blanks. The first column has three zeros in it: nobody wins anything. The second and third are complete sweeps in opposite directions. A reader who wanted a single sentence for the essay could take that pair of columns as it: the same graph, and two complete and opposite accounts of who wins every position on it.

The board with a drawn half and a decided half is the intermediate case, and it is the one closest to a real game. Half its pairs are settled by the propagation and stay settled; the other half move together. A player on such a board is playing two different games at once — one where the rules decide the winner and one where the rulebook does. Which of the two they are in is not visible from the position in front of them, and the labelling is where it becomes visible.

That is the difference between this figure and the three-column ones above it. A column of counts says how much of the board a convention decides; this says which part, and says it in the only vocabulary the method has — a round number, or nothing. A pair with a round number is one the rules settle. A pair with a dash is one the rulebook settles, and the dash is not a smaller kind of answer than the number. It is the absence of one.

What a convention cannot rescue #

There is a temptation, having seen that naming the residue decides the board, to think that the right convention makes every loopy game decisive. It does not, and the reason is the arithmetic rather than the outcome table.

on is the game whose only move, for either player, is back to itself; off is its mirror image. Under normal play G + (-G) = 0 for every short game there is, with the mirror strategy as the proof — and on + off is drawn, whatever convention is chosen for it, because the mirror strategy answers for ever and never finishes. Declaring infinite play a win for Left does not repair that: it names a winner for the sum without making the sum equal to zero, and the group law stays broken.

So the convention settles who wins this board and settles nothing about what this board is worth. Those are the two questions this site keeps separating, and loopy games are where the gap between them is widest.

Where the choice is actually made #

One more distinction, because it is the one a reader is most likely to carry away wrongly. The convention is not chosen per position. It is a clause in the rules of the game, fixed before anybody sits down, and it applies to every position at once.

That matters for the second and third columns. Reading them as “Left wins these and Right wins those” invites the thought that the two columns could be combined — that some drawn positions might go one way and some the other. They cannot, or rather, a rulebook that did that would be a different rulebook and the columns would be a different measurement. What the figures compare is three games with the same move graph, not one game read three ways by an undecided referee.

It also matters for what a strategy is. Under the draw convention, a player at a drawn pair has a strategy that avoids losing and no strategy that wins. Under “infinite play is a win for Left”, Left at the same pair has a winning strategy, and it is the same strategy — avoid losing — reclassified. Nothing about the play changes. The play was always available; the rulebook decides whether it counts as a victory.

That is the sharpest form of the essay’s claim. The strategies are computed and the verdicts are chosen, and a table that prints them in one column hides which is which.

Where the ladder goes next #

The rungs below this one built the machinery — the propagation, the draw as a residue, and the games that never end with their own arithmetic. What this rung adds is that the last step of the method is a choice.

The rung above takes that choice and asks what it survives. The one outcome that adds puts two loopy boards side by side and reads the outcome of the sum off the outcomes of the parts, which is the question this page’s last two sections keep deferring to the value theory. Loopy play has seven outcome classes where finite play has four, so the table has twenty-eight cells rather than sixteen — and eleven of them hold several answers, which is worse than the finite case rather than better. Two cells are determined, and the useful one is the same one that is determined for finite games: a second-player win added to anything leaves the outcome where it was.

Which is the strongest available reply to the temptation this page ends on. A convention decides who wins a board, and the moment two boards are put together the convention decides almost nothing, because the outcome of a sum is not a function of the outcomes of its parts under any rulebook. That is what the value theory exists to repair, and it is why on + off stays broken however the referee is instructed.