What counting positions buys

The rule of 1929 failed because it watched the moves. A game can avoid repeating its moves for ever while the board comes back to the same position every few turns, and a rule stated on the sequence of play cannot see that. So the obvious repair is to state the rule about the board. Count how many times each position has occurred and stop the game when a count reaches some limit. That is what chess does now, in the form every club player knows as threefold repetition, and it is what Go does in the form called positional superko, with a different consequence attached.

A rule of this kind can be judged on three separate things: whether it ends every game, whether it changes who wins, and what it costs to apply. The answers are short and they come from different parts of the subject. The first is arithmetic. The second is an observation about retrograde analysis that is easy to overlook, and it needs checking precisely because the reason for it is so brief. The third is where the history of a game turns out to weigh heavily, and it is what the next argument is about.

The comparison with the old rule gives the question its point. Under the rule on sequences, a player’s choices could prolong the game without limit. Under a rule on positions, the game is on a finite graph where each vertex can be used only so often. Is that merely a tidier way of stopping, or does it alter the game that was being stopped?

The rule ends every game, by counting #

Suppose a game has n positions and the rule stops play at the L-th arrival at any of them. No position can be occupied more than L − 1 times, so a game holds at most (L − 1)n occupied positions, and that many positions are joined by one fewer moves. There is nothing more to the proof. It uses no property of the moves, of chess, or of the players.

On a complete graph, where any move order is available, the bound is reached exactly: the search returns 5 moves on six positions with the second arrival barred, 9 on five with the third, and 11 on four with the fourth. A real game graph has fewer moves and so usually falls short. Nothing about that changes the conclusion, since the bound is what is needed for Zermelo-style arguments to get started: the game is finite, so induction on what remains can go through.

The last column of the figure is where the change of subject shows up. The rule of 1929 has no number to enter there, however many positions there are. It needs only one position and two ways of leaving it. Going from “no bound” to “(L − 1)n − 1” is the whole improvement, and all that was required was to change what is being counted. The number is enormous on a real chessboard, since n is the number of chess positions, and nobody would mistake it for a practical limit. Chess therefore carries a separate rule about irreversible moves, the fifty-move rule, and that rule has its own history of surprises. As a matter of logic, though, the position count suffices by itself, and a bound of any size is a bound.

It does not change who wins #

Here is the part that seems as though it should need an argument, and to which the census gives a surprising clean verdict. Take a game on a small graph. A player with no move loses. A player whose move brings the game to a position’s second arrival, or third, ends the game as a draw. Search the whole of what follows from every start, with the visit counts as part of the state, and compare with what plain retrograde labelling gives on the same graph with no rule at all.

The rule moves nothing. Over all 16,384 starts on four positions, at second arrival and at third, and over 20,405 sampled starts on five, every won position stays won, every lost position stays lost and every drawn position stays drawn. The labelling knew nothing about repetition. It worked on a graph with cycles and said “drawn” about whatever it could not resolve, and that word carries no value, only a report that the rounds of the calculation had stopped. So the rule of repetition, added on top by a committee for reasons of convenience, reproduces what the labelling already said, down to the last position.

The reason is short enough to read off a picture.

Look at a won position first. Retrograde labelling assigns it in some round, and the label records that there is a move to a position lost in an earlier round, from which every move goes to a position won in a still earlier one. So following the labels, the winner’s distance from the end strictly falls with every pair of moves, whatever the opponent does. A strictly falling number cannot return to a value it has had. So a winner who plays that way never arrives anywhere twice and the rule never gets a chance to intervene. The loser has no way of making that number go back up, because every move from a lost position lands on a position already won in an earlier round. The repetition rule can only ever fire on a line that the winner has declined to follow.

Then a drawn position. By the definition of the labelling it is not lost, so not every move leads to a won position, and some move leads to a drawn or lost one. It is not won, so no move leads to a lost one. Therefore some move leads to a drawn position, and whoever is at a drawn position can stay among drawn positions indefinitely. Both players can do this. Under the rule, staying in the drawn part ends with a repetition, and therefore with the draw it was going to be anyway.

So neither side can gain from the rule, and neither can lose by it, as long as they follow the labels. This is also why the word that defeated the older rule has no effect here. On the two round trips every position is drawn, the rule stops the game on the second or third return to P, and a draw is what the labelling said it was from the first move. Euwe’s game and a game stopped at once have the same value. All that differs is whether anybody gets to go home. What the rule buys is exactly the thing it was written for, and it costs no result. In a subject full of hypotheses that have to be checked, this one is simple enough to hold in the head, and it holds even in the sample at five positions without exception.

It also explains an odd feature of the way draws work in practice. A fortress is a drawn position in a game where the defender just shuffles, and a player can look at one and know that it is a draw without counting anything. Whether the arbiter eventually applies threefold repetition or the fifty-move rule makes no difference to what the fortress is worth. The label is the theoretical object, and the rule is the procedure that makes the game actually finish.

The contrast with the older rule is worth having in one place, because it shows what is and is not gained. Under the rule of 1929 the first row ended quickly and the last never ended. Under a rule on positions the rows are all the same, since the only number that matters is the arrivals at P and each letter adds one. So everything Thue and Euwe found about varied play, which is a large and beautiful subject, has simply become irrelevant to the game. The variety of letters is real but the rule no longer reads it. This is the sense in which the repair works. It does not out-argue the word, and it makes the word beside the point.

An old game under the rule #

A census over graphs of four positions is one kind of evidence. It helps to look at a game somebody actually played, where the graph was not chosen by the person checking it. Mū tōrere is the right size, and it has draws in abundance.

Labelling reads those 2,160 arcs and finishes: 240 positions won, 128 lost and 892 drawn, which is roughly seven in ten. By the argument above, every version of the rule gives the same result, so that the game is a draw from the opening with correct play at any count. What the count does change is how the game goes in practice, and random players make the point sharply. With the second arrival drawing, more than half of two thousand games end by the rule, at a median of fifteen moves. With the fifth arrival drawing, the rule ends fewer than one game in twenty, because a player choosing at random finds one of the 128 lost positions long before anything has come back five times. A stricter count rescues a careless player from the carelessness. That is a real effect, and it has no theoretical expression, because the theory assumes that the labels are being followed.

The figures should be read the right way round. They do not show that the rule of a given count is better for anyone who knows the game. A player who knows Mū tōrere keeps out of the lost positions, and then the game is a long shuffle among drawn ones and the count merely says how long. They do show how much of a real game’s experience the count can affect without altering its value at all. So any account of why a particular number was chosen for a rule has to be an account of that experience.

What the rule looks like in use #

The two versions on a chessboard are different kinds of thing, and it is worth setting them next to the older rule and next to Go.

Current FIDE rules separate two things that the argument above treats as one. A player may claim a draw when a position is about to occur or has occurred for the third time. Since 2014, the fifth occurrence ends the game automatically, without a claim. The difference matters logically. A rule that depends on a claim does not by itself make the game finite, since a game can continue past any number of repetitions if neither player cares to claim. The fivefold version is the one that actually gives the bound in the first figure. Together with the seventy-five move rule added at the same time, it is what makes chess under FIDE’s rules formally finite. The theoretical bound was therefore always available and was not written down as an automatic rule until well after anyone needed it for an argument about the game.

Go’s two rules appear at the bottom of the same table. Basic ko prohibits only the immediate recapture, and in that sense it is much closer in spirit to the rule of 1929: it watches a very short sequence, and longer cycles are outside its view, which is precisely why it allows the triple-ko cases for which games have been abandoned. Positional superko counts positions, with a limit of one: no earlier whole-board position may come back. It is a rule of exactly the shape discussed here, except for what happens when it applies. In Go the move is refused rather than the game being drawn, and that one difference is what the next essay is about, because it turns out to be much more serious than it looks.

What the history costs #

The rule is cheap to state and expensive to include. A position, for the purposes of a search that has to respect the rule, has to carry how often each position has occurred.

This figure counts every state that can be reached from a single start, on a complete graph, with no pruning, because those states are what a full table would have to hold. Labelling needs one entry per position and reads 90 arcs at ten positions. With the second arrival barred the same graph has 2,305 reachable states, which is roughly the number of subsets of positions a game could have used, multiplied by where it can stand. With the third barred it is much larger still, already 6,513 at seven positions, where labelling reads 42 arcs. So a program that wanted the rule built into its search would be solving a much harder problem than the labelling solves, and it would get the same answer.

That is the practical moral. Since the rule changes no result, a program answering who wins should not search the history at all: it should label the graph and report that. This is why endgame tables are computed on positions, with no reference to how they arose, and why a table’s entries remain correct under whatever repetition rule the players are using. The history enters only for a player in the actual game who is trying to claim or avoid a draw, or a program playing a game in progress, for which a table may give a move that walks into a repetition that the rule would have made a draw, and that is a matter of practice rather than theory.

The fifty-move rule is a different case and it does change results, as a counter on the position that makes distance to the end into part of the position. Winning positions in long endings become draws because the win takes too long, and the labelling on positions alone gives the wrong answer for those. The distinction is exactly this. A rule that fires only on a repeat does not touch a winning line, since the winning line never repeats. A rule that fires on the passage of time can touch one, since a winning line certainly takes time. So the argument above is specific to rules about repetition, and it does not generalise to every rule that a committee might use to stop a game.

The convention underneath #

Arrivals are counted from the start, and the start itself counts as the first occurrence of its position. A position here is the vertex of the graph, with whose turn it is built in, because in a game with a fixed graph of this kind the mover has been absorbed into the position’s identity. On a real board, repetition is defined to include the side to move, castling rights and the capture of a pawn in passing, because those change what can happen next. The definition has been refined more than once for exactly that reason, and a position that looks the same and has different rights is a different position.

The results assume that the rule fires at the arrival itself. A variant in which the player must claim on the move before, or at the next turn, does not affect the argument, since a player who wants the draw has it available either way. The census is complete on three and four positions and is a sample on five, of every 257th game in the numbering, so the claim at five is what the short proof says and the sample merely confirms it. The proof is the authority, and the checks are there because a short argument of this kind can quietly miss something.

What the census cannot show #

That the two rules are equal in practice. Result is not the only thing a rule affects. A game’s length under the rule, how soon a player can force the draw, and whether the winner must take care to avoid a repetition all depend on which arrival fires it, while the theoretical result does not.

That players can apply the labels. A chess player does not know which positions are drawn, and the argument gives a reason for that to be irrelevant to the rule rather than a method for finding them. A player who thinks a position is won and plays into a repetition has made a misjudgement and the rule will cheerfully end the game.

Anything about the size of a real position graph. The census runs over graphs of a few positions, and the theorem covers any finite graph. What does not scale is the state count. Nothing here measures a real game’s position graph under the rule, and for chess no such measurement is possible.

What the rule does to a game with chance or hidden information. Those games are outside the labelling altogether, and repetition there is a different kind of question.

Still open: when repeating is refused rather than drawn #

The whole of this result depends on what happens at the arrival, and that was a choice. Suppose the repeat is not a draw. Suppose it is simply not allowed, as in Go, so that a player with no other move has lost. The winning line still never repeats, so the winner is unaffected, and the first half of the argument stands. The second half does not, because a player holding a draw by staying among drawn positions is now going to run out of positions. Every drawn position has to go somewhere, and the rule says nothing about where. What happens to the draws under that rule is a complete reversal, and the answer depends on a number that the labelling has never heard of.