ConnectFour A connect four game

The program

This is a little project about searching through a minimax tree for playing a game. Is a java version of an old program I did a lot of years ago, and that in fact, never worked properly.

I have tried to leave the search algorithm independent of the heuristic function in case somebody want to reuse it for other game. Please, tell me if you do. I would like to hear about it.

This version is the first one acceptable. The valid portion of the search tree is maintained between the calls and only the obsolete part is removed. This should allow with little work a background thinking if we launch the explore function in a thread.

It is written completely in java. It is supposed to work in every java implementation, but I have only tried it compiled to native machine code with the GNU gcc. It comes with a makefile for saving you of the dirty compilation process.

The game

For those that do not know it, the game is played in a vertical board, with seven squares width and six heigth. The players drop their pieces in turns and the first that manage to have four in a line will win the game.

The level 2 is acceptable for a normal game. A level over 5 will be very slow for playing confortably.

I have to warn you that this game on the standard board this is a "first-wins" game, which means that the first player will win if performs no errors. The program doesn't play perfectly and is possible to beat it even playing second, but obviously the advantage of the first can be noticed.

To do

Among other things, I will work now in a non-uniformal search, giving priority to the branches with higher heuristic value. Currently the search is by depth levels.

Other future improvement will be the paralel-thinking. The program will be exploring the tree while the human player thinks. This will increase eficiency, or at least will make the game faster.

After this two things, the concept of depth level for the brain loses its meaning. Therefore I want to implement a time-based level, and a time-scheduling algorithm, able to spare time when possible and to spend it when required.

There is also need of a good user interface. I will work on it in paralel with the other things but don't expect too much ... I am an awfull graphics designer.

Finally, the heuristic function can be greatly improved, but the truth is that I do not feel like it. If somebody does it, and wants it included in the project, just tell me.

Of course, everything is under the GPL license

you can download the last version from here

Juan Garcia de Arboleya.