Connect four AI demo
I made a connect-four game to demonstrate how to make a decent computer AI quite easy.
I've included both the executable (windows) and the source code. It should be quite easy to port it though, because I've put everything non-standard in one file (clrscr) for the user to change.
The AI uses an alpha-beta algorithm (described here). I've made a very simple evaluation function that only tries to move at the middle of the board. The AI would probably be much better if I enhanced the evaluation function, but even now, it's decent.
Please try the program and report any bugs (it didn't take very long to write so there's certainly room for improvement.
EDIT: I managed to forget some header files.
EDIT: Updated version with the possibility to reduce the AI
I tried your game and the AI is very good! I found one bug though, one time when the game had finished I had 8 markers (I was X) on the screen, while the computer had 12 markers on the screen, Ill attach a screenie.
OK, I thought I fixed that bug. It has to do when the player makes an impossible move. It has been fixed now, anyway.
I've also added a very annoying message: When the computer is sure that it will win it'll print a message: Hehe, I'm sure to win.
It is quite annoying :)
It is very easy to change the difficulty of the AI: just change the maxDepth variable in the file AI.cpp.
To change the dimensions of the board and the number of pieces required to win, just change the constants in the Board class. The AI will adapt to the new rules.
I haven't tested this though.
The AI is very good. maybe too good.
is it possible to win?
Connect four is a solved game, i.e. it is always possible to win if you start.
If you'd like an easier game, try reducing the maxDepth variable.
I think I'll implement difficulty levels, hang on...
One thing I'm thinking about is the evaluation function. This function is important to a good AI. However, it must also be very fast, since it's called a lot during the testing of different positions.
Right now, I assing +-100 points to a winning position and otherwise every piece receives a point depending on where on the playfield it is, closer to the center is better:
One small problem with the algorithm is that if the computer sees the game as 'lost', it'll just move a piece at the first available slot.
The problem is that human players aren't perfect. If the player begins, he might unknowingly move so that he has a guaranteed win very far ahead. The computer might then give the player an easy win.
This can be fixed, though. Just return larger values if a winning position is found when 'depth' is low and higher values when 'depth' is high.