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.