well I have programmed a connect four which implemented minimax algorithm,but then it took 10 secs(minimum) to reply for maxdepth of 8. More over it still lost few games to online ai's which to my surprise played faster and more accurate than my program.Then by searching in books and internet I came across search funtion called as minimax with alpha-beta pruning.I replaced my minimax with this method but then it plays very bad(doesn't even see the connect 4 even if there are 3 in a row).I am willing to put my source code, pls point out my mistakes and rectify (with explanations if possible). Thank you, and also forgive me for grammatical mistakes(if any) as english is my second language

Alpha-beta pruning shouldn't change the result of the search. You should probably pick a simple position where the program doesn't seem to be doing the right thing and try to debug it. Try using depth 2 or 3 instead of 8 for the debugging, because following a depth-8 search by hand can be hard.

Also, do you understand what alpha-beta does and why it works, or did you simply try to copy some pseudocode you found?

Thanks for the reply,
The main thing to approach alpha beta pruning is that it would allow me to evaluate higher number of depths in less time as compared to minimax. So at higher depths, the mistakes would be calculated and exploited. As of this problem alpha beta pruning is one step ahead. later on i want to learn negascout and more advance searching and evaluating algorithms. So I want to learn Alpha beta pruning.

Here is my source code:

package connect4;
import java.io.*;
import java.util.*;

public class Main {
private static final int WIDTH=7, HEIGHT=6;
private static int MAX_RECURDEPTH=8;
private static BufferedReader in;
private int[][] grid=new int[WIDTH][HEIGHT];
private int[] columnHeight=new int[WIDTH];
private static int recurDepth=0;

static int r=0;

public static void main(String[] args) {
in=new BufferedReader(new InputStreamReader(System.in));
new Main();
}

public Main() {
Scanner read=new Scanner(System.in);
int column,p;
int player=1;
System.out.println("Who play first?");
System.out.println("1.Player");
System.out.println("2.Computer");
p=read.nextInt();
player=p;
double a=-MAX_RECURDEPTH;
double b=MAX_RECURDEPTH;
int move=0;
double value=0;
Vector moves=new Vector();
while(true) {
if(player==1) {
printGrid();
do {
System.out.println("Make your move (1-7): ");
column=readInt()-1;
} while(column<0 || column >=WIDTH || columnHeight[column]>=HEIGHT);
} else {
moves.removeAllElements();
column=0;
value=0;
double prevValue=-MAX_RECURDEPTH-1;

for(int x=0; x<WIDTH; x++)
{

if(columnHeight[x]>=HEIGHT)
continue;


if (move==0)
{
moves.add(new Integer(3));
break;
}
if(p==2 && move==1)
{
moves.add(new Integer(3));
break;
}




value=minmax_ab(2,recurDepth, x,a,b);

if(value>prevValue) {
moves.removeAllElements();
prevValue=value;

}
if(value==prevValue)
{
moves.add(new Integer(x));

}

}

move++;
System.out.println("VAlue="+prevValue);
if(moves.size()>0) {
Collections.shuffle(moves);
column=((Integer)moves.get(0)).intValue();
}
if(moves.size()==0) {
System.out.println("Its a draw.");
break;
}
}
grid[column][columnHeight[column]]=player;
if(player==2)
System.out.println("I PUT MY CHECKER IN "+(column+1));

columnHeight[column]++;
int haswon=0;
haswon=fourInARow();

if(haswon>0) {
printGrid();

if(player==2)
System.out.println("I WON");
else
System.out.println("YOU WON");
break;
}

player=3-player;
}

}


double minmax_ab(int player, int column,int recurDepth,double a,double b) {
double value=0,val=0;
if(columnHeight[column]>=HEIGHT)
return 0;
recurDepth++;
grid[column][columnHeight[column]]=player;
columnHeight[column]++;
if(columnHeight[column]>=HEIGHT)
return 0;
if(fourInARow()>0) {
if(player==2)
value=MAX_RECURDEPTH+1-recurDepth;
else value=-MAX_RECURDEPTH-1+recurDepth;
}
if(player==2)
{
for( column=0;column<WIDTH&&recurDepth<=MAX_RECURDEPTH;column++,recurDepth++)
{
val=minmax_ab(3-player,column,(recurDepth+1),a,b);
if(val<b)
{
b=val;
break;
}
}
return b;
}
if(player==1)
{
for(int x=0;x<WIDTH&&recurDepth<=MAX_RECURDEPTH;column++,recurDepth++)
{
val=minmax_ab(3-player,column,(recurDepth+1),a,b);
if(val>a)
{
a=val;
break;
}

}
return a;
}

value=val;


recurDepth--;
columnHeight[column]--;
grid[column][columnHeight[column]]=0;
return value;
}




int fourInARow() {
int num, player;

for(int y=0; y<HEIGHT; y++) {
num=0; player=0;
for(int x=0; x<WIDTH; x++) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0)
{




return player;


}
}
}

for(int x=0; x<WIDTH; x++) {
num=0; player=0;
for(int y=0; y<HEIGHT; y++) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0) return player;
}
}

for(int xStart=0, yStart=2; xStart<4; ) {
num=0; player=0;
for(int x=xStart, y=yStart; x<WIDTH && y<HEIGHT; x++, y++) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0) return player;
}
if(yStart==0) xStart++;
else yStart--;
}

for(int xStart=0, yStart=3; xStart<4; ) {
num=0; player=0;
for(int x=xStart, y=yStart; x<WIDTH && y>=0; x++, y--) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0) return player;
}
if(yStart==HEIGHT-1) xStart++;
else yStart++;
}
return 0;
}

void printGrid() {
int x=0;
int y=0;

for(y=HEIGHT-1; y>=0; y--)
{
for(x=0; x<WIDTH; x++)
{
if(grid[x][y]==0)
System.out.print(" * ");
else if(grid[x][y]==1)
System.out.print(" A ");
else if(grid[x][y]==2)
{

System.out.print(" B ");


}



}

System.out.println();
}
System.out.println();

System.out.println(" 1 2 3 4 5 6 7 ");




}

int readInt() {
try {
String input=in.readLine();
int number=Integer.parseInt(input);
return number;
} catch(NumberFormatException e) {
return -1;
} catch(IOException e) {
return -1;
}

}
}

You are incrementing recurDepht too many times:
(1) Once in the line that says `recurDepth++;',
(2) again in the loop over moves (probably wrong), and
(3) when you do the recursive call.

Of those, you probably only need (3).

Your code would be much simpler if you used the negamax convention (a positive score is good for the side to move). You would be less likely to make mistakes, like using `column' in the loop when player==2 and using `x' in the loop when player==1. By the way, that last loop looks totally wrong: You initialize x to 0 and you increment column...

There's a few too many mistakes to fix it easily.

[EDIT: I can't figure out what your scores mean. And where is your evaluation function?]

Thanks again for replying.
I have seen negamax(which is not a different algorithm than minimax, its just merged in one function rather than two),but still the issue is speed.
That is why i want to implement ab pruning,it will be very nice of u if help me out with it.

I know perfectly well what negamax is. I am saying that it would be easier to get the code right it you were using it.

I am sorry if i made u angry by my previous post.
Here I tried to implement negamax with ab pruning, it replies very fast, but also make alternate moves at one go(it does not allow player to choose his move. for 5-6 more moves)

Here I tried to implement negamax as you said. But it has some errors,(I must thank you that u have been kind to explain me so much, hope to hear more from u, I really wanna learn these concepts.)


package connect4;
import java.io.*;
import java.util.*;

public class Main {
private static final int WIDTH=7, HEIGHT=6;
private static int MAX_RECURDEPTH=8;
private static BufferedReader in;
private int[][] grid=new int[WIDTH][HEIGHT];
private int[] columnHeight=new int[WIDTH];
private static int recurDepth=0;

static int r=0;

public static void main(String[] args) {
in=new BufferedReader(new InputStreamReader(System.in));
new Main();
}

public Main() {
Scanner read=new Scanner(System.in);
int column,p;
int player=1;
System.out.println("Who play first?");
System.out.println("1.Player");
System.out.println("2.Computer");
p=read.nextInt();
player=p;
double a=-MAX_RECURDEPTH;
double b=MAX_RECURDEPTH;
int move=0;
double value=0;
Vector moves=new Vector();
while(true) {
if(player==1) {
printGrid();
do {
System.out.println("Make your move (1-7): ");
column=readInt()-1;
} while(column<0 || column >=WIDTH || columnHeight[column]>=HEIGHT);
} else {
moves.removeAllElements();
column=0;
value=0;
double prevValue=-MAX_RECURDEPTH-1;

for(int x=0; x<WIDTH; x++)
{

if(columnHeight[x]>=HEIGHT)
continue;


if (move==0)
{
moves.add(new Integer(3));
break;
}
if(p==2 && move==1)
{
moves.add(new Integer(3));
break;
}




value=minmax_ab(2,x,a,b);



if(value>prevValue) {
moves.removeAllElements();
prevValue=value;

}
if(value==prevValue)
{
moves.add(new Integer(x));

}

}

move++;
System.out.println("VAlue="+prevValue);
if(moves.size()>0) {
Collections.shuffle(moves);
column=((Integer)moves.get(0)).intValue();
}
if(moves.size()==0) {
System.out.println("Its a draw.");
break;
}
}
grid[column][columnHeight[column]]=player;
if(player==2)
System.out.println("I PUT MY CHECKER IN "+(column+1));

columnHeight[column]++;
int haswon=0;
haswon=fourInARow();

if(haswon>0) {
printGrid();

if(player==2)
System.out.println("I WON");
else
System.out.println("YOU WON");
break;
}

player=3-player;
}

}


double minmax_ab(int player, int column,double a,double b) {
double value=0;
if(columnHeight[column]>=HEIGHT)
return 0;

grid[column][columnHeight[column]]=player;
columnHeight[column]++;
if(columnHeight[column]>=HEIGHT)
return 0;
recurDepth++;
if(fourInARow()>0) {
if(player==2)
value=MAX_RECURDEPTH+1-recurDepth;
else value=-MAX_RECURDEPTH-1+recurDepth;
}
if(recurDepth<MAX_RECURDEPTH&&value==0)
{

for(int x=0; x<WIDTH; x++)
{
double v=-minmax_ab(3-player,column,-a,-b);
if(v>value)
value=v;
if(v>a)
a=v;

if(a>=b)
return a;
break;

}
return a;


}





recurDepth--;
columnHeight[column]--;
grid[column][columnHeight[column]]=0;
return value;
}




int fourInARow() {
int num, player;

for(int y=0; y<HEIGHT; y++) {
num=0; player=0;
for(int x=0; x<WIDTH; x++) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0)
{




return player;


}
}
}

for(int x=0; x<WIDTH; x++) {
num=0; player=0;
for(int y=0; y<HEIGHT; y++) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0) return player;
}
}

for(int xStart=0, yStart=2; xStart<4; ) {
num=0; player=0;
for(int x=xStart, y=yStart; x<WIDTH && y<HEIGHT; x++, y++) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0) return player;
}
if(yStart==0) xStart++;
else yStart--;
}

for(int xStart=0, yStart=3; xStart<4; ) {
num=0; player=0;
for(int x=xStart, y=yStart; x<WIDTH && y>=0; x++, y--) {
if(grid[x][y]==player) num++;
else { num=1; player=grid[x][y]; }
if(num==4 && player>0) return player;
}
if(yStart==HEIGHT-1) xStart++;
else yStart++;
}
return 0;
}

void printGrid() {
int x=0;
int y=0;

for(y=HEIGHT-1; y>=0; y--)
{
for(x=0; x<WIDTH; x++)
{
if(grid[x][y]==0)
System.out.print(" * ");
else if(grid[x][y]==1)
System.out.print(" A ");
else if(grid[x][y]==2)
{

System.out.print(" B ");


}



}

System.out.println();
}
System.out.println();

System.out.println(" 1 2 3 4 5 6 7 ");




}

int readInt() {
try {
String input=in.readLine();
int number=Integer.parseInt(input);
return number;
} catch(NumberFormatException e) {
return -1;
} catch(IOException e) {
return -1;
}

}
}


And regarding unused variable, I ll remove all such variable later(and avoid creating them from now on.).

Please, post your code within [source] and [/source] tags. You can edit the posts above to add them.

Oh, and I am not angry. I was trying to clarify why I mentioned negamax.

I don't use Java and I don't really know how to run your code. I tried doing

$ javac Main.javaNote: Main.java uses unchecked or unsafe operations.Note: Recompile with -Xlint:unchecked for details.

and then

$ javac Main.java -Xlint:uncheckedMain.java:56: warning: [unchecked] unchecked call to add(E) as a member of the raw type java.util.Vectormoves.add(new Integer(3));         ^Main.java:61: warning: [unchecked] unchecked call to add(E) as a member of the raw type java.util.Vectormoves.add(new Integer(3));         ^Main.java:79: warning: [unchecked] unchecked call to add(E) as a member of the raw type java.util.Vectormoves.add(new Integer(x));         ^3 warnings

Alpha beta is mind-twisting even if you understand it, so it's highly
recommended that you take the time to understand what it's doing.

As a debugging technique, run the search twice, to the same depth, using
the same evaluator, once with your original minmax, and once with alpha-beta.
If they do not return exactly the same result, you still have a bug.

It's handy if the "no cutoffs" option is a permanent feature in your alpha-beta
search anyway, because for some uses you have to run without alpha-beta.
You'll discover those later.

It's very useful to record the entire search tree for a shallow search
and study which nodes in the corresponding alpha-beta search cause cutoffs
until you reach a state of enlightenment.

Thank you for the tip
@ ddyer & @alvaro
I know alpha beta is a bit tedious thing to do(at least for me as I am doing it for the very first time).

Please take a look at this snippet, I think the error is here only,try to rectify it and if possible explain. Which is the best book that I can get which has such types of algorithms and implementations.



Now I don't know what is the problem. Computer plays 5-6 moves for it self and human (I could have made mistakes in some loop or some bracket or break or return but I am not able to make out, Please help)


[Edited by - mandar9589 on August 3, 2009 6:57:35 AM]