I was delighted to see an analysis of Tic-tac-toe on XKCD. Here is a small part of the remarkable graph format XKCD uses to show all the possible outcomes. It shows all the possible moves and the optimal responses for games that start with X in the top left corner and O in the center.

Tic-tac-toe is a good game for computer science. The rules are easy to code. Unlike chess, go, or poker, it’s possible to write a simple program that plays the game perfectly. Games finish in at most nine moves, so it’s easy to test. By considering similar states (starting with X in the top left corner is similar to starting with X in the bottom right corner, and so on), you can learn about the tradeoff between efficiency and complexity. You might start out creating a interface for playing Tic-tac-toe, and then move on to building a system that plays it against you.

A few years ago, W- was active in a LEGO group that organized occasional contests. They were thinking about competing to build a robot that could play tic-tac-toe using a marker and paper. I played with the idea of making a similar graph of all the tic-tac-toe possibilities so that I could encode it into a program, but I never considered anything close to this brilliant format.

The compactness of this graph is amazing. The recursive fractal goodness of it all warms the cockles of my geek heart. And yes, on first look, it seems really complicated and confusing, but if you can figure out enough to find the first few steps, everything will fall into place and you’ll be able to follow it all the way down. I love it like I love iterations of the Peano space-filling curve, the Koch snowflake, and the Sierpinski carpet.

What I like even more is the fact that the community has been debugging the graph, discussing optimal strategies that start with non-corner moves, sharing complete computer-drawn graphs and other sources for similar diagrams (including books). Ahh, geekery…

Image excerpt © 2010 Xkcd – Creative Commons Attribution Noncommercial 2.5 License