The strip nobody has a formula for

The rules take one line. Toads move right, frogs move left, either may hop over exactly one animal of the other kind into an empty square, and a player with no move loses. Anybody can play it on squared paper, and this site introduced it as the game whose values are stranger than the rules.

The obvious way to tame a game like that is to pick the simplest family inside it and find the formula. Here the family picks itself: a toads, a gap of k empty squares, then b frogs. Three small integers, one position, and every strip a beginner would draw.

There is no formula. Not “the formula is complicated” — there is no published closed form for the general member of that family, and the reason is visible in twenty-seven computed values.

The family, computed #

Start with one toad. T.F is ∗ — whoever moves wins, by a move rather than by a point. T..F is 0, a second-player win. T...F is ∗ again.

The parity alternation is the first thing anybody notices, and the first thing to distrust. Widen the frog side and it stops.

Now the toad side.

Twenty-seven strips of nine squares or fewer produce, among other things: 0, ∗, ±1, ±2, 2∗, 4∗, {0 | −1/2}, {1/2 | 0}, {1/8 | −1/8} and −2∗. That is integers, nimbers, numbers plus nimbers, and switches with denominators up to eight, inside a family described by three small numbers.

The eighth-point fight #

The strangest member in range is worth pausing on, because it is the one that ends any hope of a simple rule.

TTT..FFF — three toads, two spaces, three frogs — is worth {1/8 | −1/8}.

Nothing in that position has anything to do with eighths. Eight squares, three of each animal, two gaps: every quantity in sight is an integer. The eighth appears because the simplicity rule is applied three levels down a tree of options, and each level halves the denominator available.

Add one more empty square and TTT...FFF is worth exactly 0. The eighth-point fight is not a limit being approached; it is one member of the family, and its neighbours look nothing like it.

One strip, read out by hand #

TT.F is worth {1/2 | 0}, and the calculation is short enough to run in full — which is the best way to see where the halves come from.

The strip is toad, toad, space, frog. Left has one move: the second toad steps into the space, giving T.TF. Right has one move: the frog steps left into the space, giving TTF. — it cannot hop, because the square it would hop from is the empty one it is about to occupy.

Those two options are worth 1/2 and 0, computed the same way one level down, so the position is {1/2 | 0}: a fight, on a strip of four squares, worth a quarter of a move on average and a quarter of a move to enter.

The half in the Left option comes from one level further down, where a position with a single available step is compared against one with none. Nothing is approximated anywhere: every value is the simplest number between its options or a brace expression when no number will do, and the halves and eighths in this family are that rule applied repeatedly rather than a measurement of anything.

Why hopping is the awkward rule #

Stepping into a space is a harmless move. Hopping is what makes the family hard, and it is worth isolating the reason.

A step moves one animal one square and changes nothing else. A hop moves an animal past an opponent, which changes the order of the two of them on the strip — and the order is the whole position. So a single hop can convert a blocked strip into an open one, or hand the opponent a hop they did not have.

That is why the values do not vary smoothly with the parameters. Widening the gap by one square does not add a constant to the value; it changes which hops exist, and a hop that becomes available three moves deep can flip the class of the answer.

It is also why the position does not decompose. On a board that has fallen into regions, a move in one region leaves the others untouched, and the values add — that is the disjunctive sum and it is the engine of everything else here. A strip has no regions: any two animals are separated by squares that a hop may cross, so the only honest decomposition is the trivial one.

The lesson generalises past this game. A rule that reorders the pieces is a rule that destroys locality, and locality is what every large-scale technique in the subject is made of.

Where the values do settle #

It would be dishonest to present the family as pure chaos, because two clean statements hold across everything computed.

A balanced strip with a big enough gap is worth zero or a star. T..F, TF.TF, TTT...FFF and TT.TFF’s relatives come out at 0 or ∗ whenever the two sides mirror each other — which is a symmetry argument rather than a computation: a strip that is its own reflection with the colours swapped is worth its own negative, and a game equal to minus itself is worth zero or something confused with it.

An unbalanced strip with a wide gap is worth an integer. TT..F is 1 and TTT..F is 2, and the reason is that the extra toads have somewhere to go and nothing to contest: the position has become a count of spare moves, which is exactly the situation Cutcake is in permanently.

Everything between those two regimes is the interesting part, and everything in between is where the family stops being predictable.

Why the general answer is missing #

The honest account of why nobody has the formula has two halves, and only one of them is about difficulty.

The values leave the number line immediately. A formula for a family of games has to produce game values, and the family here produces infinitesimals — ↓ on a six-square strip. A closed form would have to say which strips are worth a number, which are worth a number plus a star, and which are worth something no number reaches, before it says anything numerical at all.

The recursion does not decompose. Every large-scale technique on this site rests on a position splitting into independent parts whose values add. A Toads and Frogs strip does not split: a toad at one end and a frog at the other are separated by squares that either of them may eventually occupy, so the two ends interact and the sum is not the object here in the way it is on a board that has fallen apart.

Without decomposition the only route to a value is a search over the whole strip, and the search grows exponentially with the length.

There is no language for the formula to be written in #

The two reasons above — the values leave the number line, and the recursion does not decompose — are both about difficulty. There is a third, and it is not about difficulty at all: there is nothing for a formula to return.

Look at what a closed form is, everywhere else in this subject. An octal game’s formula returns a nimber; Cutcake’s returns an integer; a blue-red Hackenbush string’s returns a dyadic rational read off the colours; Wythoff’s returns a yes or no about a pair. In every case the formula has a target class — a family of answers with its own notation and arithmetic — and the content of the theorem is a map from the parameters into that class.

This family has no target class. Twenty-seven strips of nine squares or fewer produce integers, an integer with a star, a bare star, an infinitesimal, and switches whose options are eighths. A formula for it would have to return an arbitrary short game, and there is no compact notation for an arbitrary short game — the brace form is the notation, and a formula whose output is a brace expression of unbounded depth is a description of the search rather than a shortcut past it.

So “nobody has written the formula” is not a report about effort. A closed form is always relative to a class of answers, and the first step in finding one is knowing which class to aim at. For this family nobody knows, because the family’s answers do not sit in one.

That reading also explains which sub-families are settled, and it explains them all at once. Strips with a single space, and strips with the animals packed against the gap, have known values — and what those sub-families have in common is that their answers stay inside one class. Once a restriction pins the answers to numbers, or to numbers plus stars, there is somewhere for a formula to land, and one gets written.

The values are strange and they are not unbounded #

One qualification, because “eighths appear on eight squares” invites the thought that the family produces arbitrarily fine values and cannot be pinned down at all.

It does not, and the reason is the same simplicity rule that produced the eighth. A denominator of $2^d$ requires $d$ levels of the rule, each level is a move deeper in the game tree, and a Toads and Frogs strip of $n$ squares has a game tree of bounded depth — every move advances an animal towards its own end and the total advance available is fixed by the strip.

So the denominators on a strip of $n$ squares are bounded by $n$, in the sense that a value needing more halvings than the strip has moves cannot arise. The eighth on eight squares is therefore near the ceiling for its size rather than an early sign of something unbounded, and a reader worried that a longer strip might produce a value no notation could hold is worrying about the wrong thing: the values get more numerous with the length, not finer than the length allows.

What that does not buy is a formula. A bound on the denominator says the answers live in a finite set for each strip length, which is true of every finite game and predicts nothing about which member of the set a given strip gets. The family is bounded and unpredictable, which is the harder of the two combinations to say anything about — an unbounded family would at least suggest what the unboundedness was tracking.

What is actually known #

The published state of the game is worth stating precisely, because “unsolved” covers several different things and three of them are called solved.

Toads and Frogs is solved position by position for any strip small enough to search, which on this site means about a dozen squares. It is not solved as a family: there is no known procedure that takes a, k and b and returns a value without searching.

Some sub-families are settled. Strips with a single space, and strips with all the toads and all the frogs adjacent to it, have known values. The general two-parameter family with a gap of arbitrary width does not, and neither does the general strip with animals interleaved.

What makes even a dozen squares reachable is that the search is over distinct positions rather than over routes to them. A strip has many ways to arrive at the same arrangement — the toads at one end can be advanced before or after the frogs at the other — and a solver with no memory pays for every route, while one that remembers pays once per arrangement. The gap between those two costs is the whole of what memoisation buys, and on this family it is the difference between nine squares and none.

The strip that plays back #

The values are settled well enough for a small strip to be an opponent, which is the demonstration this site keeps making.

Worth zero and the reader to move means the reader cannot win, whatever they play. That is a stronger demonstration than a position a reader might lose by inattention: the losing is a theorem, computed before anybody sat down.

The family beside its neighbours #

It is worth setting Toads and Frogs against the other particular games on this site, because the comparison says what kind of unsolved it is.

Cutcake is completely settled: every value is an integer, the integer is a count, and the generator refuses to draw a cake whose value is not one. Domineering is settled position by position and unsettled as a family, exactly like this one — but its values on small boards are mostly switches and infinitesimals of familiar shapes. Clobber is settled in kind rather than in value: every position is all-small, which is a theorem about the rule, so the class of the answer is known before any search runs.

Toads and Frogs has none of those. There is no theorem that says which class a strip lands in, and the computed values show all four classes turning up in strips of nine squares or fewer.

That is the distinctive thing about it and the reason it keeps its place in the literature. A game whose values are hard to compute is common. A game where the kind of answer cannot be predicted from the shape of the position is rarer, and it is the reason this family is a good test of any proposed shortcut: a rule that gets the numbers right and the class wrong has not understood the game.

What the values are good for anyway #

An unsolved family is not a useless one, and Toads and Frogs earns its place in every account of the subject for a reason that has nothing to do with formulas.

It is where the awkward values come from. Almost every small value in the theory turns up in some short strip: integers, halves, quarters, eighths, stars, ups and downs. A game that produced only numbers would not have needed the theory built for it.

And its positions are comparable to other games’ positions. A strip worth ↓ can be substituted for any other position worth ↓ anywhere, and that is what having values for — the equality that quantifies over sums.

That comparability is worth spelling out on the four values above, because the answers are not the ones the printed forms suggest. ↓ is genuinely less than zero, so TTF.FT is a strip Right is happy to be handed in any sum whatever. ∗ is not less than zero and not equal to it either: TT.FF is confused with zero, which is why whoever moves wins it. And {1 | ∗} is confused with 1 rather than smaller than it, so TT.TFF cannot be traded for a single free move even though its Left option is one. Three of the family’s values, three different relations to the plainest yardsticks the theory has — and not one of them readable from a picture of a strip.

Where the model stops #

Twenty-seven strips is not a family. The values quoted here are every member of the gap family up to nine squares, which is what this site’s evaluator reaches comfortably. A pattern that broke at eleven squares would be invisible from here, and the essay’s claim is about what the computed range shows rather than about what a longer search would.

Nothing here proves no formula exists. “Unsolved” means nobody has published one, not that one cannot be found — and the family is small enough that a formula is a plausible thing to hope for. What the computed values establish is why it has been hard: any formula has to produce four different kinds of value and it has to do so without a decomposition to lean on.

And the interleaved strips are a different question. TT.TFF and TTF.FT are in this essay because they are short and their values are informative, and they are not in the gap family at all. Whether the interleaved case is easier or harder is not something the computed range says.

What the picture cannot show #

A strip is drawn as squares with discs on them, which is exactly what it is, and the drawing is complete: nothing about the position is hidden.

What it cannot show is the search. Under the nine-square strip worth zero sit 1,129 positions that had to be walked to establish it, and the picture of the strip is the same size as the picture of a strip worth {1/8 | −1/8}. The cost figure is in this essay because that number is invisible everywhere else.

The second thing not shown is the family. Every figure draws three or four strips, and the arguments above are about the twenty-seven the site can reach and about the infinitely many it cannot. A figure showing that the values do not follow a pattern would have to show the pattern’s absence, which is not a thing a drawing does — the absence is established by listing the values and noticing that no rule fits.

The convention, named #

Normal play throughout: the player who cannot move loses, and a strip where a toad is walled in by frogs is a loss for the toads rather than a stalemate.

That convention is doing real work here, because Toads and Frogs is a game where running out of moves is common. Under misère play — the player who cannot move wins — the same strips have different answers and the whole apparatus of values is unavailable, so nothing on this page transfers.

One rule convention also deserves naming, because implementations differ. A hop here passes over exactly one animal of the other kind into an empty square, and no longer jump is legal. A version allowing longer hops is a different game with the same picture, and its values would have to be recomputed from the top.