Toads and Frogs — where it appears
Named by 18 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
Infinitesimals
Some positions are positive — Left wins them whoever moves first — and smaller than every positive number, including a millionth and a millionth of that. They are the values that decide close games, and the smallest of them is a single move's worth of nothing.
A position reached eleven ways is one position
A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.
The class where nobody runs out first
Three stones in a row — blue, blue, red — and the position is worth exactly up. Clobber cannot produce anything else, because adjacency is symmetric — a player has a move precisely when the opponent does, and a game with that shape can never be worth a whole move to anybody.
The class is named after memory, and that is not an accident
A 4×4 Domineering board has 6,257,129 routes through it, 5,700 distinct positions, and a deepest line eight moves long. Those three numbers are three different resources, and the smallest of them is the one that gives games their complexity class.
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.
Knowing who wins, and knowing what it is worth
Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.
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.
The values nobody's game produces
The construction hands down 1,474 values by day three. Seventeen rulesets on this site, swept to eleven thousand positions, produce 1,193 — and only 116 of those are on the construction's list. Two of the twenty-two values born by day two are produced by no position of any game here, and 1,077 of the values that are produced are born later than day three. A value's birthday and a value's reachability have almost nothing to do with each other.
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.
Nobody comes back
There is a class of games in which running out of moves is permanent, and it is the setting almost every modern misère result is stated in. Nine of this site's eleven rulesets belong to it across 5,334 positions; the two that do not are Toads and Frogs and Amazons, and Toads and Frogs loses the property to a single clause — delete the hop and it joins the list.
The strategy that is a symmetry
A pairing strategy is a symmetry of the board that turns one player's moves into the other's, and it wins without computing anything. Tested by playing it out rather than argued, it wins one of seven candidate symmetries across four games — exactly the Cram boards with both sides even, which is exactly where no domino is its own image.
The entry fee was the cap
Two rungs measured how much bigger a position has to be than the value it exhibits, and attributed what was left to the ruleset — Toads and Frogs paying 2.25 squares on everything, green Hackenbush paying nothing. Neither number is a property of the rules. Inside every ruleset the excess falls as the birthday rises, because the sweep's size cap censors exactly the values that would pay most — and three squares past the cap, Toads and Frogs exhibits values born later than the strip is long.
The rate was the alphabet
The rung below asked for a quantity a size cap cannot censor and proposed the rate: how many new values a ruleset produces per extra square. The rate is honest and it measures the notation — every ruleset grows at close to the number of symbols its positions are written in, and the seven span less than a factor of two. What separates them is the yield, which spans a hundred and nineteen.
The clause that turns the class off
Three rungs failed to find the dead-ending class doing measurable work, and each time the population was blamed. Toads and Frogs with and without the jump is the matched pair the anchor wanted — the same board with the class switched on and off — and on it the test the class licenses gains less from the class than a control that has never heard of it.
A quotient that identifies nothing
The dead-ending class is famous for quotients rather than comparisons, so the matched pair was asked the question its own subject is about. Neither quotient identifies a single pair of positions, and both are separated by exactly five addends — because a quotient is small when its universe is poor, which is a choice of company and not a property of a class.
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.
Eleven moves and one decision
A prefix has one quantifier a turn, so a game of eleven moves is eleven alternations. Counted on the boards themselves, a Toads and Frogs strip of eleven moves has twenty-six turns with exactly one move available and one turn anywhere at which the choice changes the answer; a Clobber board has a hundred and fourteen turns and none. Nim, the game everybody calls solved, decides at four turns in five.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchDomineeringPartizanCanonical formClobberEnumerationInfinitesimalOutcome classHackenbushStar (∗)SwitchComplexity