Combinatorial Game Theory
who wins, and by how much
Generator

Recording the turn doubles an odd cycle

Recording the turn doubles an odd cycle
Recording the turn doubles an odd cycle. On the left a cycle of three positions, which has no stable set. On the right the same game with the player to move recorded in each position, a cycle of six, with two stable sets, each consisting of all the positions with one player to move.

On the left a cycle of three positions, which has no stable set. On the right the same game with the player to move recorded in each position, a cycle of six, with two stable sets, each consisting of all the positions with one player to move.

2 essays call drawn-part. 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.

Recording the turn doubles an odd cycle. On the left a cycle of three positions, which has no stable set. On the right the same game with the player to move recorded in each position, a cycle of six, with two stable sets, each consisting of all the positions with one player to move. How it was found

Taking turns removes the hard part

Whether a graph has a stable set is NP-complete, and every hard instance depends on odd cycles. A real game's position graph has none. A position records whose turn it is and every move changes that, so all cycles are even, Richardson's theorem applies, and the set of all drawn positions with one player to move is a stable set of the drawn part, always. Mū tōrere and Three Men's Morris both confirm it. The hard question never reaches a game with turns, and the sets it hands over carry no information at all.

 The one colour-blind stable set of Mū tōrere. All 33 classes of drawn position in Mū tōrere under rotation, reflection and colour exchange, each drawn as a small board from the viewpoint of the player to move, with the 16 classes of the unique stable set shaded. How it was found

A rule that cannot see whose turn it is

The stable sets a game hands over work by telling the players apart. Forbid that, and read every board as mine and theirs, and the odd cycles come straight back. On Mū tōrere, with rotations and reflections identified too, the 892 drawn positions fall into 33 kinds, and among those there is exactly one stable set. It names sixteen shapes. A player who always hands the opponent one of them holds the draw against labelled play without knowing a colour, an orientation or an outcome, and the opening itself is one of the sixteen.

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