Thread: 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.

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

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

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

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?

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:

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

Should i do something else?

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

i try to use minimax in this link:

Extra Credit Algorithm Walkthroughs

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