A rule that cannot see whose turn it is

A game with turns has no hard drawn part, for a reason that is close to embarrassing. Its position graph records whose turn it is, so it has no odd cycles, so the set of every drawn position with one player to move is a stable set, whatever the game is. That set means nothing. It tells each player only what a legal move already guarantees, and all the information it appears to carry is really in the labels.

But the existence of that set depends on the rule being allowed to tell the players apart. It says, in effect, that X should do one thing and O another. Nobody thinks about a board in that way. A player reading a position sees their own counters and the opponent’s, and the empty place, and most of what is known about a game is expressed from that point of view, as the way a value is written already assumes a viewpoint. An opening principle is stated for whichever player has the move. A rule that distinguishes the colours is a rule with an extra input, and it is reasonable to ask what can be done without it.

So demand more. Declare two positions to be the same when one can be turned into the other by exchanging the colours, along with who is to move. Then look for a stable set that treats them as one. That set is a colour-blind rule: a list of shapes, viewed from the mover’s side, such that a player who always hands the opponent a shape on the list is never stuck. The argument from turns can no longer supply such a thing, because the two given sets are exactly what it rules out. They are carried into each other by the exchange of colours, so neither is unchanged by it.

What the symmetry does to the graph #

Mū tōrere is the right size for this, and it has an unusually rich group of symmetries. Its star can be rotated by any multiple of an eighth of a turn and reflected. A position can have its colours exchanged, together with whose turn it is. Each of these carries legal moves to legal moves, and takes drawn positions to drawn positions. So the 892 drawn positions can be grouped by any combination of those symmetries, each group being one vertex of a smaller graph, with an arc between two classes when any member of one has a move to any member of the other.

There is one thing to check before trusting such a graph. Suppose a stable set is found on the classes, and it is lifted back to every position in the classes it names. The lifted set is still independent, because a move between two of its members would have been an arc between their classes. And each position outside it has a move into it: its class has an arc into the set, so some member of that class has a move into a named class, and the symmetry carries that move to the position being considered, since the symmetry takes moves to moves and takes the lifted set to itself. So stable sets of the class graph are exactly the stable sets of the whole drawn part that the symmetries leave alone, and the correspondence is exact.

The table has three things in it worth noticing. The first is where the odd cycles appear. Rotating and reflecting do not disturb them, and those graphs are still bipartite, because the turn is still recorded in each class. The moment the colours are identified, the turn has been forgotten, and odd cycles appear.

So the theorem of 1953 no longer applies. The game’s position graph has none of the structure that made the question trivial, and a Richardson argument would be unavailable even in principle. The class graph on 33 vertices has odd cycles and could have no stable set at all. That would have been a clear and interesting statement: no colour-blind rule exists. The second thing to notice is that this is not what happens. There is one.

The third thing is the count. Under the board’s own symmetries alone, seven stable sets. Add the exchange of colours and there is only one, both with rotations alone and with reflections too. That is not what generally happens to a count under a bigger group, where it merely falls by some factor. Here the count falls to the smallest value it could have without being none. There is exactly one way to treat Mū tōrere’s drawn positions colour-blind. Nothing about the game suggested that in advance, and the search that shows it takes fifteen steps.

The one rule #

Here is the whole of it.

Sixteen shapes are named and seventeen are not. To use the rule, read the board from one’s own side, with no attention to colour, turning the board if necessary. If the opponent has just handed over an unshaded position, there is a move that turns it into a shaded one, and that is the move to make. If the position in hand is shaded, every move leads to an unshaded one, and any of those that keeps the draw will be answered the same way by a player holding the rule.

The figure does not say which player that is, and there lies its oddity. A set does not belong to a player. It is a property of positions, and the player who can use it is whoever first sees an unshaded position on their turn. The other player is then always moving out of a shaded position and cannot get back to use it. So it matters which class the opening falls in.

The opening position is shaded, so the first player has no move onto a shaded shape at the first turn. Whatever that player does, if it keeps the draw, leaves an unshaded position for the second player, who can then get onto the list and stay on it for the rest of the game. So on the traditional opening the colour-blind rule is a rule for the second player, and Mū tōrere’s opening offers the first player exactly two moves that keep the draw, neither of which reaches the list. The first player is not worse off in result, since the position is drawn. That player simply cannot use this rule, and needs something else to hold the draw from the far side of it, and nothing has been said here about what that something would be.

Does it hold? #

It holds by proof, since both conditions have been checked over all 892 positions in the lifted set. A player who keeps moving into a stable set of the drawn part always has such a move, as long as the opponent stays inside the drawn part. The check that matters more is what that last clause conceals.

Two separate results appear in that table. Against a perfect opponent, one who stays in the drawn part because the labels say so, the rule never fails to have a move, and the game runs to 300 moves without incident. This is the proof at work.

Against a random opponent, something else happens. A random player leaves the drawn part in almost every game. From a drawn position a move cannot reach a position lost for the player taking over, since that would have made the position won, so every such exit is a blunder that hands over a win. The rule then has no shape on its list to move to, because its list covers drawn positions only, and the count stops at that point with nobody having lost. A real player at that moment has a winning position and needs the labels, or something like them, to convert it. So the rule holds the draw and does nothing else. It is exactly what the definition of a stable set describes, a guarantee against being stuck, and it says nothing about winning.

This is a real limitation, and the limitation is an interesting one. The position has become winning because the opponent has blundered, and a rule of sixteen shapes contains no information about that. This is the same division that showed up when a stable set was first compared with labelling. The labels say who wins, and they say “drawn” and stop. A stable set says something only about the positions the labels gave up on. Nothing combines the two without carrying both.

What a list of shapes is worth #

It helps to compare this with the other ways of holding a draw on the same board. The labelling is a table of 1,260 entries, one for each position with a player to move, and a player using it reads off a drawn successor at each turn. The symmetries alone reduce that considerably. Since the game does not care which point of the star is which or which colour is which, a table written from the mover’s side needs one entry per class of position, and for the drawn part that is 33. So far that is only compression, and any game with symmetry gets it, as the catalogue of small regions does for a different reason.

The rule says something stronger than that. A table of classes tells a player, for each of 33 shapes, which moves keep the draw. The rule needs one bit per shape: shaded or not. And the instruction is the same at every turn, namely to move to a shaded shape. Nothing about the move has to be stored, because the shape reached is the whole of the test. On a position with three available moves, the player looks at each resulting board from the opponent’s side and picks the shaded one. That is a real saving, and the question of whether a player would want it is the question of whether a strategy’s size is what makes it usable.

It is also worth saying what the odd loop does to this picture, because it is the reason the result needed a search. In the graph with colours, a player’s rule and the opponent’s rule could be chosen independently: the given sets do exactly that. In the colour-blind graph there is only one rule and both sides must live with it, and the five-move loop drawn above shows the danger, since a walk round it swaps which of the two players is handing over which shape. A rule on an odd loop has to contradict itself somewhere unless it has an exit, and each of the class graph’s odd loops has one, a move out of the loop into a position whose status is already settled. The stable set exists because every odd loop has somewhere else to go, which is the same way a clause triangle in Chvátal’s graph is rescued by a true literal.

Why uniqueness is the surprise #

The result that a stable set exists at all is a measurement rather than a theorem. Nothing cited in these essays would have predicted it, and the graph has odd cycles against it, in a size small enough that one could have had a different answer. With a formula drawn on 33 positions, the same search might have returned none, and on this graph it does not. There is no reason to read that as anything except a fact about this game.

The uniqueness is perhaps more telling. A graph of thirty-three positions with forty-six arcs is sparse, with fewer than one and a half moves a position on average. A move that is the only move leaves a stable set no choice: a position whose one successor is in the set must be out, and a position whose one successor is out must be in, which is how the search finishes in fifteen steps. Mū tōrere is highly constrained, because a player’s options are at most a handful and often just one. What is true for this game may not extend to a game with more options per position, and the rule’s uniqueness may be mostly a statement about how little choice the game offers. A second game with the same colour symmetry would be the test. The obvious candidate fails: Three Men’s Morris cannot be treated this way, because its placing phase breaks the symmetry between the colours, and a position with the colours exchanged is usually not reachable at all.

The history here is worth a sentence. A concept defined in 1944 for coalitions, and adapted by 1953 to directed graphs, has been used in these essays as an existence result, then as a certificate, then as a hard problem. In all those forms, it was asked of an arbitrary graph. Asked of a real game, it first turned out to be trivial, because of the turn. Now asked of the same game in the form a player would actually want, it turns out to be sharply determined, to the point of a single answer. This suggests something about how the definition should be read. It does not tell a player how to win, and it has never claimed to. What it can do, in a small and highly symmetric game, is compress holding a draw into a short list.

The conventions underneath #

A symmetry here must carry legal moves to legal moves, and all of those used do, since the rules of Mū tōrere make no reference to which point of the star is which or to which colour moves first. The traditional restriction on moving to the centre is kept. An exchange of colours is taken together with an exchange of the player to move. Without that the map would not be a symmetry, since a position with Black to move is not equivalent to the same position with White to move.

The class graph has an arc between two classes when any member of one has a move to any member of the other. None of the graphs measured has a class with an arc to itself, which would have barred that class from every stable set. “Exactly one” means that the search finished, having considered every possibility under the two conditions. That applies to the rows of the table with an exact number, and “or more” means the search stopped at its step limit with sets still appearing.

The drawn part was fixed first, by retrograde analysis of the whole game, and the sets are sets of drawn positions only. The opponent in the second row of the play test follows the labels by preferring a winning move and otherwise any drawn one.

What this rule cannot show #

How to win. The rule holds a draw. It contains no information about a blunder or about converting one.

That a player could find it. A list of sixteen shapes is short, but it was found by a search with the labels in hand. Nobody has shown that it can be described by a simple feature of a shape, or that players of Mū tōrere have ever thought in such terms. The figure is not a claim about anyone’s practice, and no ethnographic evidence is being offered about how the game was played.

That this generalises. One game was measured. The result is a fact about a game of 33 classes with very few moves per position. Nothing here says whether other games with a colour symmetry and looping play have no such rule, one such rule or many of them, and a richer game is where the question would become hard, if it ever does.

That the rule is the best one. “Best” is not a property a stable set has. There may be other policies, not stable sets of this kind, that hold the draw just as reliably with less to remember, or that also punish some blunders. The result is only that within this definition the answer is unique.

Still open: whether a colour-blind rule is ever hard to find #

The search here takes fifteen steps, and on the class graph without reflections forty-six, so nothing about these graphs is difficult. The reduction of 1973 says that a colour-blind question is NP-complete on general graphs, since a class graph with odd cycles is a general digraph, but this game is nowhere near that. The measurement that would begin to say whether a real game ever comes close is the same one on larger symmetric games with loops and draws, of which there are few small enough, and for each the step count against the size of the class graph. If the count stays small on every game anyone actually plays, then games avoid the hard case for a further reason, unknown here, on top of the turn. If some game breaks it, then that game would be the first example of a position in a real game for which knowing the labels is not enough to find a simple rule for keeping the draw.