Friday, October 29, 2010

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!

1 comment:

  1. I sincerely hope that no one in the class reads this regularly because its going to be detrimental to my presentation points for winning against the class.

    ReplyDelete