What the play keeps coming back to

Every play ends and no round settles ends at the edge of the finite. Every game in it is open, in the sense that a win is decided at some finite stage — somebody is stuck — and Gale and Stewart proved in 1953 that every open game is determined however large it is. What that page leaves for later is the other side of the hypothesis: games in which a play can go on for ever and still be won, by one player or the other, according to what the play does over its whole infinite length.

Loopy games are the natural place to ask, because their plays already go on for ever. The gap between two answers shows that a drawn position is where the equations for Left wins have two solutions. When never ending is a win closes that gap by fiat: give every infinite play to Left, or every one to Right, and the drawn positions all go that way at once.

There is a third option, and it is the one that makes infinite play a thing to be judged rather than a thing to be assigned. Look at what the play keeps coming back to.

A winning condition on the whole play #

Mark one position of a loopy game. A play that ends is judged as always: the player with no move loses. A play that goes on for ever goes to Left if it passes through the marked position infinitely often, and to Right if it passes through it only finitely often — which is to say, if from some point on it circulates entirely elsewhere.

That is the condition Büchi used in 1962 for automata reading infinite words, and it is the simplest condition that looks at the whole play rather than at one moment of it. Nothing is drawn under it. Every play either returns to the marked position without end or does not.

The game in the figure is small enough to follow. From a, the only move for either player is to b. From b, Right may return to a and Left has no move at all. At c, both players can only stay at c.

Retrograde analysis settles only what somebody being stuck decides. Left to move at b is stuck and loses; Right to move at a has to go to b, where Left is then stuck, so that is decided too. The other four pairs are drawn: the play at c goes on for ever, and so does the play that shuttles between a and b.

Judged by what recurs, the four drawn pairs split. A play that starts at c stays at c for ever and never visits a, so it is Right’s. A play that starts with Left to move at a goes to b, where Right must return to a, and round again — through a infinitely often — so it is Left’s. No wholesale rule can say that. Giving every infinite play to Left gives Left the pairs at c too, and giving every one to Right gives Right the shuttle.

Every draw of every small game, given a winner #

The family is every game on two positions — 256 of them — and every game on three, which is 262,144: each of the six position-and-mover pairs may have any set of moves among the three positions. Each game is labelled by retrograde analysis and then solved under the recurrence condition with the first position marked.

On three positions there are 923,592 drawn pairs, and every one of them gets a winner: 596,529 go to Left and 327,063 to Right. Every pair the backward labelling had already decided keeps the winner it had — the recurrence condition only speaks where the old rule was silent — and that is checked on every pair of every game rather than argued.

And 15,432 games split their draws, sending some to Left and some to Right. Those are exactly the games a wholesale rule for draws cannot describe, because a wholesale rule is a rule about infinite play in general, and in these games what matters is which infinite play. On two positions only four games split, and all four have the shape of the loop at c above: both players can stay where they are at both positions, and at most a single way across is added — so a play that stays at a goes to Left and a play that stays at b goes to Right.

The wholesale rules were the two solutions all along #

The two wholesale rules are not arbitrary choices, and seeing what they are makes the new rule’s place clear.

The gap between two answers solves the equations for Left wins from below and from above. The least solution is the set of pairs from which Left can force Right to be stuck — which is exactly Left’s winning set if every infinite play goes to Right. The greatest solution adds every pair from which Left can avoid ever being stuck — which is exactly Left’s winning set if every infinite play goes to Left. The two wholesale rules are the two extreme solutions of the same equations, and the drawn set is the distance between them.

The recurrence condition picks a third set, strictly between the two on any game where it splits the draws. It cannot be either extreme solution, because each extreme sends every draw the same way. And it is not a solution of the one-level equations at all: it is the solution of an equation whose right-hand side contains another fixed point. That is the formal content of the phrase a fixed point inside a fixed point, and it is where the extra cost comes from.

A rule judged by content is not a mathematician’s invention #

It would be easy to read the recurrence condition as a device for automata, and it is worth knowing that board games arrived at the same idea on their own.

Chess treats a repeated position as a draw, which is a wholesale rule: the play did not end, so nobody wins. But not every game does. In xiangqi, a player who delivers perpetual check must break it off or lose, and in shogi a fourfold repetition is normally a draw unless one side has been checking throughout, in which case that side loses. Those rules do not ask whether the play went on for ever. They ask what kept happening in it — who was checking — and they award the game by the answer. That is a condition on what recurs, invented by players centuries before anybody wrote it as an equation, to stop one side from escaping a lost position by repeating a threat.

One part that never ends is where this collection first met a game whose whole value was its refusal to end, and a draw is not a value is where the absence of a value for such positions is set out. A recurrence rule does not supply a value either. What it supplies is an outcome for every position-and-mover pair — which is less than a value, and more than anything a draw can offer.

A fixed point inside a fixed point #

The labelling that settles an ordinary loopy game is a single iteration: start from the positions where somebody is stuck and propagate backwards until nothing changes. The gap between two answers writes that as one monotone equation with a least solution, and the least solution is what the propagation computes.

The recurrence condition needs more than one such iteration, and the reason is in the words infinitely often.

A play visits a infinitely often when, however far along it is, it will visit a again. That is a statement with two quantifiers — for every stage there is a later visit — and each quantifier becomes an iteration. The inner one is the old propagation: from which pairs can Left force the play into a given target set? The outer one shrinks the target: a visit to a is only worth forcing if, from there, Left can force another. So the procedure computes the pairs from which Left can reach a, keeps only the visits to a from which Left can reach a again, recomputes, and repeats until the set of good visits stops shrinking.

On three positions, 100,415 games need three or four rounds of the outer iteration, and each of those rounds runs the entire backward propagation again. A game settled in one outer round is a game where every reachable visit to a can be repeated; a game needing four is one where the procedure has to discover, three times over, that some visits it counted on lead to places from which a cannot be forced again.

This is the same alternation the complexity field measures difficulty by, appearing inside a winning condition instead of inside a formula. A condition that says eventually — somebody gets stuck — has one quantifier and one iteration. A condition that says infinitely often has two, nested, and the computation nests with it. Conditions with more alternations exist, and each alternation adds a level of nesting.

Checked against every memoryless strategy #

A nested iteration that produces surprising splits is the kind of computation to distrust, so it is checked against something that knows nothing about fixed points.

A memoryless strategy chooses one move at every position-and-mover pair and never changes its mind. Fix one for each player and the play from any start is determined, and since there are finitely many pairs it eventually repeats: it is a lasso, a path running into a loop. The loop decides the winner — Left if it passes through a, Right if not — unless somebody is stuck on the way. So for each start, the brute force tries every memoryless strategy of Left’s against every memoryless strategy of Right’s, and calls the start Left’s when some strategy of Left’s beats all of Right’s.

For conditions of this kind that is the true answer, because such games are always won by a strategy that needs no memory, whoever wins them. The fixed point and the brute force agree on every pair of every two-position game and on the first 4,096 three-position games, and the full three-position family is left to the fixed point alone only because the brute force would be a billion plays.

What a winning strategy looks like now #

Under the backward labelling, a winning strategy is a round count: from a won pair, move to a pair that settled in an earlier round, and the count falls until somebody is stuck. The paper was about how long reads that count as Zermelo’s real subject — how many moves a forced win takes.

Under the recurrence condition a win for Left can take for ever, so there is no count to fall. What replaces it is a count that falls and then resets. From a pair in Left’s winning set, Left moves so as to get closer to the marked position — closer by the inner iteration’s rounds — and on reaching it starts counting again, towards the next visit. The play never ends and never needs to. The strategy is still a table with one move per pair, still the size of the game, and still found without search; it has simply stopped promising an end.

That is the smallest change to the idea of a strategy that makes infinite plays winnable, and it keeps the property that makes the labelling useful: a player holding the table never has to think. Working backwards describes the table for finite wins; this is the same table with the counting done in loops.

What the three rules have in common #

Set the three rules side by side on the example and a structure appears that is worth stating in general.

Every rule agrees on every pair the backward labelling decided. Those are the pairs where somebody can force the other to be stuck, and no rule about infinite play can touch them, because a player who can force a finite win does not need the infinite case at all.

The rules differ only on draws, and on draws they differ in what they are willing to look at. The rule that calls them draws looks at nothing. The wholesale rules look at one fact about the play — that it did not end. The recurrence condition looks at where it went.

That ordering is the history of the subject in miniature. Zermelo’s 1913 theorem is about finite games and sees only stuck positions. Gale and Stewart’s theorem of 1953 is about games won at a finite stage however infinite they are, which is the wholesale rule’s world. Büchi’s condition of 1962, and the theorem of Büchi and Landweber in 1969 that games with such conditions on finite graphs are determined and won by strategies a finite machine can carry out, is the recurrence rule’s world. And Martin’s theorem of 1975 extends determinacy to every winning condition that can be built from open ones by countable unions and intersections — which includes all of these, and is the largest class for which determinacy has been proved without assumptions beyond the usual axioms.

What cannot be drawn #

Every game here is finite, and determinacy on a finite graph is not the deep part. The graph has six position-and-mover pairs; the nested iteration terminates in at most a handful of rounds; the answer exists because a finite computation produces it. The theorems named above are about games whose positions are infinite sequences of moves, where no computation runs to the end, and none of that is on this page.

Nor is the game without a winner. Gale and Stewart also showed, using the axiom of choice, that a game on an infinite tree exists in which neither player has a winning strategy. That game cannot be drawn and cannot be computed; its existence is proved and its description is not available even in principle. The computations here say what determinacy looks like where it holds and cannot say what its failure looks like.

And one marked position is the simplest case. A condition marking several positions, or asking which of several positions recur, is a different condition, and whether it can still be won without memory is not something the brute force above can be assumed to answer.

The rule the game is played under #

Two rules at once. A play that ends is judged by the normal-play convention: the player with no move loses. A play that does not end is judged by the recurrence condition. The first rule is what makes the decided pairs decided, and the second is silent on them — checked, not assumed, on every pair.

The marked position is part of the rule, not part of the game. The same three-node graph with c marked instead of a hands the drawn pairs out differently, and nothing about the moves has changed. That is the sharpest sense in which a draw was never a property of the positions: it was the rule declining to have an opinion, and a rule with an opinion about where the play goes has one everywhere.

Still open: when the rule needs a player to remember #

Every winner found here wins with a memoryless strategy — the brute force would not have found them otherwise. That is a property of the recurrence condition, and it is not a property of every condition on infinite plays.

Ask instead that the play return to a infinitely often and to b infinitely often. A player standing at a position with a move to each has to alternate between them, and a strategy that chooses by the current position alone always chooses the same one. Whether that ever matters in a small game — and how often, and what the smallest amount of memory is that repairs it — is the question the next computation asks.