Toads and Frogs

The combinatorial game Toads and Frogs is a partisan game invented by Richard 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. However, the general case of evaluating an arbitrary position is known to be NP-hard. There are some open conjectures on the value of some remarkable positions.