The Joy of Teaching Games

Last Wednesday was the second day we just spent playing games in class, and the first one where they had learned some of the theory (specifically, outcome classes). What a blast! I started putting up Amazons positions for them to find the outcome classes of partway through the class. They picked up on this challenge immediately, students flocking to the boards to post the class they had found, then either verifying or questioning the results of others. I had about twenty positions around the room and only a few of them remained unexplored by the end of the hour. The air is very charged, but the feeling is very positive. Students are working together to solve the problems, and this requires them to try out moves on physical boards, then confer with the people around them. Your opponent quickly becomes your best teammate as you collaborate to test all possible game tree paths. For some of the harder boards I put on the marker boards, groups had banded together to discuss their results as a bigger team. There was not an unengaged mind in the room!

As I've mentioned, this class is a first-year-experience seminar at Wittenberg (a WittSem) and has the dual purpose of helping integrate the students into college life. After teaching the math/compsci-elective version of the class last year, I thought games could make for a nice WittSem topic. I was further spurred on by David Wolfe, who told me he had once taught a freshman-introduction class all about playing Go. (I only just played my first game of Go last week, so I wasn't ready for that!)

These new students have actually been very patient. I promised them early on we would spend entire class periods playing games, and it took over two weeks of class before we covered outcome classes; giving them something to analyze while playing.

Also on the point of teaching, I happened across an old reddit post of Joshua Biedenweg's, prior to his teaching a CGT course at UCSB. Josh finished teaching his course right as I was prepping for mine over a year ago; I took some good advice from him and unfortunately ignored some better advice! (Josh, I'm using Toads and Frogs more this year! Pictoral Evidence:

)

Next on the class agenda is Game Sums, and soon it will be time for them to find actual game values! Woohoo!

Conclusion: Teaching CGT is awesome. If you have the opportunity, take it!

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!