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:
- Can I win this round? If so add the winning move! If not… got to #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.
- 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.