Taking turns removes the hard part

Chvátal’s construction left a question hanging. It drew a formula as a game in which every position was drawn, and it showed that deciding whether such a graph has a stable set is NP-complete. The graph it drew is not one anybody would play on, though, and the essay ended by asking the obvious thing: whether a real game, one with draws and a rule set not built for the purpose, has a drawn part in which finding a stable set is genuinely hard. A solved game seemed the place to look. Label it, keep the drawn positions, and search them.

The measurement is easy to make, and it returns an answer faster than the search can be started. The question is closed by an argument of about three lines, and it had been available since 1953. It is worth seeing why it took a measurement to notice, because the argument turns on something that all the graphs in the earlier essays quietly left out.

Those graphs have positions and moves and nothing else. The definition of 1944 needs no more, and the census of five-position games ran over every such graph regardless of where it came from. But a position in a game between two people carries one further fact. Somebody is to move. Two boards with identical stones and different players to move are different positions, with different moves out of them and usually different values. A graph that records this has a particular shape, and most of the graphs in the census do not have that shape.

What a turn does to a cycle #

Take the smallest graph with no stable set, a cycle of three. In the plain form a token goes round from a to b to c and back. Now write the player to move into each position, as a game has to.

Going round once does not bring the game back to where it started. After three moves the token is at a, and it is the other player’s turn, so this is a different position. Only after six moves has the position actually returned. The cycle of three has become a cycle of six, which is the case Richardson’s theorem handles. The obstruction has gone without anything about the board having changed.

The general statement needs no measurement. Every move in such a graph goes from a position with one player to move to a position with the other to move. So the positions fall into two classes and every arc crosses between them, which is to say that the graph is bipartite. Any closed walk returns to the class it began in, so it uses an even number of arcs, and no odd cycle can exist at all. This holds for every game in which the two players strictly alternate and the position records whose turn it is, whatever the game’s rules are.

Richardson’s theorem then promises a stable set. In fact there is no need to invoke a theorem, because two stable sets can be written down by inspection. Take the drawn part of the game, and in it every position with X to move. No move joins two of these, since every move changes the player to move. And each remaining position, with O to move, has a move into the set, since a drawn position always has a move to another drawn position, and that position has X to move. That is both conditions. The same is true with X and O exchanged.

This answers the question that the construction left open, and it answers it in the negative. In a game with alternating turns, the drawn part always has a stable set, and two of them need no search at all. Whatever else may be hard about a real game, this is not.

Two real games #

The argument is short enough that it deserves checking on something that was not chosen for the purpose. Mū tōrere is a Māori game played on an eight-pointed star, already solved here and with draws in abundance. Three Men’s Morris is an old and widespread game, played on a three-by-three grid with a placing phase and a sliding phase, and it has an interesting mixture of a forced beginning and looping play.

Labelling gives Three Men’s Morris as a win for the player who places first, which matches what is known of the game. The position graph has 5,390 positions and 21,509 moves, and the search visits only what can arise from the empty board. Mū tōrere’s graph has every arrangement, reachable or not, and comes to 1,260 positions with a player to move. Neither drawn part has an odd cycle, as they could not. Each pair of given sets passes both conditions. They split the drawn part of Mū tōrere exactly in half, because the game is symmetric between its colours. Three Men’s Morris splits it as 520 and 688, because the first player’s extra counter during placement breaks the symmetry.

The structure of the drawn parts differs in ways worth seeing.

In Three Men’s Morris 952 of 1,208 drawn positions lie on no cycle at all. They are in the placing phase or are on their way somewhere, and they are drawn only because of what they lead to. Everything that can actually circle is in one block of 256 positions, reached once the counters are down and sliding. In Mū tōrere the largest knot takes most of the game, 540 positions, with sixteen others of ten positions each, and 192 drawn positions are not in any knot. These are quite different things to have called drawn, and labelling writes the same letter on all of them.

The knots are also where the difference between a stable set and an outcome label could matter in principle. Inside a knot no position is forced, and any answer to the question of a stable set has to be a choice made consistently around cycles.

What the given sets do not say #

An easy existence proof should raise a suspicion, and in this case the suspicion is justified. A stable set was described in the earlier essays as a kind of certificate: a player who keeps moving into it never gets stuck. The set of all drawn positions with the opponent to move certainly meets the definition. What does it certify?

The answer is nothing beyond the labels. Taken over the whole graph, “move to a position with the opponent to move” is what every legal move does, so every player obeys it without trying, and a random player obeying it loses about half the time. Inside the drawn part, what makes the set a stable set is the claim that a drawn position always has a move to another drawn position, and it takes the labels to know which of the moves those are. So the set knows how to stay in the drawn part only because it has been told what the drawn part is. A player needs a move to a drawn position, and the labelling supplies that. The set adds no further information.

That is why this existence result is so much cheaper than the Chvátal one. The earlier theorem was about a set doing real work: a choice on two-way pairs that encoded a truth assignment, with clause triangles checking it. In a game with turns, all that can be done with no choices at all. The mover is doing what the truth assignment did, and it is free.

That is not to say that nothing else exists. The search finds other stable sets in the drawn part of Mū tōrere, smaller than the given ones and mixing the two players to move, and each passes both conditions. On Three Men’s Morris the same bounded search meets nothing but a given set, and since it stopped at a step limit that is only a report on the search. These might be interesting: a set that includes some positions of each kind is making a real statement about which positions to hand over, a statement not simply implied by the turn. Whether any of them means something for a player is the question that the next essay takes up, by demanding something that the turn can no longer supply.

The whole census, doubled #

Two games and one formula are examples. The claim is about every game, and on small graphs it can be checked completely, including the graphs that have no stable set to begin with.

Of the 4,096 labelled graphs on four positions, 214 have no stable set, and each of them has an odd cycle, as Richardson’s theorem requires. Doubling them produces 214 games that do have a stable set, with no exceptions, and doubling all the others does not remove the stable set they had. So doubling only ever moves a graph in one direction. The fewest stable sets of any doubled game is one, which seems at first to conflict with the two sets promised above. It does not, because those two were sets of the drawn part. On a game with positions that are decided, the lost positions have to be in the set and the won ones out of it, so a game with no drawn part at all has its one stable set fixed by the labels. That is the case the definition began with, a game that must end, and its one stable set is the lost positions.

This gives an exact statement of what a turn does to the three kinds of graph met so far. On a game that must end, the turn changes nothing, because the set was already unique. On a game with even cycles only, the turn doubles a choice that already existed. On a game with an odd cycle, it replaces an impossibility with a free choice. The third case is the only one in which anything is gained, and what is gained there is nothing a player could use.

The formula, doubled #

The cleanest demonstration uses Chvátal’s own construction. Take the one formula on three variables that has no satisfying assignment, the one with all eight clauses. Its graph has no stable set, by an exhaustive search that takes very few steps. Now do to it what any game does, and write the player to move into every position.

The doubled graph has no odd cycles, because no graph of this kind can. It has 72 stable sets, including the two given by the turn. Exactly what the original graph was encoding has disappeared. A triangle that was a clause’s demand for a true literal is now a hexagon that makes no demand, and any assignment at all, or none, will do. The reduction depended on the graph being one in which a move does not change the mover. There is a useful way of saying this: the hard instances are games in which both players are the same player, moving on one token with no record of whose move it is. So the NP-completeness result of 1973 is a true statement about digraphs and only a loose statement about games, and the word “game” in the title of the earlier essay needs that reading.

The result does apply to a real class of games, namely impartial ones, where the position does not have to say whose turn it is because both players have the same moves. An impartial game with loops can have odd cycles in its position graph, and its stable sets are real choices, since a position’s status does not depend on who is to move. That class is a small part of what is played, and there the question remains open in the sense that nothing here says how hard its real examples are. Nothing has been shown about whether any natural impartial loopy game realises the hard case.

There is a pleasant symmetry with the way bipartite graphs behave elsewhere in this subject. The marriage graphs of Gale and Shapley have stable sets despite plenty of odd cycles, for a structural reason. Turn-based graphs have them because they have no odd cycles at all. Each is a family that escapes the theorem, and the two escape for opposite reasons.

The convention underneath #

A position here is a board together with the player to move, and that is what makes the graph bipartite. Any game whose moves always hand the turn to the other player is covered. A game with a pass still counts, if a pass is a move that changes the mover, and a game with extra turns does not, since a move that keeps the mover breaks the two-class structure. Games of that kind can have odd cycles, and this essay says nothing about them.

The drawn part is the set of positions labelled neither won nor lost by retrograde analysis, with moves between them. A drawn position always has a move to another drawn position, because a position with no such move would have been labelled. That fact is what the given sets rely on, and it is true of every finite game graph. The Three Men’s Morris graph assumes three counters each, placed alternately and then slid along marked lines by one step, with a completed line of three ending the game at once. The rules of the game vary from place to place and some versions forbid the centre as a first placement, which would change these numbers. The Mū tōrere graph uses the traditional restriction on moves to the centre.

What the two games cannot show #

That a stable set is useless. The set given by the turn certifies nothing, and that is all that has been shown. The other sets the search meets in Mū tōrere may well say something, and nothing here tests them.

That real games are easy. Finding the labels is what costs in a real game, and for chess or Go the table cannot be made at all. The result concerns what comes after the labels, and it says that the extra question of a stable set adds nothing to what they already cost.

Anything about whether a player could use this. A player who knows which positions are drawn can already hold a draw. Nobody at a board was ever going to compute a stable set instead.

That no hard version of this question exists for games. Require something more of the set and the turn may no longer supply it. For example, one might ask for a stable set that treats the two players alike, or for the largest stable set rather than any stable set, and each of those is a different question that this argument does not reach. The first of them is taken up at once.

Still open: a set that treats both players the same #

The given sets exist because a position knows whose turn it is. They work precisely by treating the two players differently. A player reading a board does not usually do that. Most of what a good player knows is stated from the mover’s side: mine and theirs, not black and white. So the natural question is what happens if the rule has to be colour-blind, the same rule for whichever player is using it. In that case the argument above is no longer available, since positions that differ only by an exchange of colours and turn have been declared to be one position, and a graph in which turns are forgotten can have odd cycles again. Whether such a rule exists on a real game then has to be measured.