Breaking Symmetry

Right away while teaching combinatorial games, my students latched on to the idea of symmetric arguments. It comes early in the book and is more convincing of a good plan of attack than greedy strategies (and is easier to use than finding transformations to other games). Whenever we play a new game, the students first look for ways to play symmetrically and then how to escape such a situation. This is an excellent pattern, since symmetry is not always a trivial venture, and likely a good indicator you are competing with a gamester.

Okay, so say your opponent in a game is employing a symmetry-based strategy, which will be successful unless you break it. You see an opportunity to break the symmetry, but it's something you can do now or later. When should you do it?

I bring this up because Neil McKay noticed a flaw in the symmetry argument for the first player in Flume. Gasp! I have amended the game table but hope to have the matter resolved. I will present Neil's illuminating break at a later date (after it is not immediately relevant to my class; some students are actually reading this!) but it's great that he found a counterexample to the strategy.

This event makes me curious about symmetric strategies in general. Flume was a bit of a special case, because the symmetry employs two steps each turn: first be greedy and take all the free spots, then turn around and make the same move your opponent did, allowing them to make the same great moves you just did. (Luckily, you should always be ahead by one piece.) This seems to me as a bit of an "impure symmetry" (perhaps more so now that there's an escape). I still hope that there is a method to restore the symmetric state in Flume, though I'm likely biased at finding out I was wrong.

Even more so, I'm interested in other surprising examples of symmetric strategies. Are there any examples of games where symmetry can win you the day, even when you wouldn't expect it? Are there any other examples of impure symmetry that wind out working great? Are there any examples of breakable symmetry strategies that are actually robust enough to be restored?

I'd love to hear about them!

Nothing Tomorrow

I hope your tomorrow is full of wonderful things. Sadly, a post here will not be one of them.

I have spent lots of time out of the office due to unexpected appointments. Teaching is my number-one work priority, and so other things must fall to the wayside a bit.

Also... I need to figure out how to get Blogger to report the post as being dated with the day I actually Post it, not the day I first start editing it.

I do hope to return on Friday with another post!

Chickening out on Chess

I haven't played a game of Chess in years. I was recently approached by some students asking to start a Chess Club, and we're going ahead with that. I hope I'll be able to learn to play moderately from them!

Yesterday we were set to have another "Game Day" in class where students would find values (and outcome classes) of different game states. I was hoping to do Chess, and had been flipping through Noam Elkies' paper on Chess end games. A lot of stuff in there was excellent and would really get my class thinking.

But I chickened out. I know that most of my students know how Chess works, but I wasn't sure if they'd be able to see some of the acceptable moves quickly. I was nervous teams might spend half the class figuring out what was going on in one example. Worse, I was afraid I wouldn't be able to cook up new examples on the fly as I have the rest of the year. I have to really be careful with Chess to avoid instances that are not short games.

Instead, I introduced Konane (I'll write separately about this game some time; it's very nice). I played a few times with my aide the day before, then threw a bunch of boards up on the whiteboards. The students dove in immediately; writing up outcome classes, values, and questioning or confirming the results of other teams. I stopped every so often to explain how to derive some values and to switch up partners.

So far, we have only covered Nimbers (defined only via equivalence to Nim heaps) and positive and negative integers, so some of the boards were not given explicit values by the students, as expected. It is almost equally rewarding when students express frustration over not knowing the value of Up---I know they're interested to hear more from our lecture days.

We really should do Chess, though. There are only a few more weeks before we get deep into the student presentations, so I'll have to introduce it soon! Hopefully I'll have good news to report then.

Updated Game Table

I updated this table of Combinatorial games and some of their known properties. This time I added a column to list variants of games. I still want to add more games and properties, please inform me of more results to add! These could include:

More Games! I'd love to add more rows.

Properties! I'm sure there are some incomplete cells that could be updated. This time I added "Open" if the problem is known to be open (there must be more of these).

References! I added a bunch of links, but there must be more (or better) supporting documentation for some things. I would love to add more links.

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!

Still no post...

I just returned to the office today and have been busy all day catching up. I am planning on having a new post ready on Friday.

Sorry again!

No post: sick!

I've had a cold all week. More posts next week!

Nearly Shooting Myself in the Foot with Misere Sums

Oops!

Last week, in an effort to relive my success with finding negative games by summing to zero, I tried the same thing with a new game. The plan was to add states of a new game to states of games we had already covered, then see if they sum to zero. I wrote up states of the new game, and challenged students to find states in Clobber, Amazons, Nim, etc, that summed with the original game to get zero. Unfortunately, I hadn't had a good idea for a new game, so instead I decided we would play Misere Clobber.

Pretty quickly, students asked me: "Wait, how do we add a normal play game to a misere game?"

Oops!

Somehow I did some quick thinking (I usually can never seem to do this in front of a class) and reminded myself of how to make this "legitimate". I wound up writing two options on the board:

Either players are not allowed to make the last play in the misere game, or whenever a player makes the last move in the misere game, they immediately lose.

Whew! Things progressed pretty nicely at that point. Still, I was wary of teaching them that games can have the misere property instead of attaching that property to the method for playing a game. At least this took care of covering all the mechanics we needed to find negative games.

I took a number of wonderful pictures of the boards and of my students playing, but my new phone seems to have trouble with its camera and the pictures were never stored. Instead, enjoy these pictures one of my art-minded students drew on my whiteboard after we covered the definition of a game negative. :)