Hello again every one.
After a break I have started to program my connect four again.
The AI now searches 14-plys deeper in matter of 5 seconds on empty board and playing first(Comment on the speed,as it wud help me to understand if its fast or not).
I have programed Negamax+AB+ hashtables and killermove heuristics. My primitive version only included the winning conditions but however now since its not enough to contain that only, I would like to make it a bit more stronger by putting some favourable conditions,like odd and even threats.
Here is what I have done:
int threat_at_2 = 60;
int threat_at_3 = 50;
int threat_at_4 = 20;
int threat_at_5 = 10;
int threat_at_6 = 5;

for (column = 0; column < 4; column++) {
row = 4;
if (posn[row][column] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'o')
{
weighto += threat_at_2;
}
if (posn[row][column + 1] == '1' &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == posn[row][column] &&
posn[row][column + 3] == 'o') {
weighto += threat_at_2;
}
if (posn[row][column + 2] == '1' &&
posn[row][column + 1] == posn[row][column] &&
posn[row][column] == posn[row][column + 3] &&
posn[row][column + 3] == 'o') {
weighto += threat_at_2;
}
if (posn[row][column + 3] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column] &&
posn[row][column] == 'o') {
weighto += threat_at_2;
}

row = 3;
if (posn[row][column] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weightx += threat_at_3;
}
if (posn[row][column + 1] == '1' &&
posn[row][column] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weightx += threat_at_3;
}
if (posn[row][column + 2] == '1' &&
posn[row][column + 1] == posn[row][column] &&
posn[row][column] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weightx += threat_at_3;
}
if (posn[row][column + 3] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column] &&
posn[row][column] == 'x') {
weightx += threat_at_3;
}

row = 2;
if (posn[row][column] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'o') {
weighto += threat_at_4;
}
if (posn[row][column + 1] == '1' &&
posn[row][column] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'o') {
weighto += threat_at_4;
}
if (posn[row][column + 2] == '1' &&
posn[row][column + 1] == posn[row][column] &&
posn[row][column] == posn[row][column + 3] &&
posn[row][column + 3] == 'o') {
weighto += threat_at_4;
}
if (posn[row][column + 3] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column] &&
posn[row][column] == 'o') {
weighto += threat_at_4;
}
row = 1;
if (posn[row][column] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weightx += threat_at_5;
}
if (posn[row][column + 1] == '1' &&
posn[row][column] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weightx += threat_at_5;
}
if (posn[row][column + 2] == '1' &&
posn[row][column + 1] == posn[row][column] &&
posn[row][column] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weightx += threat_at_5;
}
if (posn[row][column + 3] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column] &&
posn[row][column] == 'x') {
weightx += threat_at_5;
}
row = 0;
if (posn[row][column] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weighto += threat_at_6;
}
if (posn[row][column + 1] == '1' &&
posn[row][column] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weighto += threat_at_6;
}
if (posn[row][column + 2] == '1' &&
posn[row][column + 1] == posn[row][column] &&
posn[row][column] == posn[row][column + 3] &&
posn[row][column + 3] == 'x') {
weighto += threat_at_6;
}
if (posn[row][column + 3] == '1' &&
posn[row][column + 1] == posn[row][column + 2] &&
posn[row][column + 2] == posn[row][column]&&
posn[row][column] == 'x') {
weighto += threat_at_6;
}
}
weight=weightx-weighto;
return whotomove?weight:-weight;

The above code contains only the horizontal threats(one blank and three of same color on one horizontal row.)
I just want to ask whether I am on right track or not.

Please give me some more pointers (pseudo code wud be a lot helpful, some real code of any data-struct will be very help ful.) to improve the eval and further cut down the number of nodes.

PS:The idea is to learn to program ai and slightly difficult game before moving onto reversi. The point is to learn algorithms related to AI board games and implement them, also learn to write evaluation methods.
The goal as of now is to make a real difficult connect4(It might happen that this program would play perfect with odd-even rules and later on some addition of parity(I have not thought of parity yet.))
-TYIA

Hello again every one.
After a break I have started to program my connect four again.
The AI now searches 14-plys deeper in matter of 5 seconds on empty board and playing first(Comment on the speed,as it wud help me to understand if its fast or not).
I have programed Negamax+AB+ hashtables and killermove heuristics. My primitive version only included the winning conditions but however now since its not enough to contain that only, I would like to make it a bit more stronger by putting some favourable conditions,like odd and even threats.

14-plys deeper than what? 14 plys in 5 seconds sounds reasonable. There is probably room for improvement in the search (history heuristic can be very effective for this game, for instance), but you will get much more improvement in the quality of play by improving the evaluation function.

[...] The above code contains only the horizontal threats(one blank and three of same color on one horizontal row.)
I just want to ask whether I am on right track or not.[/quote]


You should probably first learn much more about how to play the game. The two people who solved the game in 1988 also produced great resources:
* From James Allen: http://homepages.cwi.nl/~tromp/c4.html
* From Victor Allis: http://www.connectfo...es/connect4.pdf (start reading at section 3)

John Tromp has a program that solves the game in about 5 minutes on my computer. The code for this program and a bunch of interesting information about the game (including some tricks to write really fast code using bitboards and a Java applet that plays perfectly) can be found here: http://homepages.cwi...romp/c4/c4.html

@Alvaro:
Thank you for replying.
If you have some free time then would you mind to program ur connect 4 and then we can have a match between them.
I know there are plenty of online games, but however these programs donot have knowledge based evaluations.
-TYIA

It's not really looking like I am going to have a whole lot of free time in the next few months, but I'll be happy to play against your program myself. I am a pretty good player...

@Alvaro:
Thank you for replying and taking interest in my queries.
I will find some free web server and upload it as it is, I have programed in java so it wudnt take much of time for me to code the gui.
will do it in couple of days.
kindly give feedback on strengths and weakness of the program.
Thank you.

Hi again, I am trying to develop some gui for my game,but its slightly more tedious than I thought,
How ever on other hand, I am also working on my algorithms and other node pruning techniques.
I have visited many programing AI webistes(Most common chess wiki).But then many algorithms used for node pruning are domain(game) dependent.
For example,While using Null-Move Heuristics in chess can be of big advantage, it is not possible to use in connect 4 as the odd-even square have their own advantages and disadvantage(Parity is important factor in connect 4).
I read the paper on Prob-Cut implemented in othello as again Null-Move is not valid in Othello and checkers.
So Even I tried to implement the Prob-Cut algo and here is what I wrote.
if(depth==d)
{
long bound;
//v_d>beta likely to cause cutoff: cutoff=yes.
bound=Math.round((t*sigma+beta-/a);
if(-Negamax_ab(!turn,s, board1, bound-1, bound)>=bound)
{
// System.out.println("Prob Beta Cut");
return beta;
}
//v_d<=alpha likely to cause cutoff: cutoff=yes.
bound=Math.round((-t*sigma+alpha-/a);
if(-Negamax_ab(!turn,s, board1, bound, bound+1)<=bound)
{
//System.out.println("Prob Alpha Cut");
return alpha;
}

}
There are fewthings which I want to verify.

• Is this algorithm useful in game like connect 4?
• Is my implementation correct?
• Is there any formula for adjustment of a,b,sigma and t. If yes kindly mention it, If no then how to calculate it.
• What is the speed that we get if this algorithm is implemented in connect-4 correctly?
  I will give a download link for my application in my next post.
  TYIA

Prob-cut is not a must-have algorithm for any game, as far as I know. Some programs might see a modest improvement, some won't. I think you should probably concentrate on developing a very strong evaluation function instead.

You should also probably have a quiescence search of sorts, where you basically don't allow yourself to stop the search if there is a threat that you can play at (either to win the game or to stop the opponent from playing there). When I wrote my connect-4 program, I actually made it so that playing on threats are the only moves that the program would consider, if there is one available. Moving under an opponent's threat was not considered a candidate move. I also extended the search by one ply if there was only one candidate move. Your program can probably gain some tactical strength with this type of search modification.

I'll be happy to play against your program using a text interface.

@Alvaro: Thanks for replying.
I apologize for delay in replying,I was too busy with schedule,but now again I am having some free time.
I have added few more threats and configurations.
Also tried to make a primitive book, but then its a vast job for completion.
Now the program takes around 15-20 secs (depending on machine) to compute a move.
I have kept the default depth as 14.
How ever, the depth can be changed.
Also since its good to do selective search, can you suggest any method for the same?
I implemented Prob-Cut but then I am not quiet sure how to do the linear regression, can you help me with it, the formulas are direct but some how I dont know what data to collect in order to sustitute in the formula.
Null move pruning is not feasible as zugzwangs are predominant in connect4.
What about other techniques if any.
Kindly reply and comment on my game strength.
All you have to do is download the file from link below and later on run through command prompt(Assuming you are using windows),follow the steps:
-Save the .jar file in some suitable location.
-type the following: java -jar"(Absolute path)"
Download

Forget about Prob-Cut. I really don't think you are going to get much from it, and it's complicated.

You should implement iterative deepening, which will have the added benefit of enabling you to do proper time control. If your hash tables are implemented correctly, you should gain speed from this. If not, fix your hash tables.

Did you explore using some variation of history heuristic? Some of them work really well for this game.

@Alvaro: I think killer heuristics is variation of history heuristics.
I am struggling bit with iterative deepening, I have implemented
getMove()
{
for(...)
{
try moves
eval=-negamax(...)
if(eval>...)
index=moves;
return index;
}

So for this I am stuck where as to call the timesUp() method. and how many times as there are move evaluation in getMove as well as in negamax().
Will work this out.
As far as I know my hashtables doesnt show any bug, is there any specific test which I should perform to test hashtables?
Also do let me know the result of your matches against the program and its weakness and strengths.