January Challenge #9: Tic Tac Toe

Reposted on new blog at http://dynamitochondria.blogspot.com/2010/01/january-challenge-9-tic-tac-toe.html.

I kicked a co-worker's ass at Tic Tac Toe this week. Until he threw four orthogonal lines on the whiteboard while waiting for a program to install, I wasn't aware that any adults still play the game with any seriousness.

It didn't go well for him at all. After a few rounds of making him choose which of two winning plays to block, I admitted that I had over-analyzed the game long ago when I wrote a Tic Tac Toe AI that could consistently win or tie unless you knew exactly how it would react to a given game state. It only predicted outcomes one move out, so by manipulating it, you could force it to choose which of two winning plays to block.

Tic Tac Toe is a great learning tool to understand game states. In theory, there are 9! (factorial) ways to place X's then O's onto the game board, but in reality, there are a lot fewer potential game state sequences. First thing, you can remove two thirds of them by realizing that there are only three meaningful opening moves: center, corner, and edge. In response to a center open, there are only two meaningful second moves: edge and corner. And in response to an edge or corner open, there are five meaningful second moves: adjacent corner, non-adjacent corner, adjacent side, non-adjacent side, center.

After that, it's harder to get away with that kind of abstraction, so we're down to 7!*(2+2*5) possibilities. Right? Wrong. Most of these lead to wins before all the tokens can be placed. For example: X upper-left, O center, X lower-right, O upper-right, X lower-left. X wins on its next move, barring catastrophic aneurysm or some other act of god.

Most games descend into reactive play by one or both players by the fourth move and will end in a tie, assuming basic competence on the part of both players. This is why most people lose interest in the game by late childhood. It has two possible avenues to rekindle interest, as a teaching/learning tool to master the concept of game state, or as an exercise in manipulating your opponent.

As I mentioned above, the only way to beat the Tic Tac Toe AI was to know how it would play. The same can be applied to human opponents. I guessed that my co-worker would employ the common wisdom of preferring the center and then the corners, so I made my moves accordingly and won. I then guessed that he would learn from his mistake and alter his approach, and I won again.

In this, Tic Tac Toe shares some characteristics with Rock Paper Scissors, which has a serious following with world championships. I kid you not. In the abstract, RPS is about random choices which should result in even odds of win, lose, or tie. Not so much. It's about reading your opponent, and manipulating them as they try to read you.

Getting seriously stomped at a strategic game can be a valuable learning experience, especially an extremely simple one where you can almost instantly grasp the entire game state, but the fun goes away pretty fast, so I didn't wait long to explain to my co-worker what I was doing. Much like learning how you were fooled by stage magic, the fun was quickly restored. Not a game developer, he might not derive any professional usefulness from the experience, but I hope he learned enough to clobber another co-worker at Tic Tac Toe somewhere down the road.