Ultimate Tic Tac Toe

If you think classic Tic Tac Toe is too easy for you - try Ultimate Tic Tac Toe! This game (also known as Strategic Tic Tac Toe or Super Tic Tac Toe) is much more complex - there is no known strategy or algorithm to win (or even to draw) the game. But the game rules are still very simple, so everyone can enjoy it!

Ultimate Tic Tac Toe is played simultaneously on 9 classic Tic Tac Toe boards (called local boards) arranged in a 3x3 grid (called the global board). So in total, there are 81 small squares available for the players. The arrangement is shown below. For illustration purposes, the local board in the upper left corner is highlighted in red and the local board in the center is highlighted in blue.

As in the classic Tic Tac Toe game, players take turns marking small squares on a local board with X’s and O’s respectively. To win a game, a player must win, by the classic Tic Tac Toe rules, three local boards in the same row, column or diagonal on the global board. The local boards won by the X-player are highlighted in blue and those won by the O-player are highlighted in red. In the picture below X-player wins the game by winning three local boards in the middle row of the global board.

What makes the game tricky and fun are the 4 rules dictating which of the 9 local boards is used for the next move. For assistance, the squares available for the next move are highlighted in green.

Rule #1: The X-player makes the first move and can choose any of the 9 local boards for it - so all 81 small squares are green at the beginning.

Rule #2: By marking a small square on a local board a player determines the local board that his/her opponent must use for their next move - this local board should have the same relative position on the global board as the marked square position on the local board. In the example below, X-player selected the top left corner on a local board. That means O-player must play on the top left local board.

Rule #3: If a player wins a classic Tic Tac Toe game on a local board, the board becomes complete and its small squares (even empty ones) cannot be used for subsequent moves. The local boards won by the X-Player are highlighted in blue and those won by the O-Player are highlighted in red. For example, the global board below shows one local board won by the X-Player, one by the O-player, and one tied.

Rule #4: If a local board that a player was sent to by rule #2 is already completed, the player can use any non-completed board. In the example below, the O-player marks the right middle square on the local board in the bottom left corner. By rule #2, the X-player must play on the right middle local board. But this board is already completed! So the X-player can play on any available local board.

That's it! This is a really fun game to play. I have just published a free android app for it. Check it out and enjoy the game!

Tic Tac Toe "Trap"

I wrote my Tic Tac Toe tutorial  mostly for beginners: I thought that the game is simple enough for experienced players to know all the tricks in the book. It turns out that even expert players make mistakes.

Recently I googled "tic tac toe strategies". The very first search result came out as a coveted "featured snippet" and pointed to https://www.instructables.com/id/Winning-tic-tac-toe-strategies. The author of this page shows different fork configurations and classifies winning strategies for the first player (X-player) based on which fork configuration she should try to achieve. You might remember from my tutorial that a fork is a configuration in which a player can win on her next move by marking either one of two free squares. If a player creates a fork and her opponent does not have a way for an immediate win, he will obviously lose (if he blocks one winning square, she will win by marking the other). Here are some examples of forks created by X-player -- the two winning squares are highlighted in gray.

Back to the winning strategies recommended by the web page. "Strategy 1", as the author calls it, is a good one. It starts with a corner move and could really lead to a win if (of course) the second player (O-player) allows X-player to achieve the suggested fork configuration. But the so called "Strategies 3+4", are actually bad ones -- they could lose you a game. Let me explain.  I will follow the author's method of describing moves by numbering the squares of the 3x3 grid.  The author recommends taking squares 4 and 8 first, so that you can subsequently create one of two forks, as shown on the picture.

But the second player has a very effective counter strategy. If X-player starts with 4, O-player should respond with 1. Now if X-player takes 8 (as recommended by the author), she will fall right into a "trap" and deliver O-player an easy win!

Do you see why? I do not want to spoil the fun of finding the solution. But here is an answer, in case you want to compare your solution with mine. Obviously, X-player can avoid this "trap" by not blindly following "Strategies 3+4" on her second move. That is why I put "trap" in quotes.

Similar "traps" exist when X-player tries to setup a fork with different pairs of edge squares. Be careful when you play against the AI in my Tic Tac Toe app - it could "trap" you :-).

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!

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!

3x3 Semi-Magic Squares

Recently I was trying to solve a puzzle involving 3x3 semi-magic squares - 3x3 grids filled with integers 1,2,...,9  in such a way that each cell contains a different integer and the sum of the numbers in each row and each column is the same. It is easy to see that for a 3x3 semi-magic square this sum (sometimes called the magic constant) should be 15. The definition of a semi-magic square does not require (but does not preclude) that the sum of the numbers in each diagonal should also be equal to the magic constant. If that's the case a semi-magic square becomes a magic square. Here are a few examples of 3x3 semi-magic squares. The middle square is not only a semi-magic square, but also a magic square.

I could not find a list of all 3x3 semi-magic squares, so I wrote a little program to generate my own. If you ever need a list of all these squares,  -  here it is, arranged in lexicographical order.

It turned out, there are 72 different 3x3 semi-magic squares. But how "different" are they really? It is easy to see that each of the 8 geometric transformations of a square (identity, 90°, 180°, 270° counterclockwise rotations around the center, reflections across the horizontal axis, the vertical axis, and each diagonal) transforms a semi-magic square into another semi-magic square.

We can therefore split 72 semi-magic squares into 9 non-intersecting equivalency classes. Members of same class are reflections or rotations of each other; members of different classes are not. Below are representatives of each of the 9 classes . Every semi-magic square in a class is a geometric transformation of its representative. All 72 semi-magic squares can be produced out of these 9 by applying geometric transformations. From this perspective there are only 9 "substantially different" semi-magic squares.

But why stop at just geometric transformations? What other transformations turn one semi-magic square into another? Column swaps, row swaps (and sequences of them) do the trick. There are 6 transformations (including identity) done by row permutations and 6 transformations done by column permutations.  The picture below shows the 6 row permutations.

It turns out the 6 row permutations are independent from the 6 column permutations and taken together as sequences of row/column permutations, they constitute 36 different transformations.  Based on this transformation group we can split 72 semi-magic squares into just 2 non-intersecting equivalency classes. Members of the same class are sequences of row/column permutations of each other, members of different classes are not. Here are the 2 classes representatives. All other semi-magic squares are produced out of these two by series of row/column permutations.

Look carefully at the two representatives above... they are reflections of each other across the main diagonal! What does that mean? It means that all 72 semi-magic squares are the result of applying row/columns permutations and geometric transformations to just one semi-magic square. And we a free to choose any one of them as "the one". Let's actually make it a magic square, just for fun!