Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 15 of 15

Thread: help for connect four with minimax algorithm

  1. #1
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

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


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  3. The Following User Says Thank You to Norm For This Useful Post:

    captain_turkiye (December 12th, 2012)

  4. #3
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: help for connect four with minimax algorithm

    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

  5. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default Re: help for connect four with minimax algorithm

    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.
    If you don't understand my answer, don't ignore it, ask a question.

  6. The Following User Says Thank You to Norm For This Useful Post:

    captain_turkiye (December 12th, 2012)

  7. #5
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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

    	   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

  8. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default 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???
    If you don't understand my answer, don't ignore it, ask a question.

  9. #7
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

    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?

  10. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  11. #9
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: help for connect four with minimax algorithm

    Quote Originally Posted by Norm View Post
    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?

  12. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default 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.
    Last edited by Norm; December 13th, 2012 at 08:55 AM. Reason: added initialize to -99
    If you don't understand my answer, don't ignore it, ask a question.

  13. #11
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

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

  14. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default Re: help for connect four with minimax algorithm

    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.
    If you don't understand my answer, don't ignore it, ask a question.

  15. #13
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: help for connect four with minimax algorithm

    i try to use minimax in this link:

    Extra Credit Algorithm Walkthroughs

  16. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,444
    Thanks
    49
    Thanked 2,218 Times in 2,191 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  17. #15
    Junior Member
    Join Date
    Oct 2011
    Posts
    11
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

Similar Threads

  1. Connect Four FAIL....
    By melinko928 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: October 14th, 2011, 02:10 PM
  2. Simply don't understand minimax...
    By Herah in forum Algorithms & Recursion
    Replies: 3
    Last Post: October 13th, 2011, 12:45 PM
  3. Minimax
    By Scotty in forum Java Theory & Questions
    Replies: 1
    Last Post: May 2nd, 2011, 08:21 AM
  4. CONNECT FOUR GAME-MINIMAX TO ALPHABETA ALGORITHM
    By AJreal in forum Algorithms & Recursion
    Replies: 0
    Last Post: March 6th, 2011, 02:30 PM
  5. Connect 4 involving minimax.
    By mandar9589 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: July 21st, 2009, 10:52 AM

Tags for this Thread