Combinatorial Game Theory
who wins, and by how much
Series

Toads and Frogs — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks.

    Toads and Frogs

    Toads shuffle right, frogs shuffle left, and either may jump over one of the other. A strip six cells long is worth exactly up. Another six-cell strip is worth exactly down. Nobody has a formula for which.

    part 1 · positions
  2. Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks.

    The strip nobody has a formula for

    Some toads, a gap, some frogs. Two counts and a spacing is the whole description, and the values that come out of it are integers, stars, switches with eighth-point options and a down — four classes inside one two-parameter family, which is why nobody has written the formula.

    part 2 · positions
  3. The same strips, with no jumping. Elephants and Rhinos: toads move right and frogs move left, one square into an empty one, and nothing may hop over anything. The pieces keep their order for ever, and the values are computed by the same recursion as the game with the jump in it.

    The same strip without the jump

    Delete one clause from Toads and Frogs — the hop over an opponent — and the game is Elephants and Rhinos. Over the same 3,279 strips the values do not become simpler in the way a reader would guess: every value that is a number becomes an integer, against 172 fractions with the jump in, and the count of positions worth fighting over nearly doubles. Removing a move made the game hotter.

    part 3 · positions
  4. Every strip, without the hop. Toads and Frogs with the jump deleted, over every strip up to eight squares. The fourth column is the argument: whenever the value is a number it is a whole number, without exception, so the fractions the ordinary game produces are made by the hop and by nothing else.

    The strip where every number is a whole one

    Delete the hop from Toads and Frogs and the halves, quarters and ups vanish completely: over 9,801 strips, every value that is a number is an integer, without a single exception. The guess that the hopless game therefore has a formula reading the gaps is half right and exactly wrong — 1,460 strips of eight squares are switches, and three strips with the same counts of toads, frogs and empty squares are worth 1, {2 | 1} and 2.

    part 4 · positions
  5. Five kinds of empty square. Every empty square in a hopless Toads and Frogs strip falls into one of five kinds, and the value follows from which. Three of them are free moves for one player or the other, one of them is where a position stops being a number, and one is a wall that splits the strip into independent pieces.

    The square that cannot be halved

    Every number in hopless Toads and Frogs is a whole number, which the rung below measured on seven thousand strips and could not explain. The reason is that every empty square is either one player's alone or split evenly between them — except one, and that one is where the numbers stop.

    part 5 · positions

All series