Tuesday, September 28, 2010

Searching for Games

There is no final exam in my combinatorial games class. Instead, the last four or so weeks will consist of student presentations. Each student is tasked with choosing a combinatorial game (that we haven't covered heavily in class) and researching "something interesting" about that game. Students will then present their findings.

The interesting thing does not need to be something super heavy, but should be non-trivial. So far I have three students who have chosen their games: Flume, Reversi and Hex. Of those three, two students have picked their "interesting things": one will code a playable version of Hex, while the other will describe the first-player winning strategy in Flume. In addition to these sort of options, students could write a program to determine the outcome class of their game, or just describe some interesting property (for example, that Hex cannot end in a tie or that the first player has a winning strategy in Chomp).

Part of my hope here is to learn more combinatorial games myself. I continue to work on expanding this table of games.

The other ten students have yet to choose a game. I have directed them to check out some resources such as Mark Steere's extensive list of creations, as well as the long appendix of games in our text, Lessons in Play.

Do you know of any other places I can point them to to find games? Certainly there is also a degree of procrastination, but it would also be great to give my students more resources. Also, it might come down to the point where I am forcing games upon the students. In that case, suggestions will be very helpful! Perhaps you've developed a game you'd like someone to check out!

Monday, September 27, 2010

Two turning points in my Games Class

Teaching this combinatorial games class has been tough. I am simultaneously teaching Software Engineering and Algorithms, and while both are challenging courses for students, they are going pretty smoothly. I know what I can expect from those students and know what I need to get across to them.

Combinatorial Games, on the other hand, is an adventure into some tricky territory. Since I have a wide variety of math and computer science students, I'm having a hard time making the correct assumptions about what my students already know. Since this is a new-fangled elective, I also don't have specific goals I need to communicate.

The structure of the course has been to spend one of the two class periods each week focusing on playing a new game. (Here is the class schedule so far.) The first week we played Domineering, then Clobber, then Toppling Dominoes. Students would play a bit amongst themselves, and do a great job answering questions I posed. But, after a few games and a few opponent-switches, they would get a bit bored. The 1.5 hour class started to drag on and a few students would actually ask me to return to lecturing. (Luckily, I brought some notes with me!)

Then, in the fourth week, we played Amazons. Wow. The students responded to this by actively getting into the game and trying to figure out good moves. The idea of outcome classes started to click and when I called for a change of opponents, very few people got up in the first minute.

Last week, we did something even better. I had the students play game sums (Note to me: I should have done this sooner!) and try to find different games that summed to zero. The base game was Amazons, and I drew different instances on the whiteboard and challenged the students to find different Domineering, Clobber and Toppling Dominoes games that, when added to the Amazons board, summed to zero. The result was possibly the best class period I have ever taught... even though I personally did very little. Students quickly took to their game boards, reasoned about some sums, then started filling up the marker board. Almost immediately some things written on the board were challenged (though no one was brash enough to erase another student's work without permission) and some excellent discussion began to take place.


It's hard to describe that level of engagement by students. Everyone was knee-deep in advanced mathematical material, experiencing it first-hand. We haven't yet defined many possible game values (I'm not sure we've defined anything rigorously yet) but students were quickly clamoring for an explanation of different fuzzy games and non-number values.

As I continue this semester, I think I need to make sure that every topic is motivated, and perhaps play games in each class (instead of every other). These last two game days have made an amazing argument for that!

Thursday, September 23, 2010

Out again tomorrow

Unfortunately I will be out again tomorrow. With any luck I'll be back in action next week.

Wednesday, September 15, 2010

Quantum Chess

Recently there was some cool board game buzz about combining quantum super-positions and chess: Quantum Chess.

The game was designed by Selim Akl as a response to the brute-force superiority of computers in standard chess. Alice Wismath, working with Dr. Akl, implemented a non-quantum version (they point out: "a true quantum board may be a few years in the future") as a Java 1.6 applet (I had to upgrade my browser's Java).

The basic idea behind this game is that the identity of each piece (aside from Kings) exists in a super-position before it is moved. The actual piece will be one of two different options (for example, either a rook or a knight) which is only known once you decide to move that piece. Thus, each turn consists of first choosing a piece to move, then determining what type of piece it actually is, then moving that piece.

Naturally, since the value of the pieces is based on some randomness (quantumness is considered randomness, right?) this is not strictly a combinatorial game. Until we have quantum boards, it's not exactly a board game either... Still, we can implement this in a non-quantum way using a big checkerboard and two sets of chess pieces. By putting two pieces on the same square to indicate the super-position for non-collapsed pieces, you can then decide the actual value by flipping a coin once the piece is chosen.

In any case, this is an extremely original game and an excellent work by Akl and Wismath. With any luck this will bring interest into both games and general quantum... ness. As you can see, I need a lesson on quantum mechanics and quantum computing!

Note: I will be out of action on Tuesday, so the next post will probably not occur until next Friday.

Tuesday, September 14, 2010


Hmmm, apparently I've been a bit confused recently about getting posts out at the correct time. I somehow posted twice last week on Tuesday without realizing it until Friday.


Unfortunately, I have just run out of time today.

I will have something new to say on Friday and will get back on my regular schedule.


Tuesday, September 7, 2010

UGrad Course Update and a Mini Course in Amsterdam

So far, things are going well with the combinatorial games course I am teaching this semester. This is an undergraduate level course, aimed at both Math and CS students, and includes sophomores, juniors and seniors. Today it came up that the class feels both like a graduate-level course and the third grade. We are covering advanced material, but at a reasonable pace and with a very excited audience.

The class meets two days a week for 90 minutes. I try to spend the majority of one day letting students play a new game, asking them questions while they are playing. So far, this has gone very smoothly, alternating between game-playing days and note-taking days. I keep track of the games we've played on our class schedule. (Notice I haven't chosen anything in advance!)

I have assigned programming assignments as well as written homework. The students will end the semester giving oral presentations covering games not studied in class. I'm already looking forward to this!

I've already gotten some advice, but I'd naturally love to get more. If you've taught or attended a CGT course (even if you're one of my current students) any comments would be welcome.

On another note, I saw this announcement for a Mini-course in positional games next week in Amsterdam. I have the sudden desire to be in Amsterdam! :)

Game Description: Martian Chess

Just last week, I forced my aide to sit down and play Martian Chess with me. This is one of the games I was introduced to at Origins this past year, and have been looking forward to the start of the semester to try it out more.

This game is sort of a more complex version of Clobber: pieces are arranged on a checkerboard, and they "clobber" pieces near them---except that there are 3 different types of pieces and they move in different ways. Pawns move one space in any direction (including diagonal), drones may move up to two spaces (but only horizontally and vertically) and queens may move exactly as queens in Chess. Pieces may not jump over other pieces. Okay, maybe it is more like Chess than Clobber...

Nevertheless, the goal is to take opponents' pieces. 3 points are given for a queen, 2 for each drone and 1 for each pawn captured. The game ends when a player no longer controls any pieces. The twist, however, is that when you capture an opponents' piece, they now take control of your piece on the board. This occurs because each player "owns" two opposite quadrants of the board: they may move any pieces in their quadrant. Capturing an opponents' piece means moving into an opponents' section and surrendering the piece you just owned.

Martian Chess is a really fun game that forces you to think on your toes. Just about when I seemed to be coming up with a strong strategy, Ernie pulled a new trick on me and had me completely second-guessing myself. I would really like to play this game in class, but, alas, I don't think I have enough Icehouse pieces!

Let's use this wacky ownership in a variant of Clobber: Reverse Clobber. Now, when I clobber an opposing piece, I instead lose my own piece. How much fun is this to play? (Maybe not so much...)