Tic-Tac-Toe

A class of games, of which Tic-tac-toe(2,3) is the most popular

Tic-tac-toe(n,k) is played in a discrete n-space. On his turn, a player claims an unclaimed vector of dimension n with each coordinate in the set {1,...,k}. If at the end of his turn the player owns a set of k colinear vectors, that player is declared the winner and the game terminates.

I have hypothesized that if k is less than n+1, then the first player will always win if he is competent.

Tic Tac Toe is commonly known as Noughts and Crosses in the UK and is a clear sign of boredom in lectures.

Apparently it's impossible for the person who goes second to win unless the first player makes a mistake. It's sometimes used as an example in the science behind modelling complex systems.

I now present, for your enjoyment, the Ultimate Tic Tac Toe Strategy Guide:

Tic Tac Toe Theory
First of all, given two players who are fully aware of the repercussions of every move, this game will ALWAYS end in a tie. However, most human players are not that calculating. Presented with a situation where there are no blocks to be made, and no way to move toward completion of a line, you'll often find people who just plop an X or O in any square that suits their fancy. After reading this Ultimate Strategy Guide, you'll be able to beat them silly and assert eternal control over their immortal souls.

Basic theory goes like this: if you have two symbols in a row (for instance, opposite corners, a side and the center, etc), you'll only avoid having it blocked by deliberate stupidity on the part of your opponent. Thus, to win you must set up a situation in which TWO such possibilities simultaneously present themselves. Your opponent can block one, but then you can complete a row, winning the game.

A note about terminology: 'sides' refer to the squares with three bordering lines. 'Corners' are the squares with two bordering lines. The 'center' is the square with four bordering lines.


Tic Tac Toe: First Move
Assume your opponent is smart enough to block any two-symbol line set-ups, but not analyzing enough to premeditate the possible game outcome. If you are playing as X, your best case scenario is a win, and worst case scenario is a tie. As O, you can always force a tie, but winning is going to take some deliberate stupidity on your opponent's part.

If X's first move is... than the best case scenario is...

• Center: Tie if O takes a corner (50%), win if O takes a side (50%).
• Side: Tie if O takes a corner or center (63%), win if O takes a side (37%).
• Corner: Tie if O takes the center (13%), win otherwise (87%).

This demonstrates the possible first moves, and the appropriate white counter.

Tic Tac Toe: The Aftermath
From here, it should be fairly obvious where to go. As X, you're trying to set up a dual-row scenario. Play some 'toe against yourself if you can't figure out how to force the win from a scenario listed as a win. As O, you're trying to prevent a dual-row scenario by forcing X to block you. Again, play some 'toe against yourself if you can't figure out how to force the tie from a scenario listed as a tie. Good luck!

Tic Tac Toe is a rather simple game and is often tackled by many game AI writers (including myself). While it is possible to completely program the entire permutation of the game (as Everything2 Tic Tac Toe has) this is often regarded as the brute force method and very inelegant.

The brute method

There are nine possible first moves, eight possible second moves, seven possible third moves. The total number of theoretically possible games is about 9! (nine factorial) or 362880. While this is obviously not the correct actual number (the game E2-ttt-46 does not use all possible squares), it is in the ball park and gives an idea of the shear volume of the solution space for the game. This is nothing compared to games such as chess or checkers and thus this brute force method is only applicable to small games of perfect knowledge (Tic Tac Toe and Connect 4) which have been solved.

The optimized brute method

How many possible first moves are there in Tic Tac Toe? Nine you say? No - thats not the right answer. The correct answer is three. You can move in the center, corner, or edge. Everything else is just rotations of those first three moves. If this is the only optimization on the brute method we do, we've still reduced the solution space to 1/3 of its original size.

Now, assume the first move was in the center. How many possible second moves are there? The answer isn't eight - but rather two, the corner and the edge. Once again a large reduction in the solution space.

Tic Tac Toe is very rotatable and thus the original third of a million possible games can be reduced into a much smaller tree with rotations of the board. This is also applicable to some of Connect 4 in while it is only played on half a board (only useful in the opening moves).

Crude but efficient

Above, we've looked at how the entire game can be played out and saved resulting in a perfect win or draw each time. While this is what some game theoreticians would like to find for chess, it would make the game rather boring for everyone who understood it. This can be seen in the some of the endgames chess that were previously thought to be draws and instead turn out to be mate in 200 for no understandable heuristic reason and making no sense.

So, how do we look at a game of Tic Tac Toe? What is it about some move that compels us to make some move rather than another? One possible way to play tic tac toe is to assign yourself a value of '1' and your opponent a value of -1. And thus the board found at E2-ttt-12 looks like:

 X | O |     | -1 | 1 | 0  
---+---+---  | ---+---+---
   | O |     |  0 | 1 | 0
---+---+---  | ---+---+---
   | X | X   |  0 |-1 |-1

Now, sum every row, colum and diagonal and take the absolute value.

           1
          /
-1 | 1 | 0  - 0
---+---+---
 0 | 1 | 0  - 1
---+---+---
 0 |-1 |-1  - 2
          \
 |   |   | 1
 1   1   1 

If there is any item that is a '2', the move is to play in the '0'. Period. There are no questions there. This will either result in a win, or a critical block.

Go deep!

What if instead of looking at a table of all the games, you look ahead just a little ways? This is known as a minimax tree and is often used in game AI design.

Instead of looking just at the move we are currently making, look ahead a move or two. If you make this move, your opponent will make a move. The board you want to give to your opponent is the one where he has the weakest best move. Huh? Lets take a game. The first board below is the current game state, and the next two are the possible moves (with rotations).

  current          A             B
 X |   |    |  X |   | O  |  X | O |
---+---+--- | ---+---+--- | ---+---+---
   | O |    |    | O |    |    | O |
---+---+--- | ---+---+--- | ---+---+---
   |   | X  |    |   | X  |    |   | X

Boards A and B both have the same for O, however they are drastically different for X. In board A, X can move and the best move would give X two possible wins and block yours, while board B gives X one possible win and blocks yours. Which is the one you (O) want X to play from? It just takes a bit of looking ahead.

But I know this is better

While tic tac toe doesn't have much that can't be solved handled by anything other than looking ahead, there are games in which different board positions have different weights for movement. In tic tac toe, A play in the center is preferable to a play on the outside. In Othello a play on the corner is best, followed by a play on the edge (other than the spot right next to a corner). These are called 'heuristics' that help an AI play a game intelligently.

In Sweden, this game is played a lot (mostly to kill time during classes). Unlike in the US, we play it with unlimited space (I've filled two pages of drawing paper in ONE GAME with a friend once). Oh, and you need 5 symbols in a row, to make it more unpredictable. The funniest part about it is the name, though. Literally, it translates to Hobo Chess.

Yes, that's its REAL name.