One bit of memory

What the play keeps coming back to gives a never-ending play to Left when it passes through a marked position infinitely often, and finds every draw of every small loopy game acquiring a winner. It also finds, by trying every strategy of a particular kind, that those winners never need to remember anything. A table with one move for each position-and-mover pair — a memoryless strategy — wins whatever a winner can win.

That is a property of the condition, not of games. The condition asks about one position. Ask about two — Left wins a never-ending play that passes through a infinitely often and through b infinitely often — and a table of moves can fail where a player who remembers one thing succeeds.

A hub with two spokes #

The game has three positions. At the hub, Left chooses a spoke. At either spoke, Right has one move, which is back to the hub. Nobody is ever stuck except in the positions where the rules give a player nothing to do, and the play from the hub goes on for ever.

Left wants both spokes visited infinitely often. The strategy is obvious to any player: take a, then b, then a, then b. And no table of moves by position can play it. A memoryless strategy for Left has exactly one entry that matters — what to do at the hub with Left to move — and whatever it says, it says every time. Take a always and the play is hub, a, hub, a, and b never recurs. Take b always and a never does.

So with memory Left wins from the hub, and without it Left loses. The figure’s table shows the loss spreading: the two pairs where Right stands at a spoke and must return to the hub are won for Left by a player who remembers and lost by one who does not, since both lead straight back to Left’s choice. Three pairs change hands, and the game has six.

Three ways to play the same position #

The three plays are the whole of Left’s options, laid out. The first two are the only two memoryless strategies Left has — the hub is the only place Left ever chooses anything — and each produces a play that circulates through one spoke. The third is a strategy of a different kind: its choice at the hub depends on what happened last time. A reader looking at a single move of it cannot tell it from one of the other two. The difference is only in the sequence.

That is exactly the distinction the earlier essay’s brute force was built on. It tried every memoryless strategy and found that none was ever missing. On this condition the same search, run on the hub, finds Left losing — and a search that allowed memory finds Left winning. The two searches disagree, and the disagreement is the finding.

Moving the memory into the positions #

How much memory, and what kind, is the natural next question, and the hub answers it by construction: one bit, recording which spoke is owed.

The construction is the standard one, and it is worth seeing because it explains why one bit is enough rather than merely observing it. Make two copies of the game, one labelled owing a and one owing b. A move goes to the same copy, except that leaving the spoke currently owed switches to the other copy. Then a play that passes through a in the owing a copy infinitely often must have passed through b between every two such visits — it had to switch copies and switch back — so it visited both spokes infinitely often. And any play that visits both infinitely often does pass through a while owing a infinitely often.

The two-position condition on the game is a one-position condition on the doubled game. The earlier essay’s nested fixed point solves one-position conditions, and its winners need no memory; so a winner on the doubled game plays from a table of moves by doubled position — which, read back on the original game, is a table of moves by position and bit. The memory has been moved into the positions, and the positions have doubled to hold it.

The doubled hub, solved #

The doubled game is small enough to solve by hand alongside the computation, and doing so shows the bit at work in the arithmetic rather than only in the construction.

It has six positions and so twelve position-and-mover pairs. Four of them are decided before any iteration runs: Left standing at a spoke has no move in either copy, so a and b with Left to move, owing either spoke, are lost for Left. Working backwards settles those and stops, because nothing else ever gets stuck. The backward labelling leaves six of the remaining eight drawn — the hub with Left to move in both copies, and the spokes with Right to move — and the hub with Right to move is Left’s, since Right has nothing to do there.

The one-position condition then gives Left all eight. The nested iteration takes two outer rounds and twelve rounds of the inner propagation between them, the longest inner run being six. In the first outer round the target is every pair, and the propagation finds Left able to reach the marked pair from everywhere Left is not already stuck. In the second, it keeps only the visits to a while owing a from which that visit can be forced again — and all of them can, because from a owing a the play goes to the hub owing b, then to b, back to the hub owing a, and to a again. The target does not shrink, and the iteration stops.

So Left wins eight of the twelve pairs of the doubled game, and the four it loses are the four where it is already stuck. Read back on the hub, the eight are every pair of the original game in which Left is not stuck, in both states of the bit — which is the verdict the hub’s table gives with memory, and three pairs more than the verdict without it.

That doubling is the price, and it is a price in exactly the currency space is the resource says games are really measured in. A memoryless strategy is a table the size of the game. A strategy with one bit is a table twice the size. The hub needs the larger table and cannot do with the smaller.

How often memory decides #

A single game where memory matters could be a curiosity, so the question is put to every small game.

Each game is solved twice under each condition. Once by the nested fixed point — on the game itself when one position is asked for, and on the doubled game, which allows one bit, when two are. And once by trying every memoryless strategy of each player against every memoryless strategy of the other.

Asking that one position recur, memory changes nothing, in either family. That is the earlier essay’s finding confirmed by a second route: nought pairs on two positions and nought on three.

Asking that two positions recur, memory changes the winner of 49,487 pairs in 8,803 of the 262,144 three-position games. In each of those pairs Left wins with one bit and loses with none. And the count on two positions is nought again, for a reason worth stating: in a two-position game both targets are all the positions, so any play that keeps moving between them visits both, and any play that stays at one visits only that one — the choice at each position is the same choice every time, and no alternation is needed.

The reverse never happens. No pair anywhere is won without memory and lost with it, which is checked on every game rather than assumed — memory can be ignored, so it can only help.

The census also says how large the effect is against everything Left wins. Under the two-position condition Left wins 677,782 pairs of the three-position games when one bit is allowed, and 49,487 of those are lost without it: about one winning pair in fourteen depends on the bit. That is small enough that a player choosing moves from the position alone would win almost everything a remembering player wins, and large enough that a solver which assumed memorylessness would be wrong somewhere in one game in thirty. It is also the sort of error that is invisible from inside a single game, because the memoryless strategy looks exactly like a good one until the second visit to the hub.

There is a cost comparison hidden in how the two answers were found, and it runs the opposite way from what the words suggest. The search that forbids memory is the expensive one: it tries every memoryless strategy of each player against every one of the other’s, and the number of such strategies is a product over positions of the moves available, which grows exponentially with the game. The computation that allows memory is the cheap one: it doubles the positions and runs the same nested propagation, which grows with the size of the doubled graph and nothing more. Allowing the winner a bit of memory makes the winner easier to find, because it turns a search over strategies into a propagation over positions — and the doubled graph is what that trade looks like on paper.

Memory, draws and the one-position condition #

The two-position condition hands out draws the way the one-position condition does — every never-ending play is judged, and nothing is drawn — so the memory it demands is not a way of breaking ties. It is a demand the condition makes on winners.

That is worth setting against the ways infinite play has been treated before. Loopy games introduced plays that never end and the draw that comes with them; a draw is not a value found that a draw has no number behind it; when never ending is a win handed the draws out wholesale. Each of those rules treats an infinite play as one kind of thing. The recurrence conditions treat it as a record of where it went, and once a condition reads a record, it can ask a question whose answer a winner has to keep a record to secure.

It is the same observation alternation is the difficulty makes about quantifiers, one level along. Some position recurs is one alternation and needs one nested fixed point. Each of two positions recurs is a conjunction of two such statements, and a conjunction of two recurring events is the smallest statement about an infinite play that a position cannot witness by itself.

Why one bit suffices here, and when it does not #

A bit suffices for two targets because the only thing worth remembering is which target is owed. With three targets the same construction needs a counter that cycles through three values; with k targets that must all recur, k values of memory. Nothing in the census tests those, and they are standard.

Conditions that ask something more intricate about which positions recur need more. A condition may say that Left wins exactly when the set of positions visited infinitely often is one of some listed sets — a Muller condition, after McNaughton’s work on such automata in 1966 — and for those the memory a winner needs can grow as fast as the number of orderings of the positions. Gurevich and Harrington showed in 1982 that remembering the order in which positions were last seen is always enough, and Dziembowski, Jurdziński and Walukiewicz measured in 1997 exactly how much of that record a given condition requires.

Between the one-position condition and those sits a condition that ranks positions by number and lets the play be judged by the largest rank that recurs — a parity condition — and it has the property this essay’s hub lacks: Emerson and Jutla, and independently Mostowski, proved in 1991 that parity games are won without memory. That is why the parity condition became the one everything else is translated into, with the memory carried in the positions exactly as the doubled hub carries its bit.

What this has to do with the strategies drawn elsewhere #

Almost every strategy described in these essays is memoryless without anyone saying so. The backward labelling of working backwards produces a move for each position; a Nim player’s rule reads the heaps and nothing else; the strategy that is a symmetry answers the last move and forgets it. That is not a coincidence of style. It is what finite games under normal play guarantee: a winner can play from the position alone, because the position already records everything that matters about the past.

What a strategy has to remember measures a different thing under a similar name — how many positions a strategy must tell apart, and how many values among them — and it is worth keeping the two senses of remember apart. That essay’s strategies distinguish positions. The hub’s strategy distinguishes histories that arrive at the same position, and that is only ever needed when the winning condition looks at the whole play.

So the hub marks a boundary. On one side are the games of this collection — finite, or loopy with draws, or loopy with a single recurring target — whose winners play from the board. On the other are games whose winners must keep a record, and the smallest record is one bit.

What the census cannot say #

Two targets is the only condition beyond one that is counted. Muller and parity conditions are named above, not measured, and the claims about them are theorems quoted rather than checks run.

Three positions is small. The brute force over memoryless strategies is cheap only because a three-position game has at most three choices at each of six pairs; the counts are exhaustive for that family and say nothing about how common memory-dependent pairs become in larger games.

And every game here is finite. The theorems quoted are about games on infinite graphs and trees, where a finite memory is not guaranteed to exist for every condition at all; that it does exist for conditions of the kinds named — and how much — is the content of those theorems, and none of it is on this page.

The rules this depends on #

A play that ends is lost by the player who cannot move; a play that goes on for ever is judged by the stated condition on which positions recur. The census uses the first position and the second as its two targets throughout.

Both parts of the rule matter to the hub. The finite part is why Right’s positions at the spokes are forced, and the infinite part is why Left’s choice at the hub cannot be made once and for all. Change the condition to one position and the hub needs no memory; give Right a second move from a spoke and the counts change. The memory is a property of the rule and the board together.

The surprise: the board was never the whole state #

Every game in the earlier essays has had the property that the position is the whole state of the game — that whoever sits down at a position knows everything a strategy could need. It is so universal that it is never stated.

The hub breaks it with three positions and one extra word in the winning condition. The position is still everything about the board; it is no longer everything about the game, because the game now cares about history, and a history is not a position. The winning condition reached back into the play and took the state with it, and the doubled graph is what it looks like to put the state back.

That is the step from the games Zermelo wrote about, whose winners read the board, to the games that verify computer programs, whose winners must carry a record — and the smallest example of the step fits on a hub with two spokes.