Artificial intelligence in games, part 1

"Chess is not a game. Chess is a well-defined form of computation. You may not be able to work out the answers, but in theory there must be a solution."

- John von Neumann

I'd like to talk about some basic concepts of Artificial Intelligence, by talking about games. In a few posts I'm going to tell you how to play a perfect game of chess. Not just a good strategy, but a perfect strategy. With this strategy, you will always beat a non-perfect opponent. If no win is possible, you will most likely be able to end the game in a draw.

Unfortunately, once I've explained this strategy, you will realize that you can't actually use it. So before I talk about that, I'm going to try something less ambitious. I'll tell you how to teach your computer to play a perfect game of tic-tac-toe, also known as "noughts and crosses" in England.

Here's some quick background for those who don't know how to play. Tic-tac-toe is played on a three-by-three grid. Two players mark their squares, one with the letter "X", the other with the letter "O". Traditionally the X player goes first, and may place a mark on any open square. The players continue to alternate marks until one of two conditions is met. A player can win by placing three of his or her marks in a row -- either horizontally, vertically, or on a diagonal. Much more commonly if the players are experienced, the board will fill up, no player will get three in a row, and the game ends in a draw.

Complexity of tic-tac-toe

How many possible games of tic-tac-toe are there? One way to do it might be to count all possible sequences of moves. The first player has nine possible moves to make. The second player can only go in an unoccupied square, so that's eight moves left. The first player can then go in any of seven remaining squares. And so on, so the number of possible games is at most 9*8*7*6*5*4*3*2*1.

This is a common mathematical operation called a factorial. "9 factorial" is abbreviated as "9!" Factorials are very big. Some algorithms have a running time of O(n!), which can be extremely dangerous -- but I'll get back to that in another post. Luckily, in this case n is only 9, and 9! is a fairly manageable number: It's 362,880.

That seems like a big number to people who are good at thinking in the abstract but bad at storing large amounts of information. However, computers are the opposite, and 362,880 is a very small, manageable number of objects to explore.

It is also an upper bound. We know that there are no MORE than 362,880 possible games of tic-tac-toe, but most of the games resemble each other. Another trick we could apply is to calculate possible states of the board without thinking of moves. Each square can be in one of three states. Either it is empty, or it has an X, or it has an O. Thus, the total number of possible states of the board (legal or not) is 3^9, which is 19,683. So actually, there are no more than this many different ways to set up the board.

In fact, there are even fewer possible states, because many of them aren't legal. For instance, the board could contain all X's, but that's not the state of a real game, because the "O" player never got to move. So there are actually far less than 19,683 states, but all we need is a rough order of magnitude estimate to see how big a problem we have ahead of us.

Calculating all possible games of tic-tac-toe

If you go first in a game of tic-tac-toe, there are nine moves that you can make. The possibilities break down like this:

|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X 

Actually, these nine positions do not really represent unique games. Really, there are three unique moves that you can make: Go in the center, go in a corner, and go on an edge. The rest of the moves simply lead to rotated or mirrored versions of the same games. Some algorithms might take advantage of this similarity and reduce the search space, but for our purposes, it still doesn't take too long to treat all combinations as unique.

Now, if you go in the upper left corner, there are eight moves that the "O" player could make. Here are a few.

|  X | O |       X |   | O     X |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |       O |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

Again, these do not represent unique games. For all practical purposes, the first move and the third move are the same game. But it's easier to program (though slower to run) if you don't bother trying to analyze the games.

In the next post, I'll explain how we can use this system for categorizing every possible game to write an unbeatable opponent.