What a stable set knows about a draw

The trouble with Richardson’s theorem is what it leaves over. On a game that must end there is one stable set, and it means something: it is the set of lost positions. On a graph with cycles there can be many, and it is not obvious that they mean anything. Two positions that move to each other have two stable sets, one each, and backward labelling has nothing to say about either position beyond the single word drawn. So there is a real possibility that the extra sets are only a definition going on working in a place where it has stopped being about anything.

They are about something. A stable set on a graph with cycles has a precise relation to outcomes and a precise game-playing meaning, and both of them can be stated in a sentence and checked on every small game. A stable set is the lost positions, plus a free choice among the draws. And that choice is a way of never being the player who gets stuck, which outcome labelling cannot tell apart from any other way of not losing.

Where the stable sets are free to differ #

Begin with a small game containing all three kinds of position.

The tail on the right is an ordinary finite game, and backward labelling settles it. The rest is drawn: a two-way pair on the bottom, which neither player can leave to advantage, and a position at the top left which can step into that pair and can also move across to a position that wins for the opponent. This graph has exactly two stable sets, and the panels show them. They agree on the decided part. They disagree on which of the bottom pair belongs, and that disagreement then fixes whether the top-left position is out.

The first half of the general statement has a one-line proof each way. Every stable set contains every lost position, by induction on how late the labelling settled it. If all of a position’s moves lead to won positions, and won positions are outside every stable set, then that position has no move into the set, and so it must be inside it. Every stable set avoids every won position, by the same induction. A won position has a move to a lost one, and the lost one is inside, so the won position cannot be inside as well, by the independence condition. So the labelling’s verdicts are binding on every stable set, and they exhaust what can be said for certain.

The second half is the part that is less obvious. Take the positions the labelling leaves as drawn, and treat them as a graph on their own, with only the moves between them. A drawn position has no move to a lost position, since that would make it won. And lost positions have no move to a drawn one, since they only move to won ones. So nothing joins the lost positions to the drawn ones in either direction, and the won positions, each already having a move into a lost one, are satisfied without any help. The two pieces do not interact. It follows that the stable sets of the whole game are exactly the lost positions combined with each stable set of the drawn part, with nothing added or left out.

The census makes this concrete. Of the 9,608 games on five positions, 7,652 have at least one drawn position, and 6,874 are drawn everywhere, so draws are the normal condition and finite games the exception. On all of them the correspondence holds in every detail, as it must. The last column of the table is the point worth looking at. Exactly 612 games have a drawn part with no stable set, and exactly 612 games have no stable set at all, and they are the same games. Whether a game has a stable set is a question about its draws and about nothing else.

So the odd cycle in Richardson’s theorem was always going to lie among the draws, and the figure below shows what that looks like from the outside.

The tail in this figure is finite and labels without trouble. Its lost positions are right there, and a position beside the triangle has a move into it. None of that reaches the three positions going round, because a move out of the triangle does not exist. A single unbroken odd cycle anywhere in the drawn part removes every stable set from the entire game, however much of the rest of the game has been decided. A loop that the labelling simply writes D on, and treats as finished business, has a consequence the labelling cannot see.

What a stable set is for: a player who never gets stuck #

Now the interpretation. Suppose a set S is a stable set and the opponent is to move from a position in S. The independence condition says the move leaves S. The absorbing condition says that from wherever it lands, there is a move back into S. So a player who is handed a position outside S, and who always moves into S, has a reply to everything forever. That player is never stuck, and under normal play a player who is never stuck never loses.

That is the reading the 1944 authors would have recognised: a standard of behaviour that can always reply to what is proposed. In the setting of play, it is a certificate that the game is not lost, and a stronger certificate than the label drawn, because it comes with a complete policy. A draw on its own says that best play from both sides goes on forever. It does not name any policy, and the argument about whether drawn is even a value makes clear how little it carries. A stable set says: here is a set of positions to keep returning to, this is why it never fails, and it can be checked in one pass over the arcs.

The game in the figure is drawn everywhere, and labelling offers one word for all five positions. There are two stable sets. Which of them a player is working with decides which positions count as “already safe”, and these are different policies: b and d are the positions to return to under one, and a, c and e under the other. Each is a complete way of never losing. The player who is holding the set is not trying to win, since neither policy can force the opponent into anything; a stable set is defensive by nature. It says that the opponent’s moves can always be answered and says nothing about how to go on the attack, which is exactly why it gives no new information on the finite part of a game, where a good reply and a winning reply are the same thing.

There is a limit to this reading, and it comes right from the definition. Consider a drawn part with no stable set, the cycle of three being the simplest case. Neither player can lose there, because nobody ever runs out of moves. But no fixed set of positions serves as the thing to keep returning to: each player arrives at each position in turn as the play goes round, since three is odd, so no set can belong to one player’s turns and not the other’s. A position can therefore be a draw with no certificate of this form. That is a sharper statement than it looks, since the play has no choices in it at all. Everything about the cycle of three is forced, and it still has no solution in the 1944 sense.

The parts do not decide the sum #

The idea this subject is built on is that a game breaks into parts, and that outcomes and values can be read off the parts. Stable sets have an interesting and quite specific relationship to that.

A sum is the usual one: two games side by side, and a move in exactly one of them. The table takes each of a few small shapes and adds every pair. Some rows are ordinary. A cycle of two added to itself has two stable sets, which is what parity would predict, and a cycle of three beside a single move, a cycle of two or a cycle of four has none: the odd cycle’s defect is not repaired by that company. That much suggests that stable sets might add the way outcomes add in the theory of loopy sums, with absence in a part implying absence in the whole. And then the table’s most interesting line contradicts it.

A cycle of three added to a cycle of three has three stable sets, although each part has none. A cycle of five added to itself has five, and three and five together have none. The figure draws the first case as a grid of pairs, and the reason it works reaches further than the figure.

The stable set in the figure is a diagonal, and it can be read off directly. From a position where both coordinates agree, any move breaks the agreement, so the diagonal has no arc inside it. From a position where they disagree, one coordinate is behind the other by one step or by two; advancing the other one by the right amount, or advancing this one, restores the agreement, and on a cycle of three a single step does it in one direction or the other. So every off-diagonal position can return to the diagonal in one move.

This is the mirror strategy in a place it has not been before, and it is the surprising connection. Adding a game to itself is the oldest trick there is: whatever the first player does in one copy, the second copies in the other, and so every game plus its negative is a win for the second player. Here there is no second-player win to be had, because every position is drawn. But the mirror still works as a strategy for never losing, and it hands back precisely what the 1944 definition asks for. The two components, each without a solution, have one between them, and what supplies it is the relation between them. A cycle has no way to be consistent with itself, and two copies of a cycle can be consistent with each other.

It also shows that the object is not additive in the way a Grundy value is. A Grundy labelling of a sum is the nim-sum of the labels of the parts, and its zero set is a stable set of the sum. So where both parts have labellings, the sum has a stable set by the old theorem. The cycle of three has no labelling and yet the sum of two of them has a stable set. That set is not the zero set of any labelling of a sum of two labelled parts, because those parts cannot be labelled. It is a different phenomenon, and it does not come out of the Sprague–Grundy theory.

A partner that keeps step #

The lower rows of the table are the part nobody would predict from parity, and they correct a natural guess. It seems reasonable that a partner with an even cycle could never help, because evenness was the whole of Richardson’s condition. The cycle of three beside a cycle of six has three stable sets, and six is even. Beside nine it has three as well. Beside two, four, five, seven and eight it has none.

The explanation is a map rather than a parity. Send each position of the six-cycle to its remainder on division by three. A move on the six-cycle goes to the next position, and the remainder goes to the next remainder, so the six-cycle is the three-cycle gone round twice: every move upstairs is a move downstairs. Now take the diagonal of the three-by-three grid, and take every pair whose image lies on it. Those are the pairs whose two coordinates agree modulo three. A move changes one coordinate by one and so breaks the agreement, and any disagreement can be repaired by one step in one coordinate or the other. Both conditions come straight down from the small grid to the large one. So whenever the partner’s length is a multiple of three, the rescue is the same rescue, pulled back along a map that respects moves.

That says something about what the obstruction was. An odd cycle lacks a stable set because it cannot be divided in step with itself. It does not need its partner to be odd. It needs a partner that shares its period, so that the two together have a quantity both of them advance and either can correct. Lengths two and four share no period with three, and neither do five, seven and eight, and the table finds nothing. What the table has established is a pattern across cycles of length up to nine beside a cycle of three, along with the proof for multiples just given. The converse, that no other length can help, is measured here and not proved.

There is also a limit on how far the diagonal goes, and the cycle of five already passes it. Every position off the diagonal needs a single move back onto it, and on two cycles of five a position with its coordinates two steps apart has no such move. So the five stable sets of that sum are something else, larger than a diagonal, and no description of them is offered here. Three is the one length at which every disagreement is a single step in one direction or the other, so the mirror reading applies there and not in general. On an arbitrary game added to itself the diagonal is usually not a stable set, because a move in a typical graph cannot be matched from everywhere.

The convention named #

All of this is normal play, and the reading depends on it directly. “A player who always has a reply never loses” is a statement about a rule in which the only way to lose is having no reply. Under a rule that scored a repeated position against somebody, as the rules that make Go finite do, a policy of returning to the same set would be illegal or losing, and a stable set would be a poor thing to hold. And under a rule that called endless play a win for one side, as the loopy theory allows, a stable set would be worth one player’s win, and the graph would have to be considered from each side separately.

Second, the label D here means what backward labelling leaves unsettled, with no draw rule added and no count of moves. This is the only reading on which drawn positions form a separate part of the graph with no moves to or from the lost set. A game where a draw was a scored outcome with a separate payoff would not have that structure, and the theorem that existence is decided in the drawn part does not extend to it unchanged.

What the table cannot show #

Whether sums of larger shapes behave like these. The sum table is small and every entry is a single cycle or a single move. It shows that a cycle of three can be rescued by a partner with a matching period and it gives no general description of when a sum of two arbitrary graphs has a stable set. That would be a much bigger question, and nothing here touches it. There is reason to think it is hard, since a formula’s satisfiability can be written as the existence of a stable set of one graph. A sum of two such graphs would be a question about two formulas together.

Whether a player can use a stable set against someone who is not trying to draw. A stable set guarantees not losing, and says nothing about taking advantage of a mistake. Two drawn positions in different stable sets might be very different in how easily an opponent can go wrong from them. That is a real question about drawn play, and it is not one that this object measures, any more than the theory of one endless part measures how a player goes wrong inside it.

Anything about infinite games. The lift of a stable set from the drawn part to the whole graph is proved by induction on the rounds of the labelling. On a graph with infinitely many positions the labelling may need rounds beyond any finite number, and the statement needs its own care. Everything here is finite.

Still open: stable sets where no one is playing #

Everything so far has treated the graph as a game and the stable set as something a player might use. The definition never needed that. A set with no arc inside it and an arc into it from everywhere is a statement about a relation, and the 1944 authors arrived at it by thinking about preferences rather than moves. So a natural test of how far this reaches is to take a graph of preferences that has nothing to do with heaps or boards, and to ask what its stable sets turn out to be. There is a well-known example in which the answer was already famous under another name, and in which stable sets always exist, on graphs that are full of the odd cycles Richardson’s theorem has to exclude. It suggests that the theorem’s condition is nowhere near a description of when a solution exists, and that some entirely different reason can do the same job.