More Than Just A Game Of Tic-Tac-Toe

25 Aug

Last week, I was asked to build Tic-Tac-Toe for an interview happening in 1.5 days. I must have played Tic-Tac-Toe hundreds of times before , so it seemed like a really do-able task. After all, it’s just Tic-Tac-Toe!

Well, I learned that Tic-Tac-Toe is not at all that simple! Our brain is just doing amazing things to make it seem simple…


To get started with the game, I played a few rounds of Tic-Tac-Toe and thought about how I made each move:

  1. Can I win this round? If so add the winning move! If not… got to #2.
  2. Will the opponent win the next round (do they have 2 in a row / column / diagonal somewhere?)? If so, block them! If not, go to #3.
  3. Pick an opening with the best possible odds of winning.

The first 2 steps are not that difficult to program (just check rows, columns, and diagonals for 2 X’s or O’s), but picking the “best” move definitely is! I tried to optimize for open spots with the best of chance of winning. So, for example, if the board is empty, the middle spot has the highest number of winning paths – 4 (horizontally, vertically, diagonally, and anti-diagonally). However, this strategy was clearly not the best to implement, since  you can actually beat my game with some advanced plays!

This is because I focused on how the computer can win versus a more aggressive “how can i prevent my opponent from winning” strategy.

In my interview, the interviewer showed me the fascinating Negamax algorithm, which can be used to actually play out every single possible game ending and assign scores to each play based on the best outcome for the computer, all to make just one move!

And to think, this is all for just a game of Tic-Tac-Toe, which even a little kid can play! I will never look at Tic-Tac-Toe in quiet the same way again.

Advertisements

3 Responses to “More Than Just A Game Of Tic-Tac-Toe”

  1. Paul Zaich August 27, 2012 at 6:13 pm #

    Interesting stuff Natasha! I found myself trying to prevent the computer from winning in my algorithm, so it’s interesting to hear what your strategy was.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s