Tic Tac Toe — an approach to analysis

It’s a Saturday afternoon, and so naturally my wife and I decided to analyse the game of tic tac toe, because that’s what everyone does with their weekends right? For a little while I have wanted to learn, play and analyse a spectrum of different games. I maintain my notes on what I plan to do and have done so far in this regard on the games section of my website.

A little brief on the history of tic tac toe, and the rules of the game can be found on the page for the same on my website. With that basic context in mind, we wanted to analyse what it takes to win a game of tic tac toe. And so we went to the drawing board, literally.

We decided that developing a winning strategy would mean that we have to figure out what all possible situations could come up in the game. And then for each possible situation figure out what the best strategy is to win. Of course, this approach can be followed by both players. When both players follow their best possible strategy, 3 things could happen:

1. X always wins (Wx)
2. O always wins (Wo)
3. The game is always drawn (D)

Now, we have all played a fair bit of tic tac toe, so we know instinctively that the game is always drawn unless someone slips up. But the fun is in figuring out how we can either prove this or realise that our lives have been a lie.

So, now onto analysing every possible situation. Tic tac toe is a game which seems like it can be studied very nicely in the form of a state tree. What I mean by this is that:

• At every point of time the game has a specific state (the layout of Xs & Os on the grid)
• From most states there are a few possible child states (possible next step states)
• Some states are final (when the game is over)

This sort of tree structure represents all possible games of tic tac toe.

Now that we have put our game into a data structure of sorts, we can reframe our question. How do we identify a winning strategy = “a set of paths in the tree which will always lead to a winning end state”? Or perhaps, if both players play their best game, they will always be able to take paths in the tree which lead to a draw?

To figure this out, we can start with a few observations:

• The tree can have a maximum depth (number of levels) of 10 (with the empty grid state as level 1 and the full grid as level 10)
• Each node can have a maximum of 9 immediate children (and much fewer if we club together nodes which are logically equivalent)
• Each node represents either X’s turn or O’s turn, with level 1, 3, 5 etc being X’s turn and even levels being O’s turn
• In general, as we go down the tree, each node will have fewer immediate children, because of fewer possible actions
• All end nodes or leaf nodes must be either Wx (X wins), Wo (O wins) or D (draw)
• An end node need not be at level 10, it can be earlier in the tree if it is a Wx or Wo

Every end node has a fixed outcome (Wx, Wo or D). The important observation is that we can identify the “best strategy outcome” for other nodes (before end nodes) as well. Take for example a node, all of whose children are end nodes. Let’s assume that this node is at an odd level and represents X’s turn to play next. The best strategy outcome for this node is:

• Wx if any one of its children is Wx — Because then X will always make the move which results in them winning next turn
• D if none of the children are Wx, but there is at least 1 D child — Because then X will always pick a draw, if that’s their best outcome
• Wo if all of the children are Wo — Because there is no better move

This sort of calculation can be invoked recursively to trace back to the starting of the game to find out if the empty grid is Wx, where X has a guaranteed winning strategy, Wo which is the reverse, or D where good players will always draw.

Of course, we expect the starting state for tic tac toe to be D. But to make this even more fun, I intend to put this into code and simulate this backward tree calculation next.