Alpha beta pruning with negamax

[Kabir Shah]

The code below is written for connect four (plot four).This is not my home work. My hobby is programming so I am doing it.It works perfectly fine when ab pruning is not used,but has one draw back that is it takes lot of time to execute move.

  package connectfour; import java.io.*; 
import java.util.*; 
 public class Connect4 {    
 private static final int WIDTH=7, HEIGHT=6;  
   private static final 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 double 
a=-MAX_RECURDEPTH,b=MAX_RECURDEPTH;     
   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;      
   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(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(int player, int column,double a,double b) 
{  
       double value=0,v=0;  
       if(columnHeight[column]>=HEIGHT)      
       return 0;     
    recurDepth++;     
    grid[column][columnHeight[column]]=player;  
       columnHeight[column]++;  
        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;           
       v=-minmax(3-player, x,-b,-a);                       
                              if(value==(MAX_RECURDEPTH+1))      
               value=v;           
      else if(player==2)     
            {          
           if(value>v)   
 
                     value=v;    
              }          
       else if (v>value)               
           value=v;                 
     if(v>a)        
         {                 
        a=v;               
   }             
   else if(a>=b)      
             break;    
                         }     
    }      
    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;         }   
   } 
}


  

This is the entire code for connectfour using negamax+ab pruning. But it is not working. I think I have made mistake in
the if else if loop of minmax().


The code executes perfectly but then it doesn't even see win for the player,nor forces a quick win (even if it is possible) for it self


please forgive me for grammatical mistake as English is my second language.

[Fred Hamilton]

I didn't try to figure out your code, but I'm in the middle of implementing a recursive negamax algorithm with my chess program. Here is the pseudocode for the negamax part of things. If we can see eye to eye on this, then I'll add in the alphabeta pruning, and hopefully this might help you with your program.

public Move makeMove() {
	ply = n;
	fen = arbitrary starting position and game state;

	list1 = possiblesMoves(fen);	// possibleMoves is non recursive.
	max = -10,000;					// initial value is lower than any possible eval

	for each move m in list1 {
		fen1 = position after m
		m.eval = evaluate(m, ply)
		if( m.eval > max ) max = m.eval
	}

	return random selection from moves where eval = max.
}

private int evaluate( fen1, ply ) {			// evaluate is recursive function.

	if( ply == 1) return material eval of fen1, including quiescence.
	
	max = -10,000;

	list2 = possibleMoves( fen1 );
	for each move m in list2 {
		fen2 = posn after m;
		m.eval = evaluate( fen2, ply-1 );		// recursion step.
		if( m.eval > max ) max = m.eval;
	}
	
	return -max;								// why we call it negamax
}

[Kabir Shah]

Thanks for the code mate.

  double minmax(int player, int column,double a, double b) {
        double value=0;
        if(columnHeight[column]>=HEIGHT)
            return 0;
        recurDepth++;
        grid[column][columnHeight[column]]=player;
        columnHeight[column]++;

        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);
            double v=0;
            for(int x=0; x<WIDTH; x++) {
                if(columnHeight[x]>=HEIGHT)
                    continue;
                 v=-minmax(3-player, x,-b,-a);
                if(v>value)
                    value=v;
                if(v>a)
                    a=v;
                if(a>=b)
                    return a;

                if(value==(MAX_RECURDEPTH+1))
                    value=v;
                
                                    
                

            }
           
        }

        recurDepth--;
        columnHeight[column]--;
        grid[column][columnHeight[column]]=0;

        return value;
    }
  

Here is my only negamax + ab pruning code, it contains many bugs which i am not able to debug. I have tried it many a time but still failed, so I am posting it here

[Fred Hamilton]

You say that things work just fine without the abp code, just slowly, which is to be expected. It is worth noting that abp should not change your final choice of a move, just speed up the process.

The following page is a good resource for negamax and alpha-beta pruning. It's a chess page, but the algorithms are the same.

http://www.frayn.net/beowulf/theory.html

Also, give some thought to implementing some kind of a trace which will print to the console the various tree paths and their evals, and also which tree branches were pruned and why.

I am very interested in the topic, but I don't find it easy. If you can help me out by specifying exactly which lines of your code are responsible for the abp pruning, and a word or two about how you expect it to work, then I will give it my best shot to understand the problems.

[Kabir Shah]

@fred
I am very thankful to you for your replies.
I have implemented this code for connect four AI. it plays decently(beat few online bots and lost to few online bots.. thts pretty good when novice programmer like me has programmed it) The only thing is that,it takes lots of time to execute the move(at depth of 8 its 10 secs approx).and hence I want ab along with negamax,so that i can speed up the process and raise the depth to a higher value than 8 to make it play stronger.

So to describe my program I will write few word for the methods which are there.
I have two variables value and prevalue, value stores the current value while prevalue stores the previous value. Now they are compared, if value>prevalue, then prevalue stores the value (i.e its current score) and for column having the highest prevalue, checker is put in to it.(I have not written the score function yet.. I will do it , but i guess it has nothing to do with ab pruning)

Here is the code:

 value=minmax(p,x,a,b);  
     
                       if(value>prevValue) {  
                            moves.removeAllElements();  
                            prevValue=value;  
      
                        }  
                        if(value==prevValue)  
                        {  
                           moves.add(new Integer(x));  
   
                    }     

where moves is a vector

Now come the method of minmax(same as negamax+ab in this program).
it has 4 parameters.
1.playe whose turn it is to move
2.column which is to be iterated
3.alpha (variable a) which is initialized as -MAX_RECURDEPTH.
4.beta (variable b) which is intializes as MAX_RECURDEPTH .

According to me I have made mistake in if's .
More over if write return a then it plays 3-4 moves and not allowing the user to play.
if I don't write it (i replace with break) then it does not even see the victory for itself or the player(even if there are 3 in format,horizontal,vertical,diagonal).
Here is code for if's

   if(v>value)  
                      value=v;  
                 if(v>a)  
                    a=v;  
                  if(a>=b)  
                        return a;  

I want the ab pruning to behave in same way as that of negamax but eliminating the useless nodes.
here is the code for negamax+ab pruning.

 package connect4;
import java.io.*;
import java.util.*;

public class Main  {
    private static final int WIDTH=7, HEIGHT=6;
    private static final 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 a=-(MAX_RECURDEPTH+1);
    static int b=MAX_RECURDEPTH+1;

    public static void main(String[] args) {
        in=new BufferedReader(new InputStreamReader(System.in));
        new Main();
    }

    public Main() {
        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;
        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(p,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(int player, int column,double a, double b) {
        double value=0;
        if(columnHeight[column]>=HEIGHT)
            return 0;
        recurDepth++;
        grid[column][columnHeight[column]]=player;
        columnHeight[column]++;

        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(3-player, x,-b,-a);
                if(v>value)
                    value=v;
                if(v>a)
                    a=v;
                if(a>=b)
                    return a;

                if(value==(MAX_RECURDEPTH+1))
                    value=v;
                
                                    
                

            }
           
        }

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

    }
}
   

I would definitely like to help you in chess(I am chess player my self),But as of now ,I am not on that level of programming chess, so step by step i would like to learn

[Fred Hamilton]

ok bud, you are welcome. Like I said I am interested in the topic, so I will learn something useful here too. I should be able to reply by this time tomorrow. In the mean time I'll keep an eye on the thread in case someone else solves it.

And sure, we can talk about the chess later too., I'm not a guru, the negamax/abp algorithm is pretty much the same from game to game.

[Kabir Shah]

Thanks once again, I will wait for your reply which will hopefully solve my problem.

[Fred Hamilton]

I don't think we are on the same page as to what some of this stuff actually means.

OK we agree on the purpose of alphabeta pruning does. It eliminates nodes and subsequent tree creation and evaluation based on the findings of negamax, negamax tells us the nodes won't influence the final evaluation, alhabeta pruning actually does something about that.

What do you mean about not having written a score function yet. What do you mean by a score function. I don't see how you can even have negamax without a way to evaluate the end points of the tree.

... Now come the method of minmax(same as negamax+ab in this program).

I'm not sure why you are talking about it. I see minmax as a different way of traversing the game tree, as is negamax, so I don't see minmax and negamax as co-existing in the same algorithm. Furthermore. I see ab pruning as being something that can be added to negamax and minmax to speed things up. Do you agree?

I want the ab pruning to behave in same way as that of negamax

OK, are you saying that you want abp to work with minmax the same way it works with negamax? That would make sense. Except I still don't know why you are talking about minmax. Like I said, to me it's one or the other
. Either you have minmax or negamax. agreed?

Please have a look at my pseudocode. Do you understand it, do you condider it to be correct, and does it conform to your understanding of negamax, without the abp?

[Kabir Shah]

I think there is confusion here the name of function is minmax,but it is written in negamax fuction.. so to refer it by name, i I think the pseudo code that you wrote helped me but that is not the way in which I have written my negamax function. If you look at my code then you will find the variable preValue which stores the highest score. If it has connect in four then it straight away displays the (MAX_RECURDEPTH-prevalue) as score to win,for all rest till it does not find win it displays score as zero. By writing a score function, I mean it evaluates each position and then shows up like for example if computer has a slightly better position then it shows 0.24 or something like that, this is what I have not written as of now. As my code is working without the score function.(just now I tried to explain you what score function means in my program.)implementing the only negamax code, it should work with negamax+abp as well.
The reason I think that it does not work is in either the if's or in the return a rest I think there is no problem(as I have not modified my original negamax code which is fully working so trying to work there, please help me if you find the correct code or correct sequence of coding)
I think the confusion is being cleared of minmax and negamax. so to end with confusion I will give an short example:
even if you call rose as lily, it will still remain rose. In same way I have named negamax as minmax, but still it will be negamax.
Need your help.
Thank you.

[Fred Hamilton]

Gurudas Bhandarkar wrote:I think there is confusion here the name of function is minmax,but it is written in negamax fuction.. so to refer it by name, i I think the pseudo code that you wrote helped me but that is not the way in which I have written my negamax function. If you look at my code then you will find the variable preValue which stores the highest score. If it has connect in four then it straight away displays the (MAX_RECURDEPTH-prevalue) as score to win,for all rest till it does not find win it displays score as zero. By writing a score function, I mean it evaluates each position and then shows up like for example if computer has a slightly better position then it shows 0.24 or something like that, this is what I have not written as of now. As my code is working without the score function.(just now I tried to explain you what score function means in my program.)implementing the only negamax code, it should work with negamax+abp as well.
The reason I think that it does not work is in either the if's or in the return a rest I think there is no problem(as I have not modified my original negamax code which is fully working so trying to work there, please help me if you find the correct code or correct sequence of coding)
I think the confusion is being cleared of minmax and negamax. so to end with confusion I will give an short example:
even if you call rose as lily, it will still remain rose. In same way I have named negamax as minmax, but still it will be negamax.
Need your help.
Thank you.

my algorithm does pretty much the same thing, in that it stores the highest value in max. For now it only does that to so I won't have to find the maximum when it comes time to actually select the move. When I add in my abp, it will be comparing the max to the evals of the replies of the opponent As I see it what your code does when it finds a connect4 is technically not a part of negamax. It's almost like a simplified abp, you see what I mean?

Anyways, you have cleared up my misunderstanding about terminology, so now I will look closely at your code and try to reply by the end of the day

[Kabir Shah]

@Fred.
I will be very thankful to you.

[Fred Hamilton]

ok bud, I figure before I tried to tell you how to do yours, I should get mine working, so here is my recursive negamax with alpha - beta pruning. You can test drive it at the link in my signature. My head is spinning, so I will probably take the rest of the night off before I tackle your code. I'll be happy to answer any questions you have on my code. You will notice this is incomplete code, but the methods themselves are complete. p.s. it is worth noting that alpha-beta pruning reduced my search time by about 50%

// This method is called by the GUI when it wants the engine to make a move.

public Move makeMove( String pStr, int ply ) {

	pList = new ArrayList<String>();

	// possibleMoves is a non-recursive method that returns a list of possible moves
	CMove[] list1 = possibleMoves( pStr ); 

	// if the list is length == 0, the engine is in checkmate or stalemate.
	if( list1.length == 0 ) {
		Boolean white = ( pStr.charAt(64) == 'w' );
		if( inCheck( pStr ) ) return new Move( "Checkmate", false );
		else return new Move("Stalemate", false );
	}
	
	// if the list is length == 1, it makes the move without evaluation
	if( list1.length == 1 ) {
		return new Move( pStr.charAt(list1[0].i), list1[0], "forced" );
	}
	
	// the maximum eval is seeded with an impossible low value, guaranteeing that
	// the eval for the first move will be registered, no matter how bad it is.
	int maxVal = -5000;
	
	for( CMove cm1 : list1 ) {
	
		// each move is evaluated recursively using the negamax algorithm.
		// we pass the maximum eval which is required for abp to work.
		cm1.eval = evaluate( cm1.pStr, ply, maxVal );

		// we keep track of the maxVal for the final evaluation
		// this is not alpha=beta pruning.
		if( cm1.eval > maxVal ) maxVal = cm1.eval;
	}
	

	ArrayList<CMove> list2 = new ArrayList<CMove>();
	
	// extract the moves whose eval == maximum
	for( CMove cm1 : list1 ) {
		if( cm1.eval == maxVal ) list2.add(cm1);
	}

	// select randomly from the list of moves that have the maximum eval.
	int select = rand.nextInt( list2.size() );
	CMove cm = list2.get(select);
	
	return new Move( pStr.charAt(cm.i), cm, "normal" );
}

/*********************************************************************************/

// this is the recursive method which forms the basis of the negamax algorithm
// the alpha beta pruning is basically implemented with one line of code.
// pStr is a string which represents the position being evaluated.

private int evaluate( String pStr, int ply, int maxEval ) {

	if( ply == 1 ) return quiesce( pStr, ply );    // end condition for recursion
	
	int eval;
	int max = -10000;
	int i, j;
	String p1Str;
	Boolean promoFlag;
	String str;

	Boolean white = ( pStr.charAt(64) == 'w' );
	
	int[][] candidates = Utils.getCandidates(pStr);
	String s;

	for( int m=0; m<candidates.length; m++ ) {

		// i & j are starting and ending squares for the move being considered
		// i.e. the top left corner is 0, the bottom right is 63.
		
		i = candidates[m][0];
		j = candidates[m][1];
		
		p1Str = Utils.checkMove( pStr, i, j );
		if( p1Str.equals("false") ) continue;
		
		// at this point we know the candidate move is a legal one.
		
		promoFlag = ( ((j/8 == 0) && (pStr.charAt(j)=='P')) ||
						((j/8 == 7) && (pStr.charAt(j)=='p')) );
		
		if( promoFlag ) {	// if the move is a promotion, four separate moves.
		
			p1Str = p1Str.substring(0, j) +( white ? "Q" : "q" ) +p1Str.substring(j+1);
			eval = evaluate( p1Str, ply-1, max );    // recursion call
			if( eval > max ) max = eval;
			
			p1Str = p1Str.substring(0, j) +( white ? "R" : "r" ) +p1Str.substring(j+1);
			eval = evaluate( p1Str, ply-1, max );    // recursion call
			if( eval > max ) max = eval;

			p1Str = p1Str.substring(0, j) +( white ? "B" : "b" ) +p1Str.substring(j+1);
			eval = evaluate( p1Str, ply-1, max );    // recursion call
			if( eval > max ) max = eval;

			p1Str = p1Str.substring(0, j) +( white ? "N" : "n" ) +p1Str.substring(j+1);
			eval = evaluate( p1Str, ply-1, max );    // recursion call
			if( eval > max ) max = eval;

		} else {	// if the move is not a pawn promotion, this code is executed.
		
			eval = evaluate( p1Str, ply-1, max );    // recursion call
			if( eval > max ) max = eval;
		}
		
		if( -max < maxEval ) return -max;	// this is the code for aplha-beta pruning
	}
	
	return -max;	// this is the standard negamax eval.
}

[Kabir Shah]

@Fred

I understood your code. (Your comments made it easier!)
But only one problem between your code and mine: I have not created a copy of the board.as you can see in my code, I have declared everything as static variables. more over, I tried to make copy of it and tried to fit in your code, it played worse and made moves for human player as well.

[Fred Hamilton]

Gurudas Bhandarkar wrote:@Fred

I understood your code. (Your comments made it easier!)
But only one problem between your code and mine: I have not created a copy of the board.as you can see in my code, I have declared everything as static variables. more over, I tried to make copy of it and tried to fit in your code, it played worse and made moves for human player as well.

So you are saying that you tried to use my algorithm with your code, and it played worse? But you understand my code and agree with its correctness? or not?

[Kabir Shah]

@fred
When I looked at your code, it seemed pretty fine. But I guess certain things have been missed out.
You did not undo the moves (When I tried to implement it without undoing the moves it gave me array out-of-bound exception)
secondly,When I tried to implement it in my game it did not look for win,neither for itself nor for the opponent. Here is the code which I modified.Please take a careful look at it. (I don't have much time to program now as my college will start and then I must begin with my studies(electronics). So I am trying to fix this bug as soon as possible.Please Help)

 double minmax(int player, int column,double a, double b,int grid1[][],int columnHeight1[]) {
        double value=0;
        if(columnHeight1[column]>=HEIGHT)
            return 0;
        recurDepth++;
        grid1[column][columnHeight1[column]]=player;
        columnHeight1[column]++;

        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(3-player, x,-b,-a,grid1,columnHeight1);
               {
                if(value>v)
                    v=value;
               }
                if(-value<=MAX_RECURDEPTH)
                    return -value;
                

            }

        }
        recurDepth--;
        columnHeight1[column]--;
        grid1[column][columnHeight1[column]]=0;



        return -value;
    }   

here is the entire code,
try executing it:

   package connect4;
import java.io.*;
import java.util.*;

public class Main  {
    private static final int WIDTH=7, HEIGHT=6;
    private static final 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 a=-(MAX_RECURDEPTH+1);
    static int b=MAX_RECURDEPTH+1;

    public static void main(String[] args) {
        in=new BufferedReader(new InputStreamReader(System.in));
        new Main();
    }

    public Main() {
        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;
        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(p,x,a,b,grid,columnHeight);

                    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(int player, int column,double a, double b,int grid1[][],int columnHeight1[]) {
        double value=0;
        if(columnHeight1[column]>=HEIGHT)
            return 0;
        recurDepth++;
        grid1[column][columnHeight1[column]]=player;
        columnHeight1[column]++;

        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(3-player, x,-b,-a,grid1,columnHeight1);
               {
                if(value>v)
                    v=value;
               }
                if(-value<=MAX_RECURDEPTH)
                    return -value;
                

            }

        }
        recurDepth--;
        columnHeight1[column]--;
        grid1[column][columnHeight1[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;
        }

    }
}

  

[Fred Hamilton]

Yeah, I have realized that mine has some issues. It's ok as far as it goes, but it needs a little work. I will be giving this stuff my attention, but It's going to take more time than I thought, so don't hold your breath. Anyways, I shall return hopefully soon with some answers.

[Fred Hamilton]

Gurudas Bhandarkar wrote:@fred
When I looked at your code, it seemed pretty fine. But I guess certain things have been missed out.
You did not undo the moves (When I tried to implement it without undoing the moves it gave me array out-of-bound exception) secondly,When I tried to implement it in my game it did not look for win,neither for itself nor for the opponent. Here is the code which I modified.Please take a careful look at it. (I don't have much time to program now as my college will start and then I must begin with my studies(electronics). So I am trying to fix this bug as soon as possible.Please Help)

I don't know what you mean when you say "You did not undo the moves". As far as not looking for a win goes, I don't see it that way. For example in my program, at ply = 2 it will solve mate in one, at ply = 4 it will solve mate in two, etc. It does this by virtue of starting with a very low initial maxValue. At ply = 4 it will find no possible moves and return the -ve of that low max value, which will lead to the move that forces checkmate being played.

[Kabir Shah]

@fred
By undoing the moves, I mean

  
        recurDepth--;  
        columnHeight1[column]--;  
        grid1[column][columnHeight1[column]]=0;  

In my code.(If I donot write this,It gives me array out o bounds exception.)
(I have modified the code so many times, that by this time, I have almost forgotten what my original code was!)

[Kabir Shah]

More over, it should be noted as my current search max depth is 8, and still the computer does not look win in 1 also.

[Fred Hamilton]

Ok, By undoing moves are you talking about undoing the analysis so that the change in the game position only reflects the move actually played? If so, then I suggest that your array index out of bounds exception is not because of something correct that you aren't doing, it's because of something incorrect that you are doing. I don't concern myself with undoing moves because the analysis creates copies of the position as needed, and these copies are discarded once a particular subtree is evaluated. Only when the final move is chosen is the game position updated.

As for not looking for a win, as I see it that is not really a function of negamax itself , that is a function of the evaluation of the end points of the tree. A particular move leads to a forced win in all variations if all the endpoints of the subtree, after correct ab pruning, are winning positions, if your evaluation routine correctly identifies the endpoints as winning, then the algorithm I provided will indeed choose the winning move. If yor program is not finding a win in one move then you haven't implemented the algorithm properly.

Anyways, i still intend to examine your code, i will begin doing so today, and hopefully will find specific sections of yur code that is causing the problem.

[Kabir Shah]

@fred
I don't think it is possible for me to go for alpha beta pruning (I tried for 3 weeks and failed).I just have one more week to go and then my college will start.If in one week, we are not able to rectify this,then i request you (i can only request you as you may also have lot of work) to rectify my code completely.Its a favour that I can only ask for(not hoping that you will do it). But still I am quiet positive about the job being successfully done in time.

[Fred Hamilton]

heh heh I will try soon, if I can't rectify your connect-4, Then I'll write my own. Hang tough, sorry to keep you waiting after all the work you have put in to this thread so far.

[Kabir Shah]

@fred

Actually I must Thank you for replying me constantly with new ideas and taking pain to find flaws. I must also say that you helped me in this debugging(though its not completely debugged.. and that is of course my fault as the way I have programmed).

[Kabir Shah]

A good news,(at least for me) My vacation is extended.. and now it will be take one more week to start .
- hope you reply soon regarding the code