Toads and Frogs
Toads and Frogs
The combinatorial game Toads and Frogs is a partisan-game invented by richard-k.-guy. This mathematical game was used as an introductory game in the book [[winning-ways-for-your-mathematical-plays]].
Known for its simplicity and the elegance of its rules, Toads-and-Frogs is useful to illustrate the main concepts of combinatorial game theory. In particular, it is not difficult to evaluate simple games involving only one toad and one frog, by constructing the game-tree of the starting position.
These conjectures fueled further research. Jesse Hull proved conjecture 6 in 2000, which states that determining the value of an arbitrary Toads-and-Frogs position is NP-hard. Doron Zeilberger and Thotsaporn Aek Thanatipanonda proved conjecture 1, 2 and 3 and found a counter-example to conjecture 4 in 2008. Conjecture 5, the last one still open, states that <math>T^a \square^b F^a</math> is an infinitesimal value, for all (a, b) except (3, 2).
Single-player puzzle
It is possible for a game of Toads and Frogs to end early. A one-player puzzle version of the Toads and Frogs game, published in 1883 by Édouard Lucas, asks for a sequence of moves beginning in the standard starting position that lasts as long as possible, ending with all of the toads on the right and all of the frogs on the left. The moves are not required to alternate between toads and frogs.