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 | 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.