A rule that let the game run for ever

Zermelo’s paper of 1913 is remembered as the first theorem about chess, and it has a hypothesis that is easy to read past. It takes the game to be one in which a position can be reached and left, and it asks how long a winner needs, so it has to say something about play that goes round in circles. Its author knew that. A finite board with finitely many pieces has finitely many positions, but it does not follow that a game on that board has to end, because nothing in the moves of the pieces stops a rook going out and coming back. The ordinary answer is that a game which loops needs a rule to stop it, and a good deal of the theory of games rests on that rule actually doing its job.

In the 1920s the rule in German chess was stated about moves rather than about positions. A game was drawn if the same sequence of moves occurred three times in succession. That reads as a tidy way of catching the thing it is aimed at: two players shuffling back and forth, neither willing to try anything, repeating the same few moves. It catches that without trouble. What it was widely assumed to do beyond that is make the game finite, so that every game of chess must come to an end one way or another and arguments about the whole game can get started.

In 1929 Max Euwe published a short paper in the proceedings of the Dutch academy, Mengentheoretische Betrachtungen über das Schachspiel, set-theoretic considerations on chess. Euwe held a doctorate in mathematics from 1926, taught the subject in a girls’ school in Amsterdam, and would take the world championship from Alekhine in 1935. His paper showed that the rule does not make the game finite. There are games of chess that obey it for ever.

The method is what makes the paper worth reading a century later. It needs no chess at all beyond the existence of two different round trips, and the thing it uses is a sequence of two symbols with a remarkable property, one that had been written down before for reasons that had nothing to do with games and would be written down again.

Two round trips and a word #

Start with a position on a board where each side has something harmless to shuffle. Call it P. There are two ways for the players to leave P and come back to it: in one, each side makes one move out and one move home, using one pair of pieces; in the other they do the same with a different pair. Call the first round trip A and the second B. Each is four single moves, and after either the board is exactly as it was.

A game made of such trips is now a word in the letters A and B, and the rule becomes a statement about words. A game is drawn when a block of consecutive letters occurs three times running. AAA fires it, and so does ABABAB, and so does the much longer block AABAB coming three times in a row. Writing the game this way discards the individual moves, but nothing is lost by that. A sequence of moves that repeats three times has a corresponding block of letters repeating three times, as long as the repetition lines up with the trips, and if it does not line up the word has an overlap of the kind examined below.

So the question has become one that any reader can try on paper. Is there an unending word in two letters with no block three times running?

It takes only a few minutes of trying to find out that this is not as easy as it sounds. Written carelessly, a word runs into trouble almost at once.

Coin tosses do not avoid anything, so those games are not much of a test. A player who actually looks at the word and refuses a letter that would complete a repeat does better. Each letter is then chosen at random from the ones that keep the rule, and the game ends only when neither letter does. Run a thousand such games and the median one lasts 49 letters. One in ten gets past 138 and the longest, of the thousand, reaches 481. Every one of them eventually ends, stuck in a position where both letters complete a repeat, and this is striking: a player who has obeyed the rule at every step, with no plan and no ill intention, still ends up with nothing legal to play. Avoiding a repeat one letter at a time does not keep a game going for ever. A word that lasts has to be built by a plan.

The word #

Here is the plan. Begin with A. To extend, write down what is already there and then write it again with A and B exchanged.

The result begins ABBABAABBAABABBA, and it is known today by the names of three of the people who found it: Prouhet, who met it in 1851 in a question about dividing the integers into classes with equal sums of powers; Thue, who studied it for its own sake in papers of 1906 and 1912, in what was the first work in the subject now called combinatorics on words; and Morse, who came to it through geodesics on surfaces in 1921. Euwe found it again in 1929. As far as the record shows he did not know of Thue or Prouhet, and that is not surprising. Thue’s papers appeared in a Norwegian journal and went largely unread for decades. Morse himself, working with Hedlund, returned to the subject in 1944 in a paper called Unending chess, symbolic dynamics and a problem in semigroups, taking the chess application as part of its motivation and showing how much further the question goes.

The word has several equivalent descriptions and each is useful for something. It can be produced by the substitution that replaces every A with AB and every B with BA. Its letter in position i, counting from nought, is A or B according to whether i has an even or an odd number of ones in binary. And it is the limit of that doubling, so that an initial block of four or sixteen letters is a palindrome and one of two or eight letters is its own reverse with the letters exchanged. All of these are one object seen from three sides, and the second of them is the cheapest way to compute it: the parity of the binary digits is a loop of a few lines, and nothing about it depends on any earlier letter.

The claim it has to meet is that no block ever comes three times in a row, anywhere, however far along.

Why no block can come three times #

The proof is short, and it deserves to be seen because the reason is a pleasing one. Take the word and cut it into consecutive pairs, starting from the first letter. Every pair is either AB or BA, because that is what the substitution produces. Reading only the first letter of each pair returns the original word.

Two small facts follow from that picture. First, AA and BB can only sit across a boundary between pairs, since no pair holds two equal letters, and boundaries are two letters apart. So any two places where equal neighbours occur are an even distance apart. Second, AAA cannot occur, because any three consecutive letters contain a whole pair. From that, ABABA cannot occur either, because however it is cut, its pairs have names that spell AAA or BBB in the word. So any five consecutive letters hold equal neighbours somewhere.

Now take the claim slightly stronger than Euwe needed. Call a block followed by itself and then by its own first letter an overlap, and suppose the word contains one, with the block as short as any in the word. A block three times running contains an overlap, so ruling these out is enough.

If the block has length one, the overlap is AAA or BBB, which has just been excluded. If the block has an odd length of three or more, the overlap is at least seven letters long and has equal neighbours somewhere inside it. Then the same pair of equal letters occurs again one block-length along, which is an odd distance, and the first fact forbids it. If the block has an even length, the copies line up with the pairs in the same way. An overlap that starts in the middle of a pair can be pushed one letter to the left, since the second letter of a pair determines the first, and an overlap starting on a boundary reads off, through the pair names, as an overlap with a block half as long. That is shorter, against the choice of block.

No case survives, so no overlap exists anywhere in the word, at any length. A word with this property is called overlap-free, and Thue proved in 1912 that this one is, in effect, the only way to do it: every infinite overlap-free word on two letters is built from it.

A proof can be checked in the direction of its conclusion as well, by measuring how close the word ever gets.

The figure is more instructive than a yes or no. The word does repeat itself: AA occurs, ABAB occurs, BAABBAAB occurs. It repeats blocks twice, at lengths 1, 2, 3, 4, 6, 8, 12, 16, 24, and so on. That list is what a descent looks like from the outside. Every repeat of length 2b is the doubling of a repeat of length b, so all the squares in the word descend from the few very short ones at lengths one and three. The bars never go past two, and the gap above them does not shrink as the period grows. The word is not narrowly avoiding the third copy. It is built in such a way that a third copy has nowhere to come from.

This is the surprising connection the paper rests on. A question from the rules of chess is answered by a theorem about the arithmetic of binary digits, since the property that keeps the game going is ultimately a property of how parities of bit counts behave under doubling. Euwe saw the connection and Morse would see the same object as the path of a geodesic on a surface. They had no reason to expect it to be the same sequence.

What the rule cannot see #

It is worth pausing on how strange the resulting game is, because a repetition rule is usually read as a guarantee. A spectator watching would see the board go back to the same position, over and over, every four single moves, for as long as anyone cared to watch. Every other kind of repetition rule ever proposed would have stopped the game long before. A rule counting positions would stop it the third time P appeared, after two round trips.

That is why the rule was the wrong kind of rule, and it is what the example really teaches. The rule’s authors were thinking about what players do, a repeating pattern of behaviour. What makes a game loop is a property of the position graph, the fact that some position can be reached again. A word over two letters has a rich structure, with arbitrarily long stretches of play that do not repeat. A position graph with two cycles through one vertex has almost no structure, and on it the honest label for every position is a draw. The same game is both, and a rule stated on the first has no grip on the second. The modern rule counts positions, and what that buys can be stated exactly. Go arrived at a position rule by a different road, since its own prohibition was always written about the board.

The trade-off runs the other way too, and it would be a mistake to treat the 1929 version as simply a blunder. A rule about sequences of moves can be applied by looking at the scoresheet, with no reconstruction of positions. Spotting that the moves have run in a pattern is what an arbiter or an opponent actually does, and counting arrivals at a position needs the position to be recognised across different move orders. The rule was cheap for the same reason that it was weak.

How much room the rule leaves #

The word is one game, and it could have been an isolated freak. It is not. The rule leaves a great many games, growing fast with their length.

Since the word’s letters and length are all that matter, the count from a single position is exact: 2 words of length one, 4 of length two, 6 of length three because AAA and BBB have gone, then 10, 16, 24, 36 and on to 24,054 at length 24. The ratio between successive counts settles near 1.46. This is a different kind of result from Euwe’s. The Prouhet–Thue–Morse word shows that one unending game exists, while the count says that a player has real choice for as long as anyone likes to go, and that the legal games of a given length are exponentially many. Yet it does not follow from the count alone that there is an infinite word, since a tree can have enormous numbers of finite branches with each of them dying. It does follow from the word, and from the compactness argument that turns arbitrarily long words into an infinite one.

That compactness argument is itself a small lesson about games. If there are legal words of every length, then some first letter begins arbitrarily long ones, and among those some second letter, and so on, and the letters chosen form an infinite legal word. So the existence of an infinite game follows from a finite search failing to find a limit, provided the failure persists at every length. That proviso is the catch, because a finite search can never establish it, and a proof like the one above is what discharges it. Counting to 24 proves nothing about length 25. Knowing about the gap between two answers makes this distinction feel familiar: a question about all lengths needs an argument that holds at all lengths.

The conventions underneath #

A letter is taken to be a complete round trip by both players, so the board is back at P at the end of every letter. The rule in the real game counts single moves, and a repeat could in principle begin part-way through a round trip. That changes nothing, since the moves of A and of B are different moves. Even a fragment of a round trip says which letter it came from, so a run of moves repeating three times opens up into a run of letters repeating three times, with a little to spare at each end. The translation from letters to moves loses nothing.

The rule as stated is taken at face value, with a draw by repetition in the sense of moves in succession. The accounts of the 1929 rule available in secondary sources describe it this way, and the essay leaves aside how arbiters applied it. Euwe’s paper itself was also about more than repetition, considering the logical status of strategies in an intuitionist spirit, and this is the only part of it being described here.

Round trips are also assumed to be available. On a real board that is rarely in doubt, because it needs only two independent shuffles that neither side is obliged to stop, and it needs both players to go along with it. Nobody is compelled to play the word. Euwe’s result is about what the rule permits, and a player who wanted to break away from the word and try to win would be free to, if a winning try existed.

What this picture cannot show #

That anyone would play it. The game is a demonstration of what a rule allows. Nothing about it suggests that a player could be forced into it, or would choose it. Whether the rule can be made to bite on a player who does not cooperate is a separate question with a very different answer.

That chess itself is unending. The conclusion concerns the rules of 1929. The rules changed, and the game under the current rules has a bound, though it is not the kind of bound a player would notice.

That the word is the only one. The figure on growth shows otherwise for the plain rule. There are 24,054 legal games at 24 letters and the word is one of them, chosen because it can be proved to go on rather than because it is typical.

What the figure of letters says about the moves. A letter here stands for four moves by two pieces on each side, and two independent round trips were assumed rather than constructed. An actual position with this property is easy to construct on a real board, but the abstract version says nothing about whether a given position allows it, or for how long, once captures and pawn moves are considered, since either of those would be irreversible and would end the shuffle.

Still open: how much stricter the rule could have been #

Three times running was the rule, and the word beats it by holding each block to two. Tighten the rule to two times running and two letters collapse immediately, since no word of two letters can avoid that past length three: ABA is the longest, and each of its two possible next letters makes a square. Allow a third round trip and the room comes back. So the real shape of the question is a table with the number of available moves down one side and the strictness of the rule along the other, with a boundary somewhere in it. Thue found the first points of that boundary, and they turn out to have exact values on the two sides of which everything changes. Measuring where it falls is the next thing to do, and the numbers are stranger than the single fact Euwe needed.