Combinatorial Game Theory
who wins, and by how much
Generator

How the word is made

How the word is made
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.

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.

5 essays call repeat-word. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.

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. How it was found

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.

 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 it was found

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.

 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. How it was found

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.

 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. How it was found

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.

 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. What it costs

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.

The whole library · The position index · The figures that play back