Connect Four
If this applet fails to load, try updating java at

(1) Choose Red Player (Human/Computer)
(2) Choose Black Player (Human/Computer)
(3) Set any Computer Player difficulty levels
(4) Start Game. Good luck.

I worked on this project for about a year and a half off and on through my freshman year and summer. The data structure has been rewritten about 4 times and I most recently reworked the entire applet structure. It now uses a better layout and has a more professional code style, which makes it easy to change. When I stopped working on it I had finally solved the horizon problem (with the exception of one case, try to find it) and surprisingly I used the solution to increase the algorithm's efficiency in the end game play.

When I first wrote it, the game tree was only recursed 3ply, badly, in about a minute. Now it projects the game tree to 10ply and beyond in less than five seconds for a standard board and in about a minute for larger boards (This is dependent on the speed of your machine as well). This is accomplished with alpha-beta pruning amoung other pruning techniques to reduce the search space, as well as an extrememly efficient non-trivial evaluation method that was implemented based on some heuristic graph theory.

A revision I am thinking about right now, but am having trouble with, is making a more aggressive AI. The current one is shy, playing very defensively because it literally overestimates its human opponants, an unfortunate bi-product of minimax. It would be fun to see how an aggressive AI plays and how one might create it. Other ideas include amortizing the game search. The problem is that it is difficult to predict the cost/benefit due to the already strong (and more necessary) alpha-beta pruning. Also, in Connect Four "theory", there is a parity of the board, which I did not account for in this version of the evaluation method, the board's datastructure prohibits this trivially. Integrating this parity may improve its chances of winning by Zugzwang in some of the lower difficulties. Finally, I'd like to port this algorithm and structure to Checkers, just need inspiration. If you have any suggestions for improvements, e-mail me!