Solving Problems with Recursion - Connect 4 AI program
(Page 6 of 10 )
Our last example is creating an AI routine for a connect 4 program. Let's assume you are creating a connect 4 game, and you want to write the routine for the computer player. How do you make the computer think? This is our example.
By the way, the same idea can be used to make an AI routine for nearly any turn based game, be it Tic-Tac-Toe, Connect 4, or even Chess. We will see in a moment what changes need to be made, and why the harder games require more work.
First, for those people who don't know what Connect 4 is, it involves dropping pieces into a board to form a line of of 4 in a row, column or a diagonal. You can find an applet that plays Connect 4 at http://www.bodo.com/Applets/Connect4. I hope this gives you an idea of the game.
What is a good way to make the computer play this game? Here's an idea. Computers are good at enumerating choices, so let's make them do just that. Here is how we will make it work.
First, let's consider this solution. The computer will try to put one of its pieces in each different location. Whatever makes the computer win, it will take it. What do you think of this solution? It is not very good. Why? Because the computer is not planning anything ahead. If the computer is only looking one move ahead, it is just like a man fighting in the dark, a man who can only see his footsteps. He will never be able to beat his opponent. Especially if his opponent can see and plan his moves very carefully.
Here is a better alternative. The computer will try to play a piece in each possible location. For each location, it will also try to put a piece for the opponent in each possible location, and then evaluate the position. It will choose the best position. Now, this is a bit better. The computer is now looking one move ahead.
But why stop here? We can extend this idea like this. The computer will try to place a piece in each possible location. For each location, it will try to put a piece for the opponent, and for each location it will try to place a piece for itself, and so on.
In other words the computer is trying all possible combinations for several moves ahead, and then it chooses the best move.
How should the computer decide the best move? It should assume that both sides are playing their best moves. So, when it tries its own moves, it should take the best move for itself, and when it considers the opponent's move, it should take the worst move for itself. In other words, the best move for the opponent.
Getting complicated? Don't worry, let me explain it in more detail. When I am trying my moves, if I find a really good move, then I certainly will take it. When I am enumerating my opponent's moves, what if I find a really good move for him? He will certainly take it. It is that simple. When you are considering moves, you should take the best move for the side you are trying moves for.
Next: The Minimax Method >>
More Practices Articles
More By Mohamed Saad
/ 32 
AT&T devCentral & BlackBerry(r) Webcast Series: BlackBerry and GPS -Build Location Awareness into your BlackBerry Applications, July 10th -1:00PM EST. 
