You are not undoing the move when you return early from the function. You could save yourself some problems if you did and undid the move outside of the function. So you wouldn't pass a column to the function, and it would be the caller's responsibility to do and undo the move.
I still don't understand what it is that your function returns. For instance, what does it mean if the function returns 0? Does it mean that the situation seems even? In that case, your program seems to think that you can get a draw by playing on a column that is already full...
And where is your evaluation function?
help in alpha beta pruning
August 03, 2009 08:30 AM
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) { value=MAX_RECURDEPTH+1; for(int x=0; x<WIDTH; x++) { if(columnHeight[x]>=HEIGHT) continue; double v=-minmax_ab(3-player,column,-b,-a); if(value==(MAX_RECURDEPTH+1)) value=v; else if(player==2) { if(v>value) value=v; } else if(v>value) value=v; else if(v>a) a=v; else if(a>=b) return a; break; } } recurDepth--; columnHeight[column]--; grid[column][columnHeight[column]]=0; return value; }I have rectified few mistakes here as I have to replace a,b with -b,-a.
By adding break statement (after return a),computer only plays its move (7 times(maximum number of possible moves) without giving chance to player)
The above code was return in netbeans. Hence if I want to give the .jar file, how should I do it?
This is the first method i can send you.
To compile and run,
Step 1:Save the file in C drive
Step 2:open command prompt
Step 3:write the following code, java -jar "C:\connect4.jar"
To download:
http://rapidshare.com/files/263242215/connect4.jar.html
21,607
August 03, 2009 08:56 AM
Your logic for the variable `value' is tortured. You first initialize it to 0, then to a large number, then you copy the first value returned by a recursive call. Instead of that, you can simply initialize it to `a' and not have any special cases. In fact, you don't need it at all, since `a' can play the same roll.
You still have some confusion between `x' and `column' (definitely a bug).
There is code that depends on the side to move inside the main loop, which doesn't make sense.
Your scoring scale seems to be related with your search depth, which is strange. It makes sense that the score that represents "mate in 5" would be something like MATE_SCORE-5, but there should be space around 0 for heuristic values in positions where you don't see mate.
You check `if(columnHeight[column]>=HEIGHT)' in three places. I am sure you only need it once. Figure out what the right place for it is, and remove the others.
Your break statement after a return will do nothing to help the situation.
I am afraid you are just too far from getting it to work... Perhaps you should improve your programming skills on simpler problems before you can tackle this one.
Perhaps your reference for alpha-beta is not the best. I think you should read Bruce Moreland's chess programming pages.
You still have some confusion between `x' and `column' (definitely a bug).
There is code that depends on the side to move inside the main loop, which doesn't make sense.
Your scoring scale seems to be related with your search depth, which is strange. It makes sense that the score that represents "mate in 5" would be something like MATE_SCORE-5, but there should be space around 0 for heuristic values in positions where you don't see mate.
You check `if(columnHeight[column]>=HEIGHT)' in three places. I am sure you only need it once. Figure out what the right place for it is, and remove the others.
Your break statement after a return will do nothing to help the situation.
I am afraid you are just too far from getting it to work... Perhaps you should improve your programming skills on simpler problems before you can tackle this one.
Perhaps your reference for alpha-beta is not the best. I think you should read Bruce Moreland's chess programming pages.
August 03, 2009 09:31 AM
Sir,If you see the code properly, All the three cases where I have checked heights for columns are for different reasons,also i dont think there is any confusion between column and x as it runs properly when only negamax is used more over this is not a chess program but a simple connect four program which when run in negamax alone runs quiet properly the only trouble faced is it takes lot of time even at depth of 8(round about 10 secs) so I want to speed up this search that is why I am going for alpha-beta pruning. The special cases are according to pseudo code for alpha beta pruning found on internet. The variable value is initialized to maximum possible depth only when there is a forced win (I have to work on score table yet) But this has got nothing to do with ab-pruning if the program works for negamax, it should work for negamax+ab pruning. As I said earlier,programming is only my hobby so I do it in vacations,My college starts from coming monday and that is where I have to stop programing and start studying (electronics)and I don't want to leave this program in between.That is why I am asking help in forum. In short,if I have to replace my negamax with negamax+ab,how should I do it. I am getting stuck (bugs) just to replace the function of negamax with negamax_ab. and this is where I want help.
This is the .jar with only negamax.
Play ,I think its a decent opponent which takes more time to move(and that is exactly where I want ab pruning as i am a beginner programmer in this field).
http://rapidshare.com/files/263257944/connectfour.jar.html
Here is the entire source code (bugged)
This is the .jar with only negamax.
Play ,I think its a decent opponent which takes more time to move(and that is exactly where I want ab pruning as i am a beginner programmer in this field).
http://rapidshare.com/files/263257944/connectfour.jar.html
Here is the entire source code (bugged)
[source lang=java]package connect4;import java.io.*;import java.util.*;public class Connect4 { 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 Connect4(); } public Connect4() { 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) { value=MAX_RECURDEPTH+1; for(int x=0; x<WIDTH; x++) { if(columnHeight[x]>=HEIGHT) continue; double v=-minmax_ab(3-player,column,-b,-a); if(value==(MAX_RECURDEPTH+1)) value=v; else if(player==2) { if(v>value) value=v; } else if(v>value) value=v; else if(v>a) a=v; else if(a>=b) 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; } }}
21,607
August 03, 2009 10:23 AM
Quote: Original post by mandar9589
Sir,If you see the code properly, All the three cases where I have checked heights for columns are for different reasons,also i dont think there is any confusion between column and x as it runs properly when only negamax is used more over this is not a chess program but a simple connect four program [...rest of the rant ommitted]
for(int x=0; x<WIDTH; x++) { if(columnHeight[x]>=HEIGHT) continue; double v=-minmax_ab(3-player,column,-b,-a);Why does it say `column' and not `x' on that last line?
The program you linked to does work, but I haven't seen its code. I bet you used `column' as the loop variable, and you partially changed it to `x' later on.
EDIT: You sent me the code for the non-alpha-beta program in a private message. The equivalent of the lines above says:
for(int x=0; x<WIDTH; x++) { if(columnHeight[x]>=HEIGHT) continue; double v=minmax(3-player, x);At some point you replaced `x' with `column'.
[Edited by - alvaro on August 3, 2009 12:23:31 PM]
August 03, 2009 01:02 PM
I did it but the error is still there.
So now I don't know what to do as things are looking perfect and matches according to pseudo code of ab, perhaps if possible you can modify my code and use ab pruning.
So now I don't know what to do as things are looking perfect and matches according to pseudo code of ab, perhaps if possible you can modify my code and use ab pruning.
August 03, 2009 01:17 PM
Take a look here. http://ce.sharif.edu/~ahmadinejad/gametree/
21,607
August 03, 2009 02:20 PM
Quote: Original post by mandar9589
I did it but the error is still there.
So now I don't know what to do as things are looking perfect and matches according to pseudo code of ab, perhaps if possible you can modify my code and use ab pruning.
Well, that's because that's by far not the only error. I was just trying to point out that you were wrong when you said "i dont think there is any confusion between column and x".
Your biggest problem is that you are not undoing the moves correctly in all the points where you may return from your function. The `break' you added is misplaced and only makes things worse.
Notice that the pseudo-code in the page where you got the alpha-beta algorithm doesn't pass a move to the search function: The caller makes the move and then calls the function. In your case you are not making copies of the board (which is a good thing), so the caller would also need to undo the move immediately after calling the function. That way you can return from any point without worrying about undoing anything.
In C++ you can use destructors to achieve automatic undoing of the move whenever you leave the function, but I am not sure if that mechanism is available in Java.
August 04, 2009 08:16 AM
A question still arises in my mind, if I am following a procedure with negamax, can't I follow it with negamax+ab?. In pure negamax, I have never undid moves nor any reference call or copying board,But it still works. Please help me in this,how should I undo the moves, finalize() is used as destructor in java (somewhat).And please do explain me the exact reason that makes the only negamax code run and not negamax+ab.
-Thank you
-Thank you
21,607
August 04, 2009 09:47 AM
The difference is that once you have alpha-beta (or at least the way you implemented it), you have multiple exit points from your function. You have to be careful to undo the move in all of them, and this is now harder to get right.
You could also change your function so instead of returning on a beta cut you simply break out of the loop and use the move-undoing code and the return statement that you already had.
You could also change your function so instead of returning on a beta cut you simply break out of the loop and use the move-undoing code and the return statement that you already had.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
