Toads and Frogs

This article is about the combinatorial game. For the Arnold Lobel children's book franchise, see Frog and Toad. For frogs and toads, see Salientia. For other topics, see toad (disambiguation) and frog (disambiguation).
An example of the combinatorial game 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.[1]

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.[1] 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.

A one-player puzzle version of the game has also been considered.

  1. ^ a b Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2001), "Toads-and-Frogs", Winning Ways for your Mathematical Plays, vol. 1 (2nd ed.), A K Peters, pp. 12–13