The number in the rule

A rule that draws on a repeated position turned out to be a rule that changes no result. It ends the game and leaves every label where retrograde analysis had put it, for a reason that takes two sentences: a winner never needs to come back, and a defender among drawn positions can stay there until the rule closes the game on them. That argument depends on what happens at the moment of arrival. There is a second family of rules that treats that moment differently, and it is the family that governs Go. A player may not make the move at all. If no other move is available, that player has lost.

The change looks minor. In both cases, the game cannot go through a certain position again, and the difference is only in the penalty attached. Yet the two rules have nothing in common after that. Draw on a repeat, and the theoretical result is the labelling, which takes time proportional to the arcs of the graph. Refuse the repeat, and the result ceases to be a function of the graph alone, draws vanish, and the question moves up the complexity scale to a very different class.

It is one of the cleanest places in the subject to watch one clause in a rule do a very large amount of work, and it can be checked over every small game there is.

Nothing decided moves, and nothing stays drawn #

Run the census again. Take every game on three and four positions, a sample on five, every start, and search under the rule that the second arrival at any position is illegal. A player with no legal move loses.

The table has two very firm columns and two that seem almost arbitrary. On four positions there are 3,076 won starts, all still won, and 2,984 lost starts, all still lost. That half of the old argument survives intact. A winner following the falling distance never repeats, so barring repeats takes nothing from the winner. And a loser gains nothing, because the winner’s line never depends on the loser’s being unable to repeat. That is true of any rule that only removes moves that repeat, and the census shows no exceptions.

Then come the draws. On four positions there are 10,324 of them, and under the rule 7,804 become wins for the player to move and 2,520 become losses. On three positions 39 and 48, so the balance between them even reverses, and on the sample at five positions it is 7,849 against 8,229. Nothing about these counts has a simple shape. Since every line of play now has to end, and ending means that someone is out of moves, every game has a winner, so a draw is impossible under the rule on any graph. The label “drawn” did not carry any information about what the position was worth, which is why it can be replaced by either result, and here the replacement has to be decided by actually playing through what can happen.

So the division between easy and hard falls on the same line as it did for stable sets. Decided positions are easy under this rule and can be read off the labelling, while everything difficult is in the part that the labelling calls drawn. Here that part is the majority of all starts, and there is no shortcut known for it.

The winner depends on the number #

The most striking thing about the rule is not that draws disappear, but what decides their replacement. Change the count from the second arrival to the third and read the same starts again.

On four positions, 1,392 of the 10,324 drawn starts change winner between the second-arrival rule and the third, about one in eight. On three positions it is 21 of 87. There is no plausible sense in which one of those numbers is the correct one for the game, because the graph is the same and only a parameter in the rule has moved. In the theory of the plain game the position is simply drawn, and any attempt to read one of these winners back as a fact about the position would be a mistake. The winner is a joint fact about the position and the rule.

The smallest cases are worth working through because the reason is visible in them. On any game where the moves simply go round a single cycle there is only one line of play, so the rule alone decides how long it is and hence who makes the last move.

The arithmetic is easy to state: with L arrivals barred on a cycle of c positions, the game has (L − 1)c − 1 moves and the first player wins when that is odd. On a cycle of even length, the first player wins for any L, since the product is always even and subtracting one makes it odd. On a cycle of odd length, the winner alternates with L. Those columns of the grid are not hard to explain, and they are worth looking at for what they do not contain, which is any information about the game. A cycle has no choices in it. The result of the rule on it is wholly a matter of counting how long the rule lets the play continue, then asking whether that number is odd.

That is the point about Go’s rule in its simplest form. A position in which two sides can only go round is a draw in the plain game, and it acquires a winner under a refusal rule. The winner is whoever happens to get the last legal move before the prohibition closes the cycle, which is a matter of who is ahead on threats in the real game, because those are what can be played outside the cycle to change its parity. A ko fight is a real instance of this. It is a drawn cycle, the rule refuses the immediate recapture, and the outcome depends on what else each side can play to get round the refusal. So the result of a ko depends on something outside the position, and that has been seen before from the side of the board. This is the same thing from the side of the rule.

What this does to the difficulty #

The labelling reads each arc once and is done. Under the refusal rule a position is no longer a vertex, because what is legal depends on which vertices have been used, so a position is a vertex together with the set of used vertices. With the second arrival barred, that game is exactly generalised geography in the form that uses up each vertex as play passes through it.

That identification settles the worst case. Thomas Schaefer showed generalised geography PSPACE-complete in 1978, by a reduction from quantified formulas, and two years later Lichtenstein and Sipser used it as the route to Go. It is the standard example of a game with that difficulty. So the rule that bars a second arrival takes a game whose result could be found in linear time and returns a game for which no polynomial method is known or expected, by changing the penalty at one moment. Nothing about the graph has changed, and the graph’s labelling is unaltered as an object. It has only stopped being what the question is about.

The formal results run further. Allowing a position to be revisited in some games and barring it in others is a real distinction in the complexity literature, and J. M. Robson’s work in the 1980s on games with a no-repeat condition showed that they can reach exponential space, well beyond the plain versions. That is the general territory that Go’s superko is in. The exact complexity of Go under superko is a finer question than these small graphs can address, and it should be stressed that an EXPSPACE result about games of that general form has not been shown to transfer to Go itself by anything here.

It is worth putting the three questions about one graph side by side, because each of them has now appeared. Whether a player wins, with repetition as a draw, is linear. Whether a stable set exists is NP-complete. Whether a player wins with repetition barred is PSPACE-complete. In all three cases the position graph is identical, and in each case the hard part sits inside the positions the labelling calls drawn. A drawn position is the place where a game’s easy question stops and its harder questions begin, and which harder question depends on what it is that somebody has decided to ask about it.

How often this matters #

One thing to read from the first figure is how large that drawn part is, and a wider measurement shows where it is heading.

On a random small graph the drawn part is not a corner. On three positions it is 45 per cent of starts, on four 63 per cent, and it keeps rising. Labelling needs a position with no moves in order to start at all, and a random graph has fewer of those the larger it gets. A game with few terminal positions has most of its positions drawn, and under the refusal rule all of those are decided by whatever the history makes of them.

A real game gives a sharper sense of what that costs. Mū tōrere, drawn as a plain graph, has 1,260 positions with a player to move and 2,160 arcs, and labelling reads each arc once and is done, with 892 positions drawn including the opening. Under the refusal rule the same question becomes who wins from the opening when no position may recur. A direct search with a table, allowed to remember three million states, had not settled it when it stopped. So the same 1,260-position graph that gives up its plain answer in a little over two thousand steps gives no answer at all after three million. That is one search and one cap, and a cleverer method may well do much better. It is nonetheless a real game and an actual count, and the size of the gap is roughly what the complexity results would lead anyone to expect.

Real games are of course not random graphs. Chess has a great many terminal positions and many irreversible moves that keep the graph close to acyclic, and Go’s captures are what create its cycles in the first place. For a game such as Mū tōrere, in which the great majority of positions are drawn, a refusal rule would convert nearly the whole game into something whose result depends on the count. Nobody plays it that way, and the fact gives some sense of why rules of the drawing kind are the more natural ones to reach for: they leave an old game’s theory intact.

So a choice between drawing and refusing is not simply a choice about how much to punish repetition. Go’s basic rule is of the refusal kind, and the obvious reason is that a draw would give the side that is behind an easy way out of every ko, while the game lives largely on the fights that the refusal creates. Chess’s rule is of the drawing kind, in a game where a draw is an ordinary result and where refusing a move would change what a fortress is. Each rule is suited to its game, and neither is a repair of the other. They are different decisions about what a cycle in the position graph should mean.

There is a small history lesson in this as well. The two families of rule have been treated as versions of the same idea, a way of stopping repetition, and any account that lists them together invites that reading. The earlier chess rule failed because it read the wrong object, and the repair changed the object it reads. The difference between drawing and refusing is a different axis altogether. It has nothing to do with what is read and everything to do with what is done about it, and it is the axis along which the difficulty of a game can change by the largest amount anybody knows how to measure. Rule-makers on either side had no way to see that, since the complexity classes were not defined for another several decades in the case of chess and for many centuries in the case of Go, and yet their games sit on opposite sides of the line.

The conventions underneath #

The second arrival is counted with the start as a first arrival, so a game cannot return to its starting position under the rule with limit two. A player with no legal move loses, which is the normal-play ending carried over. Positions on a graph contain whose turn it is by construction, whereas Go’s positional superko looks at the stones alone, so its rule is coarser than the one modelled here, and situational superko, which includes the side to move, is the nearer match. In that sense the graphs here model the situational rule. The two are genuinely different rules with different results on some boards, and the census does not distinguish them, since it has no notion of stones.

The rule’s count is applied to every position alike. A more realistic rule might apply only after some event or only to some positions, and each such restriction produces its own table. Every number in the first two tables comes from complete enumeration on three and four positions, and the five-position row is a sample of every 257th game. The proportions at five are therefore estimates, and the claim that nothing decided moves rests on the argument, with the census as a check on it.

What the census cannot show #

That the worst case is what happens. PSPACE-completeness is a claim about all graphs. These graphs have at most five positions, on which everything is trivially finite, and nothing here shows that any particular board is actually hard. It may well be that the graphs arising from real games are far easier than the worst case.

Why the counts come out as they do. The split between wins and losses among the drawn starts moves from favouring losses at three positions to favouring wins at four, then back to losses on the sample at five. No pattern can be read from three points with one of them a sample, and nothing here predicts the next.

That a cycle’s arithmetic explains a general graph. On a cycle there is one line of play and the count is everything. On a graph with choices, a player can choose which cycle to spend, and the parity is fought over rather than given. The flips in the second table come from that fight, and a reader should not take them to be parity arguments in disguise.

That Go’s result follows from these. Stones, captures and scoring all sit on top of what is measured here, and the graph of a Go position is not chosen from the same distribution as these. What carries over is the logic of refusing a repeat, and not any of the numbers.

Still open: what a real game does under each rule #

All of this was done on abstract graphs, chosen for completeness rather than for resemblance to anything played. The obvious place to go next is a very small Go board, with real stones, captures and scoring, solved under the drawing rule and under the two kinds of superko. That is harder than the board’s size suggests, and a direct attempt shows why. A board of two rows and two columns has only 57 positions that can arise, and a plain search with the history in its table still had not settled it after one and a half million steps, under any of the four combinations of superko and suicide rules tried. A row of five had not either. A row of four gives the same value of 4 wherever the search finished, and a row of three the same value of 3. So the disagreement between the rules, if there is one on a board this small, lies just beyond what the plain method reaches, and a proper treatment needs a search that handles histories more cleverly than by remembering them whole. The rule that made Go finite was chosen by people playing it, and whether the choice matters on a board small enough to check is a question with an exact answer, and a search that remembers whole histories does not reach it.