help for connect four with minimax algorithm

• December 12th, 2012, 03:03 PM
captain_turkiye
help for connect four with minimax algorithm
i try to write connect four game with ai. my alpha-beta function should return move(column number) but it always returns 0. also there is another problem, when i remove comments in if states(in min and max) depth goes only 1 level. my control function checks if game finish or not.

Code :

``` public static int[][] Move(int temp[][],int x,int t) { if(temp_heigth[x]>0) { if(t==1) temp[temp_heigth[x]-1][x]=1; else temp[temp_heigth[x]-1][x]=2; temp_heigth[x]--;   } else { //System.out.println("Column is full. Try a new column"); }   return temp; }   public static int AlphaBetaSearch(State state){ state.value = max_value(state,-99999,99999,10); return state.move; }   public static int max_value(State state, int alpha, int beta, int depth){   int t_arr[][] =new int[8][8]; int i,j;   for(i=0;i<8;i++) { for(j=0;j<8;j++) t_arr[i][j]=state.state[i][j]; }   if (depth==0/* || control_state(t_arr)!= 0*/){ return state.value; }   for(int c=1;c<9;c++){ State temp=new State(); temp.move=c; temp.state=Move(t_arr,c-1,2); temp.value = eva_fun(temp.state); state.children.add(temp); } for (State a: state.children){ state.value = Math.max(state.value , min_value(a, alpha, beta, depth-1)); if (state.value >= beta){ return state.value; } alpha = Math.max(alpha, state.value); } return state.value; }   public static int min_value(State state, int alpha, int beta, int depth){   int t_arr[][] =new int[8][8]; int i,j;   for(i=0;i<8;i++) { for(j=0;j<8;j++) t_arr[i][j]=state.state[i][j]; }   if (depth==0 /*|| control_state(t_arr)!= 0*/) return state.value;   for(int c=1;c<9;c++){ State temp=new State(); temp.move=c; temp.state=Move(t_arr,c-1,1); temp.value = eva_fun(temp.state); state.children.add(temp); } for (State a: state.children){ state.value = Math.min(state.value, max_value(a, alpha, beta, depth-1)); if (state.value >= alpha){ return state.value; } beta = Math.min(beta, state.value); } return state.value; }```
• December 12th, 2012, 03:12 PM
Norm
Re: help for connect four with minimax algorithm
Try debugging the code by adding println statements that print out the values of variables used to control the logic. The print out will show you what the computer sees and help you understand what the program is doing so you can fix it.
• December 12th, 2012, 03:56 PM
captain_turkiye
Re: help for connect four with minimax algorithm
when i write this in begining of min function(same in max):

Code :

``` if(depth>-1) System.out.println("depth min: "+depth);```

and write this in alpha-beta before return

Code :

`System.out.println("state value: " + state.value+ " state move: "+state.move);`

i get this output(removed comment in if statement).

depth max: 10
depth min: 9
depth min: 9
depth min: 9
depth min: 9
depth min: 9
depth min: 9
depth min: 9
depth min: 9
state value: 20 state move: 0

output with comments is too long but here last few lines:

depth min: 3
depth max: 2
depth min: 1
depth max: 0
depth min: 1
depth max: 0
depth min: 1
depth max: 0
depth min: 1
depth max: 0
depth min: 1
depth max: 0
depth min: 1
depth max: 0
depth min: 1
depth max: 0
depth min: 1
depth max: 0
state value: 20 state move: 0
• December 12th, 2012, 04:13 PM
Norm
Re: help for connect four with minimax algorithm
Quote:

state move: "+state.move);
Where is the move variable given values? You need to print out each time the variable is changed.
Having the move variable be public will make it harder to add printlns for all changes.
If there were setter and getter methods, there would be one place to add a println.
• December 12th, 2012, 04:41 PM
captain_turkiye
Re: help for connect four with minimax algorithm
i changed my code a little. i think i should return state's. and add println in 3. for in max and min

Code :

``` public static int AlphaBetaSearch(State state){ state.value = max_value(state,-99999,99999,10).value; System.out.println("state value: " + state.value+ " state move: "+state.move); return state.move; }   public static State max_value(State state, int alpha, int beta, int depth){ //if(depth>-1) // System.out.println("depth max: "+depth);   int t_arr[][] =new int[8][8]; int i,j;     for(i=0;i<8;i++) { for(j=0;j<8;j++) t_arr[i][j]=state.state[i][j]; }   if (depth==0 /*||control_state(t_arr)!= 0*/){ return state; }   for(int c=1;c<9;c++){ State temp=new State(); temp.move=c; temp.state=Move(t_arr,c-1,2); temp.value = eva_fun(temp.state); state.children.add(temp); } for (State a: state.children){ state.value = Math.max(state.value , min_value(a, alpha, beta, depth-1).value); System.out.println("max state move:" + state.move); if (state.value >= beta){ return state; } alpha = Math.max(alpha, state.value); } return state; }   public static State min_value(State state, int alpha, int beta, int depth){ //if(depth>-1) //System.out.println("depth min: "+depth);   int t_arr[][] =new int[8][8]; int i,j;     for(i=0;i<8;i++) { for(j=0;j<8;j++) t_arr[i][j]=state.state[i][j]; }   if (depth==0/* || control_state(t_arr)!= 0*/) return state;   for(int c=1;c<9;c++){ State temp=new State(); temp.move=c; temp.state=Move(t_arr,c-1,1); temp.value = eva_fun(temp.state); state.children.add(temp); } for (State a: state.children){ state.value = Math.min(state.value, max_value(a, alpha, beta, depth-1).value); System.out.println("min state move:" + state.move); if (state.value >= alpha){ return state; } beta = Math.min(beta, state.value); } return state; }```

output(last few lines):

max state move:1
min state move:5
max state move:1
min state move:6
max state move:1
min state move:7
max state move:1
min state move:8
max state move:1
min state move:8
max state move:1
min state move:8
max state move:1
min state move:8
max state move:1
min state move:8
max state move:0
state value: 20 state move: 0
• December 12th, 2012, 05:05 PM
Norm
Re: help for connect four with minimax algorithm
Does the printout show you anything? Why is the last value for move set to 0?
The posted code does not show where move is set to 0???
• December 12th, 2012, 05:14 PM
captain_turkiye
Re: help for connect four with minimax algorithm
i think i should return just state, now i lose moves. and i guess i call evalution function in wrong place.

i changed my code in this way, now state value and move are print 0.

Code :

```public static int AlphaBetaSearch(State state){   state = max_value(state,-99999,99999,10); System.out.println("state value: " + state.value+ " state move: "+state.move); return state.move; }   public static State max_value(State state, int alpha, int beta, int depth){ if(depth>-1) System.out.println("depth max: "+depth);   int t_arr[][] =new int[8][8]; int i,j;     for(i=0;i<8;i++) { for(j=0;j<8;j++) t_arr[i][j]=state.state[i][j]; }   if (depth==0/* || control_state(t_arr)!= 0*/) { state.value=eva_fun(state.state); return state; }   for(int c=1;c<9;c++){ State temp=new State(); temp.move=c; temp.state=Move(t_arr,c-1,2); // temp.value = eva_fun(temp.state); state.children.add(temp); } for (State a: state.children){ state.value = Math.max(state.value , min_value(a, alpha, beta, depth-1).value); // System.out.println("max state move:" + state.move); if (state.value >= beta){ return state; } alpha = Math.max(alpha, state.value); } return state; }   public static State min_value(State state, int alpha, int beta, int depth){ if(depth>-1) System.out.println("depth min: "+depth);   int t_arr[][] =new int[8][8]; int i,j;   for(i=0;i<8;i++) { for(j=0;j<8;j++) t_arr[i][j]=state.state[i][j]; }   if (depth==0/* || control_state(t_arr)!= 0*/) { state.value=eva_fun(state.state); return state; }   for(int c=1;c<9;c++){ State temp=new State(); temp.move=c; temp.state=Move(t_arr,c-1,1); // temp.value = eva_fun(temp.state); state.children.add(temp); } for (State a: state.children){ state.value = Math.min(state.value, max_value(a, alpha, beta, depth-1).value); // System.out.println("min state move:" + state.move); if (state.value >= alpha){ return state; } beta = Math.min(beta, state.value); } return state; }```

i'm trying to fix this problem for a week but i couldn't found another solution. how do i fix this code?
• December 12th, 2012, 06:37 PM
Norm
Re: help for connect four with minimax algorithm
For testing you need to post a small program that will compile, execute and show the problem.

Where is the value of move changed? The posted code does not show where its value is set to 0.

What is its default value? Does the code rely on an initial value for move?
• December 13th, 2012, 07:42 AM
captain_turkiye
Re: help for connect four with minimax algorithm
Quote:

Originally Posted by Norm
For testing you need to post a small program that will compile, execute and show the problem.

Where is the value of move changed? The posted code does not show where its value is set to 0.

What is its default value? Does the code rely on an initial value for move?

I do nothing out of these functions. 0's are initial values. in main i only do this:

Code :

```State temp_state = new State(); temp_state.state=board; x=AlphaBetaSearch(temp_state);```

Should i do something else?
• December 13th, 2012, 07:46 AM
Norm
Re: help for connect four with minimax algorithm
If you don't change the value of move then its value will be the initial value of 0,

To see if the code is changing the value of move, initialize it with a different value like -99. Then if it prints out as -99 you'll know that its value has not been changed.
• December 13th, 2012, 12:57 PM
captain_turkiye
Re: help for connect four with minimax algorithm
i initialize move and value with -99 and they print -99. should functions(min and max) returns state or int?
• December 13th, 2012, 01:01 PM
Norm
Re: help for connect four with minimax algorithm
If it prints -99 that would mean that the code does not change its value.

Quote:

should functions(min and max) returns state or int?
I don't know the algorithm or logic for your code and can not recommend changes to what it does.
• December 13th, 2012, 01:15 PM
captain_turkiye
Re: help for connect four with minimax algorithm
i try to use minimax in this link:

Extra Credit Algorithm Walkthroughs
• December 13th, 2012, 01:28 PM
Norm
Re: help for connect four with minimax algorithm
Reading a complicated algorithm and then code is a little more than most of us have the time to do.
• December 13th, 2012, 03:45 PM
captain_turkiye
Re: help for connect four with minimax algorithm
Is there anyone who knew this algorithm already and help me? i thought this algorithm is more popular.