I chose tic tac toe because of its simplicity. There are a maximum of 9 moves, even the lamest computers today can think 9 moves ahead, which means from the time we make our first move, we already know all the possible outcomes of the game. The key to a good AI program, is being able to look at a possible future game state, and assign it a score, higher when in favor or the computer, lower when in favor of the opponent. Because in tic tac toe, we can look 9 moves ahead, it is easy to score the terminal states.
- BAD : For when the opponent won
- OK : When the game ends in a draw
- GOOD : When the computer wind
See, how easy is that. But in a game like chess, for which no computer, (not even deep blue) can fully expand all possible game moves, you would have to assign a score to a board state only part way through the game, which is a VERY difficult thing to do.
OK, now we know why we are using tic tac toe, and not somthing more interesting, lets move on to how we are going to do it.
Each time that the computer needs to make a move, we need to take the current state of the game, and expand it. Looking at all possible moves. This is called our search tree. To see how we grow our tree, look at the Breadth first search section of the first AI article. Now, in the previous AI article, when we were playing a single player game, all we had to do now was to look at all the tips of each branch in the tree, and decide which one we liked best, then look at all the moves needed to get from the initial state, to where we want to be.
HOWEVER, we cannot do that in a 2 player game. Every time the computer makes a move, the human player is going to make a move to try and spoil our efforts, and so we have to take this into account. We do this using a technique called the minni-max method. if you do not understand this dont worry, it will become much much MUCH clearer when we begin to program. Although the theory in 2 player gameing AI is much more complicated, the actual programming is much more simple (because we have no use for heuristics, list sorting, and pointers)
Ok, Like i was saying, the problem is we cannot predict how the human will behave. So basically, we should assume that the human is perfect, and will make the perfect move at each chance. This way, if the human does play perfectly, we will be ready, and if he doesnt, well, all the better for us(the computer player)
Anyway, how do we do this ? First, we look at all the terminal states, and assign each a score, (BAD, OK or GOOD) depending on if that state shows the computer loosing, drawing, or winning. NOW, we look at all other states, If all of that states children have been assigned a score, we can assigned the childrens parent a score. IF the state in question was made by the human, then that state takes the Highest score of all its children, If the state in question was made by the computer player, then it takes the Lowest score of all its children.
Do you see whats happening? a possible move made by a human takes the Highest possible score, and vice versa. this is why its called minni-max (minimum / maximum) (assuming the human, and computer is perfect, in reality, neither may falter giving a draw, but the human may falter, giving the computer a win, however, the computer wil never falter). We keep dooing this untill all states have bee assigned a score, Then, the computer makes the move that it at the top of the tree, and has been assigned the highest score.
Again, if all this has confused you, dont worry, the minni-max is written in 1 if-then-else structure, using only 5 lines of code in total. hehe, like i said, the theory is harder than the implementation.
On the next page, we will start programming
Comments