The rule decides who has to remember

One bit of memory finds a place where a winner has to remember something. Judge a never-ending play by whether one position keeps recurring and every winner can play from a table with one move against each position. Ask instead that two positions both keep recurring, and at a hub with a move to each a player has to alternate — which a table cannot do, and 49,487 position-and-mover pairs change hands over the three-position games.

That leaves an obvious question and a tempting answer. Two conditions have been looked at, one needing memory and one not; there are 126 others on three positions, and something about a condition ought to say which kind it is.

The tempting answer is closure under union — if the condition accepts two sets of recurring positions it accepts their union. It is the property that gets quoted, and it is wrong. The condition every position recurs is closed under union, since the only set it accepts is all of them, and it is the condition that needs memory most obviously of all.

Every condition, swept #

A condition here is a family of sets: a never-ending play visits some set of the three positions infinitely often, and the condition says which of those sets go to Left. There are seven non-empty sets, so there are 128 conditions — from the one that accepts nothing to the one that accepts everything.

Against each of them, arenas: every position has at least one move for each player, so nobody is ever stuck and every play is infinite. There are 117,649 such arenas on three positions and the sweep takes a systematic 257 of them.

32 of the 128 conditions have an arena that Left wins and cannot win from a table. The remaining 96 never produced one.

19 of those 32 are closed under union, so the property does not separate the two kinds. It is not that it separates them badly; it gets more than half of the memory-needing conditions wrong.

The first one, and why closure was never going to work #

What a strategy has to remember prices memory on games that end; this is the same quantity on games that do not. The first failure in the sweep arrives at the tenth arena, under the condition Left wins when the play ends up circulating on b alone, or on all three positions. That family is closed under union — its two members are {b} and {a, b, c}, and their union is the second of them.

It is also a condition with a genuine choice in it, and that is what closure cannot see. Left is being offered two quite different objectives, and which one is available depends on where the play has been. A table of moves cannot pursue one objective and switch to the other; it makes the same move at c every time it stands there, and the two objectives want different moves.

Closure under union is a statement about what the condition accepts and not about how a player would go about getting it. Two accepted sets whose union is accepted say nothing about whether either is reachable by a fixed choice. The condition every position recurs, with a single accepted set, is the extreme case: closed under union for want of anything to violate it, and unwinnable without memory the moment a position has two ways out.

The line that does hold #

Put a number on each position and say that Left wins when the largest number that recurs is even. That is a condition on which set recurs, so it is one of the 128 — and only some of the 128 can be written that way.

Which ones is a search: every assignment of the numbers 0 to 5 to the three positions, against the seven sets, asking whether the largest-even rule agrees with the family everywhere. 26 of the 128 conditions can be written as numbers.

And the same 26 are exactly the conditions where the family and its complement are both closed under union. Those are two computations over different objects — one an arithmetic search over 216 assignments, the other a closure test on a family of sets — and they agree on all 128 conditions with nothing left over in either direction.

No condition that can be written as numbers needs memory, anywhere in the sweep. That is the line, and it is a sharp one: 26 conditions on one side with no witness among them, and every one of the 32 witnesses on the other.

The reason is worth stating, because it explains the failure of the single-closure test as well. A condition written as numbers gives a player one thing to want — the largest even number they can keep recurring — and one thing to want is exactly what a table of moves can pursue. A player standing at a position asks which move leads towards a high even number and takes it, and the answer does not depend on where the play has been. Closure under union of the family alone leaves the opponent with a choice of objectives, and an opponent with a choice is a player whose behaviour Left has to track.

What the smallest condition cannot be #

The condition that needs memory with the fewest accepted sets is the one with exactly one: every position recurs. It is the two-target condition of the hub game with a third target added, and the hub shows what goes wrong in three positions.

Of the seven conditions that accept exactly one set, six need no memory and the seventh is this one. The six are the conditions the play settles on exactly this set, where the set is a proper subset of the positions, and each of those can be written as numbers — the positions in the set get an even number, the positions outside get a larger odd one, and the largest recurring number is even exactly when the play stays inside.

The seventh cannot, because the set is everything. There is no position to give a larger odd number to, so there is no way to say and nothing else recurs; and there is no way to say all of them recur with numbers either, since numbers can only express a maximum. What replaces it is a memory — the record of which of the three is still owed. The gap between two answers writes the drawn set as the difference between two solutions of one equation, and this is the same shape one level up: what a number cannot express, a second pass over the same object can.

So the smallest condition needing memory is the only one of its size that cannot name an outside, and the number of things a player has to remember is the number of objectives they have to cycle through.

Where in the 128 they sit #

The 32 conditions needing memory are not spread evenly across the list, and the shape of the spread says something the classification does not.

Sorted by how many sets a condition accepts, the 128 run 1, 7, 21, 35, 35, 21, 7, 1 — the binomial coefficients, since a condition is a choice of accepted sets out of seven. The 32 that need memory run 1, 6, 12, 10, 3, 0, 0 across accepting one set to accepting seven. Nothing that accepts six or seven of the seven sets ever needs memory, and nothing that accepts none does either, which is a triviality: a condition accepting every set is a condition Left cannot lose, and one accepting none is a condition Left cannot win, and neither asks a player to do anything.

The interesting end is the middle. A condition accepting three of the seven sets needs memory 12 times out of 35, and one accepting two needs it 6 times out of 21 — roughly a third at both. Past that the share falls away: 10 of 35 at four accepted sets, 3 of 21 at five.

That is the opposite of what a reader would guess from the hub. The hub’s condition accepts one set and is the hardest thing on the page, so more accepted sets might look like more ways for a table to succeed and therefore less memory. It is not monotone. What matters is not how many sets are accepted but whether the accepted ones can be pursued by a fixed choice, and a condition accepting five of the seven is usually one whose complement is small and simple — a condition Left can win by avoiding two or three particular circulations, which a table does well.

The share needing memory is also a statement about the sample and not only about the conditions, since a condition counts as needing memory the moment one arena of 257 shows it. Raising the sample does not move the 32, so the shares above are stable; what they are stable at is a fact about three positions.

Two positions are too few #

The two-position sweep is complete: 8 conditions against all 81 arenas, every pair checked. Nothing needs memory anywhere in it.

That is not because two-position conditions are all well behaved. Two of the eight cannot be written as numbers — Left wins when exactly one position recurs and Left wins when both do — and on a larger board the second of those is the hub condition, which is the whole of the earlier essay. On two positions there is simply nowhere to put a hub: a player who must visit both a and b infinitely often is a player on a graph with two vertices, where any play that does not stop at one of them already visits both.

So a condition can be unwritable and still need no memory, if the board is too small to make it bite. The test on the condition is necessary and it is not sufficient on its own — it is necessary and sufficient over all boards, which is a different statement and is why a sweep over arenas is the only way to see it.

What the sweep checks about itself #

Two claims on this page rest on a solver that did not exist before it, and both are checked against something already here.

The winner under an arbitrary condition is computed by bolting a finite memory onto the arena — an ordering of the positions with the most recently visited first, and a record of where the current position was found in it — which turns the recurring set is accepted into the largest number recurring is even, and then solving that. On the one condition both methods can state — the play returns to a infinitely often — the new solver is run against the fixed point inside a fixed point over every arena on two positions. 256 arenas, no disagreement.

And the other half — whether a table of moves can win — is not the brute force the earlier essays used. That one plays Left’s tables against Right’s tables, which is the right question only when Right needs no memory either, and under most of these 128 conditions Right does. So Left’s table is fixed and the rest of the arena is read directly: Right wins from a start when the play can reach a place Left is stuck, or a set of positions that is strongly connected, that Left’s fixed choices cannot leave, and that the condition rejects. Every time the table wins somewhere the solver says Left cannot, that is a contradiction and the sweep stops.

What the numbers cannot say #

257 arenas of 117,649 is a sample, and the three-position result is a sample result. The 32 conditions with witnesses are established — a witness is a witness — and the 96 without are established only over the arenas swept. Raising the sample to 514 and to 1,033 finds the same 32, with the first witness of each condition arriving proportionally later, which is what a dense population looks like rather than proof of one.

Three positions is a small board. Of the 96 conditions with no witness, 26 have the property that rules memory out over every board there is; the other 70 are conditions that three positions cannot make bite, exactly as the two-position sweep cannot make the hub condition bite. Nothing here says what happens to them on four.

And the memory is counted as needed or not, never measured. A condition that needs memory is a condition where some table loses, and how much memory repairs it is a different quantity — one bit repaired the hub, and nothing on this page says whether one bit repairs the condition that every position recur.

The convention the sweep runs under #

A player with no move loses, which is the normal-play convention carried over to plays that need not end, and it is why the sweep is run over arenas where nobody is ever stuck: with a dead end anywhere, some starts are decided before the condition is consulted and the measurement is about the dead end rather than about the condition.

The other convention is that the winner of an infinite play depends only on the set of positions recurring, not on the order or the frequency. That is what makes the 128 a finite list and it is a real restriction — what the play keeps coming back to adopts it for the same reason, and a condition that asked, say, for a to recur twice as often as b is not on the list and has nothing to do with any row here.

The surprise: a hierarchy of conditions, not of games #

Everything in the earlier essays about never-ending plays is a fact about a game: which positions are drawn, how many rounds the propagation takes, how large the position graph is. The first theorem is about a game, the rounds are about a game, and what happens when the positions do not run out is about a game.

Memory is not. It is a property of the sentence that says who wins, and the sweep says so in the sharpest available way: the 26 writable conditions need no memory on any of the 117,649 arenas, and the conditions that do need it need it on arenas as small as three positions with six moves between them. Change the board and nothing moves; change the sentence and everything does.

That reverses the usual direction of enquiry. Asking how hard is this game is the question space is the resource and a strategy is not a certificate are about, and the answer is a property of the position graph. It is the same split a puzzle asks once, a game asks alternately draws between a question and the prefix of quantifiers that states it — the difficulty living in the sentence rather than in the object. Asking how much does a winner have to remember is not that question at all, and it has an answer before any board is drawn. The 26 conditions are settled for every board there will ever be, by a search over 216 assignments of six numbers, which takes no time at all and quantifies over an infinity of games.

Still open: how much memory, and on four positions #

Two questions follow and neither is answered here.

The first is quantity. A condition that needs memory needs some amount of it, and the amount is what would turn this table into a scale. The natural measurement is the smallest number of states a winning strategy needs, computed the way the hub’s one bit was computed — by taking the product of the arena with a memory of that size and asking whether the winner comes back. Whether the 32 conditions split into levels, and whether the level is a property of the condition rather than of the arena, is the question the sweep here makes askable.

The second is the 70. Three positions leave 70 conditions untested rather than cleared, and four positions would test them — at the price of 32,768 conditions and an arena count in the tens of millions. A sweep of that shape is not a larger version of this one; it needs the conditions grouped before it is run, and the grouping would be the result.