AI: Connect 4 Game

I have been kinda slow in posting these last couple of weeks. One of the reasons is of course that I've been busy coding (as always). This time however, it's actually real homework thats been keeping me busy.

In the AI course I'm taking at ITU we were assigned the task of making our own version of "Connect 4" - the well known board game where you drop coins into a board from the top and try to get four in a row, horizontally, vertically or diagonally - and preferably before your opponent.

I know that this game has already been "solved" and there exist a perfect solution for it. But nevertheless it's still interesting to make an algorithm that calculates the computers move.

In order to do this I've used a variant of the MiniMax algorithm, optimized with Alpha/Beta pruning. The basic idea is to search through a tree of possible actions and thereby thinking ahead to find the best possible action in order to go from an initial state to a goal state (win).
A state would typically consist of current game-board, and who's turn it is. From a state there's often 7 possible actions - each of the columns that it's possible to choose. If a column is full the number of possible actions decrease.
So, in theory, every time it's the computers time to move we would like to build a tree, starting at the initial (current) state and then branching out with the possible actions. Each of the possible actions will lead to a new node, that indicates the opponents move. The opponent again have a number of possible actions, and we assume that he will always pick the action that is best for him (= worst for us, the computer). This means that we can build a double-recursive method to traverse this tree, taking turns choosing the action with the maximum and minimum outcomes for us and thereby in the end evaluate which of the current actions available to us is the best (= where it's most likely we will win, even if the opponent does his best to screw it up).

If you haven't played around with algorithms like this before it might sound kinda complicated but it's really just applying the same method as most of us do in our heads when playing a game like this: "So, let me see.....if I select this column, then he will most likely select that column which means that I'm certain to win in the following move". However, where as humans often have difficulty thinking more than a couple of moves ahead, computers often have a better chance.

But there's one catch: Even with a game as simple as Connect 4, thinking several moves ahead scales terrible. Except for when the columns starts to fill up, there's 7 possible actions. For each of these actions the opponent can again choose 7 actions bringing us up to 7^2 (=49) states we need to consider. I've found that a typical game of Connect 4 often goes to at least 30 moves before a winner is found, meaning that we would have to examine something like 7^30 (=22539340290692258087863249) states. Of course Alpha-Beta pruning can help a lot on that, but in the end it'll still be too much to calculate in reasonable time.
Thats why it's a bit of a modified Minimax with AB pruning algorithm I use.
Instead of searching all states till it reaches a terminal state it will search until it reaches a certain cut-off depth. At that time it will apply some heuristic evaluation to the cut-off states to determine how close it is to winning in those states.
By experimentation I've so far found that to think 6-7 moves ahead makes the most sense performance wise. Perhaps even 8 will be a possibility if I optimize some more and allow the computer more time to think for each move.
The trick to achieving success even after "only" thinking 6 moves ahead is to have a good evaluation function that gives an accurate impression of how well the computer is doing compared to the player. I seem to have found one that works pretty well (so far only one of my friends have reported to have beat the computer once). The details of the evaluation function, along with code for the rest of my project you'll have to wait for until the project is officially handed in (there's going to be a computer vs computer contest in my class - not unlike the poker robot tournament I'm working on).

As for now, you can try out my game here! You always get to start first, you are red computer is blue. (And yes, I realize there are a couple of bugs still - no need to report them I'm working to fix them).