Game Description: Toads and Frogs

Prior to this semester, I got a lot of helpful suggestions for preparing to teach Combinatorial Games. One reader, Joshua Biedenweg (instructing at UC Santa Barbara while an undergrad!), was in the middle of teaching his own CGT class and suggested I include Toads and Frogs in the class. I liked his reasoning, but wound up using Domineering as the main guiding example, as it is used throughout our text.

For our recent "game day" class, I tried out his suggestion, and Toads and Frogs worked out really well. Students quickly figured out the value of many games, including some games of arbitrary sizes!

Toads and Frogs is a game invented by Richard Guy. A game state consists of a horizontal row of "spaces", each of which either empty or inhabited by a Toad or Frog. Toads face right (but are controlled by the Left player), and Frogs face left (controlled by Right), and may only move in the direction they are facing(Toads move "to", Frogs move "fro"). Each turn, a player chooses one of their amphibians and moves it. An amphibian may move one space if that space is empty, or may instead jump over an adjacent opposing piece if the space behind that piece is empty.

For example, in the following situation a T is a Toad, an F is a Frog, and an underscore, _ is a blank space. Then in this game:

T _ _ T F _

Left can move both of his amphibians, resulting in either _ T _ T F _ or T _ _ _ F T. Right only has one frog to move, and can move to T _ F T _ _. As my class found out, it is fairly easy to evaluate a lot of different positions, and as Josh explained to me, this is a great demonstration of different game values. Sums are also very easy to do: just draw the rows on top of each other.

Simple rules, simple game description. And, fortunately, this game is hard to play well! Jesse Hull showed that NP-hard instances of the game exist (using techniques I am not familiar with). I wonder whether it can be shown that determining a winner is also PSPACE-complete.

The best challenge I came up with for my class was to add two games together:

T _ _ ... _ _ _ F
+
T _ _ ... _ _ F

Where the top row has one more space between amphibians than the bottom. The result is very nice (* = {0|0}) especially since students' intuition had them first thinking it depended on whether the top or bottom game had the odd number of spaces.

Thanks Josh, for telling me to check this game out!