The opponent makes it repeat

Every result so far about repetition rules has had the same shape: there exists a word. Euwe’s exists on two letters under the rule of 1929, Thue’s exists on three letters under a rule with no immediate repeats at all, and the table of thresholds says exactly which rules leave such a word alive. A theorem of that shape is a statement about a tree of possibilities, and it treats the two people at the board as one person writing down a sequence. Games are not played that way, and the difference matters here more than in most places, because the word has to be chosen one letter at a time by people who may want different things.

Consider what the rule of 1929 did for a player. A draw by repetition was a result, so a player in a worse position had every reason to want it, and a player in a better position had every reason to avoid it. Euwe showed that there are games that obey the rule for ever. Nothing in his paper, as far as the accounts of it go, says that a player who wants to keep the game going can actually do so. That is a different claim and it is about a different game. Two questions are worth separating, and they have quite different answers. One is what happens when one player wants the rule to fire, and the other is what happens when each player wants the other to be the one stuck for a legal move.

One player wants the draw #

Keep the model of the two round trips and give the letters to the players in turn. One of them, the repeater, wants the word to end in a block three times running. The other, the keeper, wants that never to happen. The rule fires whoever finishes the repeat. It does not matter who plays the letter that completes it, since the result is a draw and both are bound by it.

The first row of that table is the result that matters most, and it is an uncomfortable one for the unending game. Under the actual rule of 1929, on the actual board of two round trips, the repeater forces the draw by the seventh letter. The search that finds it, in both orders of play, visits thirty-nine positions. Thue’s unending word was not even a factor in the answer, because the keeper is never given the chance to play it.

The plan is so short that the whole of it fits on the page.

The repeater plays A, every time. That is the entire strategy. If the keeper ever answers with A, the word ends in AA, and the repeater’s next A finishes a block three times running. So the keeper must always answer B. But if the keeper always answers B, the word is ABABAB, which is the block AB three times running, and it is the keeper who finishes it. The keeper has two choices at each turn and each of them loses, one quickly and the other slowly.

The argument is worth a second look because of how little it uses. The repeater does not read the word and does not have to count anything. The keeper’s difficulty is that there are only two letters: the only way of avoiding one bad pattern is to play into the other. A word of Euwe’s kind avoids repeats by varying the letters in a pattern too subtle for any small block to catch, and it needs both players to agree to that pattern. As soon as one player keeps writing the same letter, half of the word is fixed, and the other half has nothing left to vary with.

This is a comment on the rule as well as on the word. A repetition rule has two jobs, which were not separated at the time: it should stop a game from going on for ever, and it should give a player who wants a draw a way of getting one. It fails the first of these as a matter of logic, by Euwe’s argument. It does well at the second, at least on a board that really has nothing else to do. A rule that a theorem proves inadequate can also be doing just what it was written for. The people who wrote it, watching what players actually did, may have had a better grip on its practical work than the theorem suggests, though the theorem is right about what the rule can guarantee.

What a third move changes #

Now change the number of round trips. With three, the same repeater playing A every time gets nowhere, because the keeper has two ways of answering that do not simply alternate, and can build a word from B and C around the A’s that never comes three times running. A search to twenty-six letters across more than eight million positions finds no forced repeat under the rule at three times running.

The second and third rows are worth comparing. On two moves with a ban on a block coming four times, the forced repeat takes seventeen letters, and at five times nothing is forced in twenty-six. So a rule can be loosened, or the number of moves can be raised, until the keeper is safe as far as the search goes. Both changes do the same thing, in giving the keeper room to vary what the repeater is trying to fix.

In the other direction the table has a strikingly flat line. Banning a block twice running, on any number of moves, the repeater needs at most three letters. There is no strategy to speak of here: on the keeper’s letter, the repeater simply copies it, which makes a block of one letter twice running. If the keeper starts, the repeater needs only that one reply. Eight moves or eighty make no difference. This is the case Thue’s theorem speaks to most strikingly: a three-letter word with no immediate repetition goes on for ever, and yet it can be destroyed by the most naive opponent imaginable, with one move, on any alphabet at all. Between “exists” and “can be held to” there is a gap of the entire infinite word.

That gap is the reason for caution in reading a row where the keeper appears safe. “No, to twenty-six letters” is a statement about a horizon. The keeper has not been shown to survive. This is where the argument stops, because a search has to stop somewhere, and a proof would have to supply an actual strategy for the keeper that works at every length. Nothing here supplies one.

Each player wants the other to run out #

The second question gives the rule a different role. Suppose no draw is available, and a player with no legal letter simply loses, the way a player with no legal move loses under normal play. Both players now want the word to continue exactly until the other is stuck. Neither wants to complete a repeat, and each hopes to steer the word into a place where the opponent’s every letter is illegal. The dead ends of the last essay are now the goal of the game.

The small cases have clean answers. Under a ban on a block twice running with two moves, the game lasts three letters and the first player makes the last of them. The same ban with three moves lasts seven letters, and the first player wins again. Banning everything past exponent two on two moves takes eight letters and the second player wins. And the rule of 1929 itself, with two moves, takes twenty-one letters and the first player wins.

The seven-letter case rewards being followed move by move, because it ends on exactly the trap identified earlier.

The first letter can be called A without loss, and the second has to differ from it, so it can be called B. Then the first player has a real choice, and the choice is to return to A. After ABA the second player cannot play A, which makes a square at once, and cannot play B, which makes ABAB. So the second player has to introduce C. After ABAC the first player plays A again. Now ABACA leaves two legal-looking letters, but C would make ACAC, so the second player is left with B alone. And ABACAB gives the first player the last A, after which every letter completes a square.

So the first player steered the word into the shortest dead end in the whole tree, and from the third letter on the second player had no decision at all. That the smallest possible trap is also reachable by force is not something that had to be true. The dead end is a statement about the words and the forcing line is a statement about the game, and on this rule the two happen to meet at the same seven letters.

The longest of the settled games is much less obvious.

On that line the first player, who is going to win, is almost never making a decision. The second player chooses A and then the first player is obliged to play B, because a third A is illegal, and this pattern runs on: the second player keeps doubling letters to take away the first player’s options. It looks like the second player is in control, and through most of the game every first-player letter is forced. The block AABB is two letters away from coming round for the third time when the second player finally has to break the pattern, and from there the first player has a choice of letters and uses it. Having all the choices does not mean being in control. On this line the player with the options is losing, and has been from the start.

That is an interesting reversal of the intuition about the repeater’s game, where the player making the same choice over and over was the one in command. The structure is the same in both, since each player’s letters rule out the other’s. What differs is whether completing a repeat is what a player wants or what a player must avoid.

How small a forced win is #

A forced win of twenty-one letters sounds as if it might need a huge amount of memorisation. It does not.

A plan needs one reply at each of the winner’s turns and every reply at the opponent’s, and because the opponent is usually short of options too, the tree stays narrow. The rule of 1929 has 12,314 words up to length 21 with the first letter fixed, and a player who knows 107 positions has the game solved. This ratio is typical of a strategy compared with the game it comes from, and here the reason is plain. Legal words are many only if both players cooperate in varying them, whereas under a plan one of the two players has stopped varying anything.

Taken together, the two games say the same thing from different sides.

Reading across a row is reading how much of the unending game survives each increase in opposition, and it shrinks at every step. Cooperative players never stop. A random pair of players last a few dozen letters. Players trying to strand each other finish in seven to twenty-one. A single player who wants the rule to fire needs three to seven. The Prouhet–Thue–Morse word lives at the far left of that table and nowhere else, and the rows differ only in how far it is possible to get to the right.

This changes how the 1929 result should be read. It is often repeated as the statement that chess could go on for ever under the old rule, and that is correct about what the rule permits. It would be wrong to take it as saying that a player could keep a game going against an opponent’s wishes on a board of this kind. On two shuffles, a player who wants a draw has one.

An unsettled game #

The last unsettled row is the one where search runs out first, and the reason is worth seeing.

Here the structure of the game explains the difficulty of the search. The shortest dead end on four moves is ABACABADABACABA, fifteen letters long, so no game can be over before then, and a search to fifteen or sixteen plies has only barely reached the first terminal position. Since the winner has to steer the word into a dead end, and four-move dead ends are rare, it is quite possible that nobody can force anything and the game is drawn by never ending. It is equally possible that a forcing line exists somewhere past the horizon. A separate run to twenty-two plies, at about 1.4 billion positions, found no winner either, and the multiplier suggests that each additional two plies costs nearly seven times as much as the last. Search by itself will not reach a far-off answer, and a real answer would need an argument about which words a player can be held away from.

The conventions underneath #

A letter is modelled here as chosen by whichever player’s turn it is, which is a simplification. In a real round trip both players move, and each has a say in how the trip goes. Letting one player name the whole trip gives that player more control than a chessboard would, so the forced lines above should be read as what a rule allows when a player has that control. On a real board a keeper also has every other legal move available. A pawn advance or a capture changes the position permanently and leaves the whole structure of round trips behind, and that is what a player actually trying to avoid a draw does. The result concerns the shuffling alone, and it shows that shuffling cannot save the keeper.

Whichever player finishes a repeat, the rule fires, as it would in chess, where a sequence of moves occurring three times concerns both players’ moves together. In the second game a repeat is simply illegal, and the player with no legal letter loses, which is the normal-play convention carried over and no part of any rule of chess. First letters are taken as A by the symmetry between letters. Search depths count letters, so the figure of seven means the rule has fired by the seventh letter in the worst case for the repeater.

What these searches cannot show #

That the keeper is safe where it says “no”. The rows that remain unsettled report a horizon, as the plateau in the three-letter count showed can be misleading. Twenty-six letters on two moves at five times running is well past anything that has happened so far, and that is not evidence of much.

That a real board behaves like this. The round trips here are independent and always available. A real position has a few shuffles for a while, and any of them may stop being available when something else on the board moves. How much of this analysis survives on a real position would need an actual game’s graph rather than a word, and no such graph is examined here.

What it means for the player who gets the draw. The forced repeat assumes that the draw is what one player wants. Whether a player should want it is a question about the whole of the rest of the position, which the model has discarded.

Still open: whether counting positions solves any of this #

All of this has concerned a rule about sequences of moves, in which a keeper with room to vary can avoid the rule for as long as the variation lasts. The rule that replaced it counts positions, and a position cannot be varied around. Two round trips bring the board back to the same place no matter which order they come in. That rule obviously ends the game, which is the first thing it buys, and it raises a sharper question: since the outcome labelling of a game was already defined without any rule at all, does a rule on repeated positions change who wins? The answer can be read off the graph, and it is simpler than anything in this essay.