Some games of chess come regrettably to an irresolvable impasse. Imagine a game, for example, in which all the pieces have been captured except the two kings, who wander the board like two King Lears on the barren heath. There will never be any checkmate.
The players lack mating material—it is impossible to set up a checkmate position on the board using these pieces. Other piece combinations also lack mating material, such as king and knight or king and bishop.
Even when players have mating material, optimal play may nevertheless proceed in an infinite repeating pattern. Consider the case here of perpetual check—White has just played 1.Qa5+, checking the black king.
Black is forced to retreat with 1..Kb8, moving to the back rank. White checks again with 2.Qd8+, forcing the Black king back to the original square, 2..Ka7. And then White checks again on the original square with 3.Qa5+, returning the whole position to where we started. Thus the white queen checks repeatedly on a5 and d8, forcing the black king to oscillate between a7 and b8. White can aim at this pattern of perpetual check, hopelessly but persistently checking the Black king, who must respond forthwith every time. Meanwhile, White cannot afford to stop the checks, you see, since Black threatens mate at Qb2# and holds otherwise an insurmountable lead. (But watch out, if 1.Qc3, do not take 1..Qxc3??, since this is stalemate; instead there is mate in 3 via 1..Qh7+.) So White is happy to continue the game with endless checks, since otherwise it will be a loss.
The historical rule on 3-fold repetition
To resolve these endless games, chess had adopted various rules on repetition. Historically there was variation in the exact number of repetitions required, but by early twentieth century chess had largely settled on what I shall refer to as the historical rule on 3-fold repetition, namely, if players repeat the same sequence of moves (having the same successive piece positions on the board) three times in succession, then the game may be called a draw. According to this rule, the perpetual check example becomes resolved as drawn upon the third repetition of the pattern. Kindly notice that this historical version of the rule is about repeating sequences of moves three times, rather than repeating a given position of the game three times, as in our contemporary rule on 3-fold repetition. The actual position will actually be repeated four times at the conclusion of the three cycles of repeated moves, an instance of the fencepost error phenomenon, by which a fence with 3 rails has 4 posts, similar to how a two-night hotel stay from June 12–14 involves three days: June 12, 13, and 14.
To my way of thinking, the 3-fold repetition rule is mainly to be conceived of as a natural proxy for what I regard as the more fundamental underlying rule, which is: infinite play is a draw. I think similarly about the 50-move rule, commonly used in chess competition, according to which 50 moves in succession without a capture or pawn movement makes the game is a draw. But of course, any rule about infinite play is hopelessly impractical, since we shall never achieve infinite play on the board, so these proxy versions of that rule are implemented in its place as a practical measure.
The perpetual check example above was a repeating pattern of the form: queen checks on a5, king moves to back rank b8, queen checks on d8, king moves to a7, and then repeating. So the pattern of movement is ABCD ABCD ABCD, and so forth, and the draw is called by the historical rule on repetition upon the third repetition of this pattern. Meanwhile, one can also find positions involving a longer sequence of repeating moves.
The contemporary rule on 3-fold repetition
The contemporary rule on 3-fold repetition, as I alluded, is not exactly the same as the historical rule. Rather, our current rule is that when a game position occurs three times, then the game is drawn. There is no requirement that the intervening sequence of moves is the same in the two intervals between the repeated occurrences of the position.
What exactly does it mean to repeat a position in chess? What exactly is a chess “position”?
Think about it…
On the game-tree conception of game positions, we identify the game positions with the nodes of the game tree. These never repeat during game play, since the game play proceeds in the game tree always to deeper and deeper nodes—one never repeats a node of the game tree during play.
For the purpose of the repetition rule, therefore, the notion of a chess position is somewhat looser than the game-tree conception. Of course, at the very least a position should specify the detailed arrangement of pieces on the chessboard, and it should specify whose turn it is to play, whether White or Black. But not only this, for one should also specify the castling rights for each player, whether they can castle kingside or queenside, as well as the en passant rights, if any.
In summary, for the purpose of the current 3-fold repetition rule, to repeat a position in chess means to repeat the state of pieces on the chessboard, like a snapshot, with also it being the same player’s turn, and with each player having the same castling and en passant rights as earlier. Upon the third occurrence of such a state of affairs, the game is drawn. This notion is the same as the concept of rich-enough board position used in the discussion of the tactical variation of the fundamental theorem for chess.
Why did chess change the rule on 3-fold repetition? What was the reason for the change? Was it important to change from repeating the same sequence of moves three times to repeating the same position three times?
Think about it...
The possibility of infinite play without repetition
The answer is a subtle mathematical problem. To get into it slowly, let us consider the following simple position, with White to play.
It is a draw, because neither player will be able to get their king through the pawn gap at e4 and e5. Black currently holds the opposition of kings, since White must retreat with his king to d3, e3, or f3. Black can then penetrate with king to e5, but this is temporary, because White can remain on one of d3, e3, or f3, and so the Black king will have to withdraw to d6, e6, or f6, while White can reclaim e4. Thus, the two kings stand in each other’s way at the gate. The main point of the position is that it will be a draw, but there are choices to be made about how exactly the play will proceed. It doesn’t matter much when white retreats whether this is to d3, e3, or f3, and similarly with Black retreating to d6, e6, or f6. So we shall be able to make complicated intricate patterns of combination. Will we have eventually be forced to repeat the same (possibly very long) sequence of moves three times in succession?
At bottom, the question is whether there could be an infinite sequence of chess moves, with the property that no finite pattern repeated three times in succession. Is it possible?
Think about it...
This is exactly the question that is answered by the Thue-Morse sequence, to which we now turn.
The Thue-Morse sequence
Let us now develop the mathematical theory of the Thue-Morse sequence, which begins like this:
a b b a b a a b b a a b a b b a b a a b a b b a a b b a b a a b b a a b a b b a a b b a · · ·
The Thue-Morse sequence, generated by any of several different but ultimately equivalent generation rules, exhibits remarkable features, which I should like to explore and explain in detail.
Among the surprising properties of the sequence is the fact that it is recurrent, which means any string appearing in the sequence appears infinitely often, indeed, appearing in any sufficiently large substring, and yet the sequence is not periodic. Indeed, it is cube-free, which means that there is no instance in which a finite sequence s occurs repeated three times sss. It has many squares, to be sure, such as aa, bb, abab, and others, instances of ss for arbitrarily long strings s. But there are no cubes, and the strings aaa, bbb, ababab, and so forth will never appear in it—no instance of sss for any string s.
The Thue-Morse sequence is one of those mathematical ideas that is so very natural and full of mathematical vitality and fecundity, that it is been discovered and rediscovered independently numerous times, by researchers in distant research areas. Evidently, Eugène Prouhet was the first, studying it in 1851 with applications in number theory; Axel Thue used it in 1906 in the combinatorics of string rewriting systems; Marston Morse applied it to differential geometry in 1921; Max Euwe rediscovered it in 1929 with his application to the 3-fold repetition rule in chess; Steven Brams and Alan Taylor rediscovered the sequence under the slogan “taking turns taking turns” in connection with their 1996 book on fair division; and so on in many other instances.
Let’s explore and discuss all these various aspects of this remarkable sequence. We shall have a full account of the sequence, as well as the fundamental change it had caused in the rules of chess.
We’ll discuss: the block recursion account, palindromes, anti-palindromes, the bitwise recursion account, the bit-count parity account, the string rewriting system, squares, cube-freeness, recurrence, self-similarity, application to chess, Thue-Morse in fair division, as a turn sequence, and finally, the transfinite Thue-Morse sequence.
