help for connect four with minimax algorithm

[captain_turkiye]

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.

	   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;
	    }

[Norm]

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.

[captain_turkiye]

when i write this in begining of min function(same in max):

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

and write this in alpha-beta before return

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

[Norm]

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.

[captain_turkiye]

i changed my code a little. i think i should return state's. and add println in 3. for in max and min

	   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

[Norm]

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???

[captain_turkiye]

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.

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?

[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?

[captain_turkiye]

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:

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

Should i do something else?

[Norm]

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.

[captain_turkiye]

i initialize move and value with -99 and they print -99. should functions(min and max) returns state or int?

[Norm]

If it prints -99 that would mean that the code does not change its value.

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.

[captain_turkiye]

i try to use minimax in this link:

Extra Credit Algorithm Walkthroughs

[Norm]

Reading a complicated algorithm and then code is a little more than most of us have the time to do.

[captain_turkiye]

Is there anyone who knew this algorithm already and help me? i thought this algorithm is more popular.