Tuesday, February 5, 2019

Tic Tac Toe: First Move Strategy

Tic Tac Toe is one of the most popular paper and pencil games. It is also known as "Noughts and Crosses" or "Xs and Os". In the classic variation two players take turns marking squares on a 3x3 grid. One player (X-player) marks her squares with Xs (crosses), another player (O-player) - with Os (circles). X-player starts the game. A player who manages to mark a whole row or a whole column or one of the two diagonals wins and shows it by crossing the winning squares. Here are a few examples.

Like millions of others, I played this game as a child and learned the "right moves". Recently I had some free time on my hands and although there are plenty of Tic Tac Toe apps, I decided to write my own just for fun and experience. This required a more detailed formal analysis of game strategies. Figuring out what the optimal first move is is an interesting challenge. The answer is well known to "seasoned players" but I hope the following description will serve as a useful game guide or tutorial for beginners. 

At first glance it may seem that X-player has a big advantage - by the end of the game she can mark 5 squares out of 9, while her opponent O-player can at most mark 4 squares. But it is well known that having first move advantage is not enough to win Tic Tac Toe against a perfect player (the one that always makes optimal moves) - a game between perfect players always ends in a draw. Moreover, a perfect X-player can choose any square as her first move and still tie the game no matter how hard her opponent tries to win. So the first move of a perfect X-player against a perfect opponent does not matter - the game will always end in a draw.

Well, what about playing against a non-perfect opponent? Here is where the first move can make a big difference. To simplify our description we will introduce a hypothetical good player (call him Joe) and make him follow a particular strategy. Joe by no means represents all possible non-perfect opponents, but we will make him pretty smart, sensible and disciplined to be a good substitute for a solid player. In fact, Joe's skill level is just one notch below that of the perfect player (call her Jane). Joe does not make simple mistakes - he picks his moves looking two steps ahead. How does he do it? What is his strategy? When Joe's turn comes, he first tries to find a critical line - a line with one free square and two identically marked squares. If such line exists he will mark the free square with his mark. This move will (depending on the marks of the other two squares) either make him the winner of the game or prevent his opponent from an immediate win on the next move. Here are 3 examples of Joe executing the first step of his strategy. Joe's last move is highlighted in gray.

The first step of Joe's strategy is helpful, but - as you can see from the third example above - it does not always prevent Joe from losing the game to Jane. As Joe blocks one critical line (right column), Jane will win by turning the second critical line (top row) into a winner. This example shows what is called a fork - two (or more) identically marked critical lines without a common free square. Forks are fatal - no matter which critical line Joe picks, his opponent will always win by marking the free square on the other one. Here is where the second part of Joe's strategy comes in handy. Joe is not called a good player for nothing: in addition to preventing Jane's immediate critical lines, he is also able to think two steps ahead and pick a move that prevents Jane from creating a fork on her next move. If there is no danger of Jane creating a fork, Joe will try to create his own if possible (never possible if his opponent is a perfect player). It is important to note that Joe will start thinking about blocking/creating forks only after he has made sure there is no chance of him losing/winning by exploiting an existing critical line. (Do you see how Jane can use this to her advantage and still create a fork despite Joe's best effort to prevent it?) Here are a few examples of the "forking" element of Joe's strategy. Joe's last move is highlighted in gray, and the prevented forks are marked by dashed lines.

The first two examples are straightforward - Joe simply marks a square that Jane could have used to create a fork. The third example is slightly more tricky. There are two free squares that Jane can use to create a fork - top right corner and bottom left corner. Joe can mark one of them, but it would not prevent Jane from using the other to create a fork. So Joe saves the game by creating a critical line of his own (middle column). This move forces Jane to mark the bottom middle square instead of creating a fork

With that, Joe's capabilities as our hypothetical good player reach their limit. If there is no opportunity to apply the two elements of his strategy, he can not think three steps ahead and just marks one of the remaining free squares at random. And where Joe's capabilities end, Jane's opportunity arises. It is time to return to the main subject of this article. When Jane is the X-player, what should be her first move? There are three distinct options - the center, a corner, or the middle of an edge. Note that if Jane picks a corner, from a strategy analysis perspective it does not matter which of the four corners she picks. The reason is the symmetry of the grid. For example, the bottom left corner turns into the top left corner if you rotate the grid 90 degrees clockwise. The same argument goes for the middles of the edges. The symmetry argument simplifies the strategy analysis - we only need to analyze 3 moves, not 8.

Basic intuition might suggest that picking the center is the best move. After all there are only 8 possible winning lines on the grid - 3 rows, 3 columns, and 2 diagonals. The center covers 4 out of these lines, a corner 3, and the middle of an edge only 2. So putting a claim on half of the winning lines with one move must be the best choice. Well, it turns out basic intuition is not always right. More thorough analysis is needed.

Let's say Jane picks the center. Joe will pick at random either a corner or the middle of an edge. If Joe chooses the middle of an edge, Jane will always win. The picture below shows an example of how Jane can do it.

If, instead, Joe chooses a corner and follows his rules, he can always tie the game (there is not enough space here to demonstrate all possible plays - feel free to experiment yourself). That means that the probability of Jane's winning against Joe if she starts with the center is 4 out of 8 - 50%.

Now let's say Jane starts with a corner. Joe will pick at random one of the remaining 8 squares. If he happens to pick the center square he will be able to tie the game. But if he picks any other of the 7 squares, Jane will win (see an example below). That means that the probability of Jane's winning is 7 out of 8 - 87.5%. Much better odds!

Lastly, let's say Jane picks the middle of an edge. The following diagram shows the four possible moves by Joe that will make Jane win and 4 moves that will allow Joe to tie the game (convince yourself by experimenting!). That means that the probability of Jane winning is 4 out of 8 - 50% - the same as the center square first move.

To summarize, Jane's best first move against our hypothetical good player Joe is a corner square. As you notice, we did not provide an exhaustive analysis of how Jane wins and how Joe ties. We also did not analyze other strategies a non-perfect player might use. But we covered the basics, and some fun has to be left for actually playing the game with a friend or with your phone (who is also a friend :-)). Feel free to download and install my Tic Tac Toe app by following the link. It is free and will not bother you with ads. Just enjoy the game!

Get it on Google Play