Combinatorial Game Theory
who wins, and by how much
Particular games

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.
17 min read 7 figures Small things decideNot every game is a numberThe theory runs out

A strip of squares. Some hold toads, some frogs, some are empty. Left moves a toad one square right, into an empty square, or jumps it over exactly one frog into an empty square beyond. Right moves a frog one square left, or jumps it over one toad. Whoever cannot move loses.

The rules take a line. The values do not.

Toads and frogsToads 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.∗N∗N↑L↓Rblue toads move right · red frogs move leftevery value came out of the moves; none was chosen
Fig. 1 Four strips and their exact computed values. The third is worth up and the fourth down, which is not visible in the pictures and was found by evaluating every strip up to seven cells.

The smallest strips

T. — one toad with an empty square ahead. Left can move it; Right has nothing. Value 11.

.F — the mirror. Value −1-1.

T.. — Left can move the toad twice. Value 22.

TF. — the toad is blocked by a frog, and the square beyond is empty, so Left may jump. After the jump the frog has an empty square to its left, so Right may move. Working it out: value 00.

T.F — Left moves the toad into the gap; Right moves the frog into it. Either move leaves the other player stuck. So the position is {0∣0}\{0 \mid 0\}, which is ∗\ast — confused with zero, whoever moves wins.

That last one is the game’s first infinitesimal and it takes three squares.

Where up appears

Enumerating every strip of length three to seven and evaluating it produces 113 distinct values. Most have no name. Two of the named ones are the reason this game is worth studying.

T.TFF=↑TTF.F=↓\texttt{T.TFF} = \uparrow \qquad \texttt{TTF.F} = \downarrow

Both are five squares. Neither is symmetric, and neither is obviously different from strips worth something else entirely. T.TF is worth 12\tfrac12; T.FF is worth {0∣−12}\{0 \mid -\tfrac12\}; TT.F is worth {12∣0}\{\tfrac12 \mid 0\}.

So five-square strips of the same shape family carry a number, two different switches, and an infinitesimal, with nothing in the pictures to indicate which is which. That is the honest state of the game and it is why enumeration is the method.

Smaller than every positive number, and not zeroValues that sit between zero and every positive number. Up is genuinely greater than zero — Left wins it whoever moves — and genuinely less than a thousandth. Star is not comparable with zero at all. None of them is a number, and in a close game they are the entire margin.↑{0 | {0 | 0}}> 0< 1/1024outcome L⇑{0 | {{0 | 0}, 0 | 0}}> 0< 1/1024outcome L↑∗{{0 | 0}, 0 | 0}‖ 0< 1/1024outcome N∗{0 | 0}‖ 0< 1/1024outcome N↓{{0 | 0} | 0}< 0< 1/1024outcome Rvaluecanonical formagainst 0against a thousandth↑ is positive and smaller than every positive number — which no real number is∗ is none of greater, smaller or equal — the order is partial, and that is the point
Fig. 2 The values that a five-square strip can be worth. Up, down and star are all realised by Toads and Frogs positions, and so are ordinary fractions.

Why the infinitesimals appear

The mechanism is worth naming, because it explains where ↑\uparrow comes from in every game that has it.

↑\uparrow is {0∣∗}\{0 \mid \ast\}: Left can move to a position worth nothing, Right can only move to a position worth star. So Left’s move settles the position and Right’s leaves a tempo behind.

In T.TFF, that is exactly the structure. Left’s move fills the gap in a way that leaves the remaining pieces mutually blocked — a dead position, worth zero. Right’s move leaves one square that either player can still use, which is a star. The asymmetry between “settles it” and “leaves one move floating” is what an up is, and Toads and Frogs realises it because jumping and stepping interact to leave exactly one loose square.

Whenever a game has moves that block and moves that leave a single shared square, it will produce ups and downs. That is why they turn up in Go endgames, in Clobber, in Domineering fragments, and here.

The up strip, opened up

T.TFF is worth ↑\uparrow not by reduction but literally — the raw position, before any canonicalisation, has exactly one option each way, and they are 00 and ∗\ast.

Left’s only legal move: the leading toad steps into the gap, giving .TTFF. Now no toad has an empty square ahead and no toad has a frog-then-gap ahead; no frog has an empty square behind, and no frog has a toad-then-gap behind. Nobody can move. Value 00.

Right’s only legal move: the first frog has a toad immediately to its left and an empty square beyond, so it jumps, giving TFT.F. That position leaves exactly one square either player can still use — the leading toad can step into the gap, and the trailing frog can step into it too — so it is {0∣0}=∗\{0 \mid 0\} = \ast.

So the position is {0∣∗}\{0 \mid \ast\} written out, which is the definition of ↑\uparrow — no dominated options to strip, no reversible options to bypass. Five squares, two moves, and the canonical form of one of the subject’s two most-used values.

TTF.F is the exact mirror: Left’s only move jumps the second toad, giving T.FTF, worth ∗\ast; Right’s only move steps the last frog into the gap, giving TTFF., in which nobody can move, worth 00. So {∗∣0}=↓\{\ast \mid 0\} = \downarrow.

That both appear at five squares, in strips that differ by a rearrangement, is the whole appeal of the game. It manufactures the small values without any of the artifice that Hackenbush needs.

Toads and frogsToads 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.↑L↓Rblue toads move right · red frogs move leftevery value came out of the moves; none was chosen
Fig. 3 The two strips, side by side. One is worth up and one down, they use the same five squares and the same pieces, and nothing in the pictures distinguishes them but the arrangement.

The number strips

At the other end of the value set sit the strips that are worth plain integers, and they are worth understanding because they explain why the game is not all-small.

TTT... — three toads, three empty squares, no frogs. Right cannot move at all, ever. Left can advance the toads until they fill the right-hand end, and the number of moves available is the total distance the toads can travel: 3+2+1=63 + 2 + 1 = 6? The enumeration says 99.

The discrepancy is instructive. The leading toad can travel three squares, the second three, the third three — nine single-square moves in total, because each toad can occupy every square ahead of it in turn and the toads never block each other permanently when there is space for all of them. Nine moves, value 99.

TT. is worth 22: the leading toad steps once into the gap, and then the second toad steps into the vacated square. TTT. is worth 33 by the same counting.

So one-sided strips are counters, and the value is a move count. That is not deep, and it is exactly what makes the game not all-small — a position with no frogs gives Left an arbitrary reserve and Right nothing.

The interesting positions are the ones where both sides have pieces and the pieces are close enough to interfere. Interference is what produces switches and infinitesimals, and space is what produces integers.

Switches, and the cramped middle

Between the integers and the infinitesimals sit the switches, and they are the most common value in the enumeration.

TT.F is {12∣0}\{\tfrac12 \mid 0\}: Left moving reaches a position worth a half, Right moving reaches zero. Left’s option exceeds Right’s, so the simplicity rule does not apply and the position is hot — mean 14\tfrac14, temperature 14\tfrac14.

T.FF is {0∣−12}\{0 \mid -\tfrac12\}, the mirror, mean −14-\tfrac14.

T.TF is a plain 12\tfrac12 — Left’s option below Right’s, so the simplicity rule applies and the position is a cold number.

Three five-square strips, three regimes: hot for Left, hot for Right, cold. The difference between them is one piece moved one square, and no rule of thumb predicts which is which.

That is a fair picture of the game and of most games. The value classes are all present at small size, they are interleaved, and the only reliable way to tell them apart is to run the recursion.

The thermograph of {1 | 0}Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.-1-0.50.511.5201234valuetemperaturetemperature 1/2mean 1/2Left's wallRight's wall{1 | 0} — mean 1/2, temperature 1/2
Fig. 4 The thermograph of a switch of the kind these strips produce. The wedge is shallow because little is at stake — which is what a temperature of a half looks like when it is drawn.

Not an all-small game

A common claim about Toads and Frogs is that it is all-small — that every position is infinitesimal. It is not, and the counterexample is the first strip on this page.

T. is worth 11. T.. is worth 22. TT. is worth 22; TTT. is worth 33; TTT... is worth 99. A strip of toads with empty space ahead gives Left a great many moves and Right none, and the value is a plain positive integer, as large as the space allows.

An all-small game is one in which, at every position, either both players have a move or neither does. Toads and Frogs fails that as soon as the pieces are not interleaved.

What is true, and more interesting, is that the game produces the whole range: integers, dyadic fractions, switches, nimbers and infinitesimals, in strips of five or six squares. Games that are entirely all-small — Clobber, Cutthroat — have a narrower value set and are in that sense easier to describe.

Toads and Frogs on T.FT.F — and who winsA Toads and Frogs strip with the outcome stated before anybody moves. Toads move right, frogs left, and either may jump one opposing piece into an empty square. The position is worth zero, so whoever moves first loses — and every reply the machine makes was computed at build time.worth 0whoever moves first losesyou move the toads · it moves the frogswith the script running, the toads become clickable and this claim can be tested
Fig. 5 Six squares worth exactly zero, which under normal play means whoever moves first loses. The reader moves the toads and goes first. Every frog reply was computed in advance.

What the solver computed

toadsAndFrogs(strip) in lib/games.js builds the position from a string: T, F and .. Left’s options are found by scanning for a toad with an empty square to its right, or a toad followed by a frog followed by an empty square. Right’s are the mirror. lib/cgt.js evaluates and canonicalises.

The values quoted here came from an exhaustive enumeration: every string over the three symbols of length three to seven — 3,270 strips — each evaluated and canonicalised, with the distinct values collected. That produced 113 distinct canonical forms, and the named ones are as listed above.

The enumeration corrected an error in this site’s own draft. The infinitesimals essay originally described Toads and Frogs as all-small, on the strength of the four strips the default figure happens to draw, all of which are worth ∗\ast or 00. Enumerating found T. worth 11 on the second entry, and the claim was wrong. The lesson is the one this site keeps relearning: a claim checked against the figures that were drawn is a claim checked against a sample chosen for looking good.

Every value in the figures is re-asserted at build time. assertValue compares the canonical form against the caption’s claim and throws rather than render a wrong label.

The jump rule matters

A rules detail that turns out to be load-bearing.

A toad may jump over exactly one frog, into an empty square. It may not jump two, and it may not jump into an occupied square. If the jump rule is removed entirely, the game becomes trivial — pieces simply shuffle until they meet, and the values are all integers or zero.

If the jump rule is loosened to allow jumping over any number of opposing pieces, the game changes character completely and the values become different. The version analysed everywhere, and here, is the single-jump one.

That sensitivity is typical. Small rule changes in combinatorial games do not produce small changes in the value set; they produce different games. It is why “Toads and Frogs” without a statement of the jump rule is an ambiguous reference, and why the misère version is a different game again.

Toads and frogsToads 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.0P1/2L1/2 | 0N0 | −1/2Nblue toads move right · red frogs move leftevery value came out of the moves; none was chosen
Fig. 6 Four strips whose values are a zero, a half, and two different switches. The jump rule is what makes the second and third differ, and neither value is guessable from the picture.

Why enumeration is the method

For most games in this subject there is a choice between proving things and computing them. For Toads and Frogs there is not.

The values have no visible pattern. Strips of the same length differ wildly; strips differing by one square’s contents produce values from different families; and the value set grows at each length with no sign of stabilising. So there is nothing to conjecture and nothing to prove by induction.

What is available is exhaustive evaluation at small sizes, which gives certainty about a finite range and nothing beyond it. The enumeration behind this page — all 3,270 strips of length three to seven — took seconds and settles every question about strips that short. It settles nothing about strips of eight.

That is an uncomfortable position for a mathematical subject and it is a common one here. The honest statements are of the form “every strip up to seven squares was evaluated and here is what was found”, and the temptation is to phrase them as though they were general. The site’s rule against quoting values it did not compute is aimed exactly at that temptation, and the all-small error corrected above is what it looks like when the rule is not followed.

Toads and frogsToads 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.0P↑L1/2 | 0N↓Rblue toads move right · red frogs move leftevery value came out of the moves; none was chosen
Fig. 7 Four strips whose values are a zero, an up, a switch and a down. Nothing in the arrangement predicts which is which, which is why every one of them was evaluated rather than reasoned about.

What is unsolved

Toads and Frogs is a small game with real open problems.

The starting position. The natural starting strip is nn toads, kk empty squares, nn frogs. Its value is known for small nn and kk and there is no general formula.

Which strips are worth ↑\uparrow. No characterisation is known. The ones that are, are found by evaluation.

The value set. Which values are achievable by Toads and Frogs positions at all is open. Enumeration produces more distinct values at each length with no sign of the set closing.

Complexity. Whether deciding the winner of a Toads and Frogs position is hard in the complexity-theoretic sense is not settled, though the general expectation is that it is as hard as these games usually are.

Jeff Erickson catalogued the known results and open problems in the 1990s, and the list has not shortened much. As with Domineering, the small cases are computed and the general case is open.

What makes a game a good example

Toads and Frogs is worth its place on this site for a reason worth naming, since it is neither elegant nor played.

A good example for a theory does two things: it realises the theory’s objects concretely, and it does not flatter the theory by having been designed for it.

Hackenbush does the first superbly and fails the second — it was built so its values would be legible, and the legibility is engineering rather than discovery. Domineering does the second and barely the first: its values are real and mostly nameless, so it demonstrates that values exist and illustrates none of them.

Toads and Frogs does both. It was not designed for the theory, its rules are as arbitrary as any real game’s, and it nonetheless produces ↑\uparrow, ↓\downarrow, ∗\ast, plain integers, dyadic fractions and switches — the entire elementary value set — in strips of five or six squares.

That combination is rare. Most games realise one part of the value system and none of the rest, and a subject illustrated only by designed examples would be open to the charge that its objects are artefacts of the design. Finding ↑\uparrow in an undesigned game, at five squares, with the raw options literally 00 and ∗\ast, is the answer to that charge.

Who studied it, and when

Toads and Frogs is Conway’s, introduced in On Numbers and Games as an example of a game producing a rich value set from trivial rules — and specifically as a source of infinitesimals, which is what it is best at.

The extended analysis is Jeff Erickson’s, in the 1990s, including the enumeration of small positions and the catalogue of open problems. Games of No Chance (1996) contains his survey, which is still the standard reference.

The game has no recreational following worth mentioning. It exists as an object of study, which distinguishes it from Domineering, invented as a game, and puts it closer to Hackenbush, invented as an illustration — except that Hackenbush’s values are legible and these are not.

Where the model stops

Strips up to seven squares. That is what the enumeration covered and what the figures draw. Longer strips have values the code here has not computed, and none are claimed.

Single jumps only, as above.

Normal play. Misère Toads and Frogs is a different and much harder game.

No pattern in the values. The values listed are computed facts about specific strips, not instances of a rule. Extrapolating from them is exactly the mistake the enumeration caught this site making.

One-dimensional. Two-dimensional variants exist and none of this transfers.

The ladder from here

Nearby: the starting position and what is known about it; the characterisation problem for ↑\uparrow-valued strips; the full value set at each length; and Erickson’s open problems worked through.

Then across to the games where infinitesimals are all there is — Clobber and Cutthroat, genuinely all-small — and to atomic weight, which is the tool for comparing infinitesimal positions when their exact values are too unwieldy to use.

Where this goes next

↑{0 | {0 | 0}}> 0< 1/1024outcome L⇑{0 | {{0 | 0}, 0 | 0}}> 0< 1/1024outcome L↑∗{{0 | 0}, 0 | 0}‖ 0< 1/1024outcome N∗{0 | 0}‖ 0< 1/1024outcome N↓{{0 | 0} | 0}< 0< 1/1024outcome Rvaluecanonical formagainst 0against a thousandth↑ is positive and smaller than every positive number — which no real number is∗ is none of greater, smaller or equal — the order is partial, and that is the point 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. the boardworth 2 | −1/2outcome N{2 | −1/2}Left plays verticallyRight plays horizontally Domineering One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it. 1blue2blue blue1/2blue red3/4blue red blue1/4blue red red3/8blue red red blueeach string is worth a number, and the string spells itblue is Left · red is Right · the ground is what holds it up Hackenbush is a numeral Draw a stalk of coloured edges. Read it as a string, blue for one and red for zero, and the string is the binary expansion of what the position is worth. Not approximately — exactly, and the site computes it both ways and refuses to build if they disagree.