Combinatorial Game Theory
who wins, and by how much
Concept

Repetition rule — where it appears

A rule that stops a game when play comes back on itself. It can count repeated sequences of moves, as the German chess rule of 1929 did, or repeated positions, as the modern rules do, and what it counts decides whether it ends every game and whether it can change who wins.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

How the word is made. The Prouhet–Thue–Morse word built by doubling. Each row of one, two, four up to thirty-two letters is the row above followed by its swap, which is the same word obtained by replacing A with AB and B with BA.

A rule that let the game run for ever

In 1929 German chess drew a game when the same sequence of moves came three times running, and the rule was meant to make chess finite. Max Euwe, six years from the world title and trained as a mathematician, showed that it does not, using a word that had already been found twice for other reasons. Two round trips are enough. The board returns to one position thousands of times, no block of play ever comes three times running, and the rule has nothing to say.

history · Repetition How strict a repetition rule can be before it ends every game. For two, three and four available moves, the longest legal game under each repetition exponent from 7/5 to 3. Two moves stop at three letters at exponent two and never stop above it; three moves stop at 38 letters at 7/4; four moves stop at 121 letters at 7/5.

How strict a rule can be

A repetition rule can be tightened one notch at a time, and each notch either leaves unending games alive or kills them outright. With two moves a block may not come twice, and every game is over by the fourth letter; relax that by a single letter of overlap and unending games appear. Three moves stop dead at 38 letters under a rule that a whisker's relaxation frees. Four stop at 121. Past each boundary the words go on for ever, and the boundary sits at a fraction nobody would have guessed.

history · Repetition The repeater's plan on two moves. Every line of play in which the repeater forces the rule of 1929 on two moves, 4 lines of at most 7 letters, each ending in a block three times running.

The opponent makes it repeat

Euwe's unending game needs both players to keep to it. Give the letters to two players in turn, with one of them wanting the draw that a repetition brings, and the rule of 1929 fires within seven letters on a plan of one sentence: always play A. The word that defeats the rule exists and nobody can be held to it. Add a third round trip and the same player can no longer force anything in twenty-six letters. Existence and force turn out to be separate questions, with separate boundaries.

history · Repetition A draw by repetition changes no result. Over all labelled games on three and four positions and a sample on five, the result from each start with a draw on the second or third arrival at a position, compared with retrograde labelling of the graph. They agree everywhere.

What counting positions buys

A rule that counts arrivals at a position ends every game, which the rule of 1929 could not do, and it needs no proof beyond arithmetic: with L arrivals barred on n positions, no game is longer than (L − 1)n − 1 moves. What it does not do is change a single result. Over every game on three and four positions and a sample on five, drawing on the second arrival or the third gives exactly the labels retrograde analysis had before any rule was written. The rule pays for the game's ending and for nothing else.

history · Repetition Refusing a repeat resolves every draw. All games on three and four positions and a sample on five. When the second arrival at a position is refused, every won start stays won and every lost start stays lost, and every drawn start becomes a win or a loss.

The number in the rule

Draw on a repeated position and no result moves. Refuse the move instead, as Go does, and nothing is left drawn: over every game on four positions, 10,324 of 16,384 starts are drawn with no rule and every one of them acquires a winner. Which winner depends on the number written into the rule. Bar the third arrival rather than the second and 1,392 of those starts change hands. A question with a linear answer has become one that needs the history, and the extra difficulty lies entirely in the positions the labelling called drawn.

complexity · Repetition

Named alongside it

The objects these essays reach for when they reach for this one.

DrawEnding conditionExhaustive searchLoopyThue morse wordProofRetrograde analysisComplexityIntractableStrategy

All concepts