Games!

I just watched an episode of Numb3rs, which is an FBI detective show with a healthy dose of math/CS. I used to watch a lot of it, but the math has somewhat soured in recent episodes. Coincidentally, my fantastic high school math teacher's father did math consulting for the show after his blog about the show gained some attention with the producers. Cool!
Disclaimer for real math-heads: Numb3rs is best when taken as entertainment, and as discovery of math topics. Often, in the translation from math to exciting real life application!!1, the math is distorted a little.

Anyway, this episode (which happens to be the one on the home page of Numb3rs linked above right now) mentioned the Chinese Room thought experiment and the perfect information game of Chomp (or Munch, etc). Chomp is a fabulous game because it is both utterly simplistic and a neat window into mathematics and game theory. Try it out at the previous link after you read this quick description.

(As an aside: the Chinese Room thought experiment, like most thought experiments, is a great read. I may write about it later, because it seems to be a very interesting statement on Artificial Intelligence that, with apologies to one of the greatest men in history, goes beyond Turing Tests.)

I mentioned that Chomp is a perfect information game, which is a fancy mathematician way of describing games like checkers or chess, as opposed to the prisoner's dilemma. In other words, in a perfect information game, the entire layout or "state" of the game is out there for all players to see. In the prisoner's dilemma, the strategy comes from the lack of perfect information, as it does in most games, like poker or, more abstractly, life. Although I, like most people, have played a perfect information game and thought nothing strange of it, I now find it kind of interesting that some games can have strategy and be interesting without withholding information.

Okay, back to Chomp. I mentioned that Chomp is simple- the players alternate taking blocks of items from a grid. These blocks are created by picking an item and taking all of the blocks to the right and down from that item. This is a lot easier to visualize with the sample game I linked above, called Munch. With that online version, you can play against a computer that always plays optimal moves.

Now comes the interesting part of Chomp: with perfect strategy, the first player always wins. In Numb3rs, Charlie claims that although this can be proved, the winning strategies cannot be proved. I don't think that's true at all. According to the W-God, the first player always wins because of strategy-stealing. The strategy-stealing argument claims that the proof does not constitute how to win every time, because it is non-constructive, i.e., a mere statement of existence. This may be why the show claimed that the winning strategies cannot be proved, because intuitively, I'm sure that you can reason out winning strategies for Chomp, if only by brute force. I may examine this later.

So, if you haven't yet, play around with Chomp online, and then play with your friends. See if you can always win as the first player. To be honest, I haven't figured it out yet!

I'm a big fan of simple games like these that hold the key to interesting mathematical concepts. Feel free to post any others you know of. I once attempted to learn Go, but after a few hours, I was still pretty mediocre. I think mastery of the game is beyond my reach. Go is interesting because it is fairly simple, but incredibly complex to play in practice. In fact, in CS terms, the depth of the search required to play well is so large that computers will probably never solve it in brute force (like they did Chess with Deep Blue).