For the evaluation function, you are going to have to identify where threats exist on the board. By "threat" I mean an empty place on the board that is aligned with three pieces of one player, so it the player were to play there he would win. A strong evaluation function needs to know the difference between threats that happen on even and odd rows (with the top row being even), and how multiple threats combine (e.g., player 1 wins with an odd threat, player 2 wins with an even threat, but an odd threat by player 1 beats any number of even threats by player 2). Read
this or buy
the book. You can also give small bonuses for things like controlling squares in the central column.
You also need to be able to search much much further than depth 4. Here are some things that can help:
- You are currently using some simple heuristics to determine what order to use to explore moves in the search (3,4,2,5,1,0,6), but one can do much better than that by using statistics on what moves have produced beta cuts before. You can see how "history heuristic" is used in chess and adapt it for connect 4.
- You then need transposition tables, because in this game it's very easy to reach the same position through different paths, and you want to reuse what you learned when you saw this position before. You can also use the hash tables to store the most promising move, to be searched first when you encounter this position again.
- Instead of doing a fixed-depth search, you should use iterative deepening, where you search depth 1, depth 2, depth 3... until you run out of time. The early searches are not a waste of time because they fill out the hash tables and make the later searches faster. Iterative deepening also allows for proper time control.
That should keep you busy for a while.
