Coding an alphabeta algo

295

Author

July 07, 2006 03:48 AM

I'm trying to code an alphabeta algorithm. I think I got the logic of it right, and with a depth of 7 it plays sort of ok but sometimes it doesn't see that it can win or that the enemy can win. I was wondering if you guys could have a look at the code. First of all, I have a board structure:


//this stores the evaluation of a move and the move
struct SMove{
 SMove(int s, int m){score = s; move = m;}
 int score;
 int move;
};

struct SBoard{
  //board values can be: 1-computer, -1-player, 0-emty
  int Position[7][6];
  //the hieght of the lowest emty square in each coloum   
  int Heights[7];
  int Evaluation;
  int MaxHeight;
  bool Win;
  SBoard();
  void   UpdateBoard(int move, int turn);
  void   EvaluateBoard();
};

here're the functions:


//////////////////EvaluateGroup//////////////////////
//
//  evaluates a group of 4 cells
//
/////////////////////////////////////////////////////
int EvaluateGroup(int NumberOfMe, int NumberOfEnemy)
{
  int Evaluation=0;
  if(NumberOfEnemy == 0)
   {
    switch(NumberOfMe)
     {
      case 2:
        Evaluation+=5;
        break;
      case 3:
        Evaluation+=15;
        break;
     }
   }
   
  if(NumberOfMe == 0)
   {
    switch(NumberOfEnemy)
     {
      case 2:
        Evaluation-=5;
        break;
      case 3:
        Evaluation-=15;
        break;
     }
   }
  return Evaluation;
}

//ctor
SBoard :: SBoard()
{
 Evaluation = 0;
 MaxHeight  = 0;
 Win        = false;
 memset(Position, 0, sizeof(int)*7*6);  //init the boads to 0;
 memset(Heights,   0, sizeof(int)*7);

}

/////////////////UpdateBoard/////////////////////////
//
// Updates the board with a move, it also checks for a win
//
/////////////////////////////////////////////////////
void SBoard :: UpdateBoard(int move, int turn)
{
 if((Heights[move] < 6)&&(move<7)&&(move>-1)) 
  {
  Position[move][Heights[move]] = turn;
  
//--Check if someone won
  //check coloums
  int InARow = 0;
  for(int r=0; r<6; r++)
   {
    if(Position[move][r] == turn)
     InARow++;
    else
     InARow=0;
     
    if(InARow==4)
     Win=true;
   }
   
   //check rows
  InARow = 0;
  for(int c=0; c<7; c++)
   {
    if(Position[c][Heights[move]] == turn)
     InARow++;
    else
     InARow=0;
     
    if(InARow==4)
     Win=true;
   }
   
   //check right diagonal
   int first_coloum;
   int first_row;
   InARow = 0;
   if(move > Heights[move])
   {
    first_coloum = move - Heights[move];
    first_row = 0;
   }
   else
   {
    first_coloum = 0;
    first_row = Heights[move] - move;
   }
   int r=first_row; 
   int c=first_coloum; 
   while((r<6)&&(c<7))
   {
    if(Position[c][r] == turn)
     InARow++;
    else
     InARow=0;
     
    if(InARow==4)
     Win=true;
     r++;
     c++;
   }
   
   //check left diagonal
   InARow = 0;
   if(7-move > Heights[move])
   {
    first_coloum = move + Heights[move];
    first_row = 0;
   }
   else
   {
    first_coloum = 7;
    first_row = Heights[move] + move - 7;
   }
   r=first_row; 
   c=first_coloum;
   while((r<6)&&(c>-1))
   {
    if(Position[c][r] == turn)
     InARow++;
    else
     InARow=0;
     
    if(InARow==4)
     Win=true;
    r++;
    c--;
   }
   
   
  
  //update the max height
  Heights[move]++;
  if(Heights[move] > MaxHeight)
   MaxHeight++;
  } 
}

////////////////////UpdateBoard////////////////////
//
//  Evaluates the board by checking all groups of 4
//
///////////////////////////////////////////////////
void SBoard :: EvaluateBoard()
{
//---ROWS
  //Loop through all the rows up till the highest hieght
  int ScoreForAllRows = 0;
  for(int r=0; r<MaxHeight; r++)
  {
    //Loop through all of the groups of 4 
    
    for(int c=0; c<4; c++)
     {
       int NumberOfEnemy = 0;
       int NumberOfMe    = 0;
        //Loop through the 4 in the group
        for(int i=0; i<4; i++)
         {    
            if(Position[c+i][r] == 1)
             NumberOfMe++;
            if(Position[c+i][r] == -1)
             NumberOfEnemy++;
         }
        //Evaluate that group
        ScoreForAllRows += EvaluateGroup(NumberOfMe, NumberOfEnemy);
     }//c  
  }//r
  
  //---COLOUMS
  //Loop through all the colums up till the highest hieght
  int ScoreForAllColoums = 0;
  for(int c=0; c<7; c++)
  {
    //Loop through all of the groups of 4 
    
    for(int r=0; r<3; r++)
     {
       int NumberOfEnemy = 0;
       int NumberOfMe    = 0;
        //Loop through the 4 in the group
        for(int i=0; i<4; i++)
         {    
            if(Position[c][r+i] == 1)
             NumberOfMe++;
            if(Position[c][r+i] == -1)
             NumberOfEnemy++;
         }
        //Evaluate that group
        ScoreForAllColoums += EvaluateGroup(NumberOfMe, NumberOfEnemy);
     }//c  
  }//r
  
  //---DIAGONALS
  //Loop through all the bottom rows and check which diagonals they have
  int ScoreForAllDiagonals = 0;
  for(int c=0; c<7; c++)
   {
   for(int r=0; r<6; r++)
   {
    //if we can diagonal up to the right
    if((c<4)&&(r<3))
     {
       int NumberOfEnemy = 0;
       int NumberOfMe    = 0;
        //Loop through the 4 in the group
        for(int i=0; i<4; i++)
         {    
            if(Position[c+i][r+i] == 1)
             NumberOfMe++;
            if(Position[c+i][r+i] == -1)
             NumberOfEnemy++;
         }
        //Evaluate that group
        ScoreForAllDiagonals += EvaluateGroup(NumberOfMe, NumberOfEnemy);
      }//UR
      
      //if we can diagonal up to the left
    if((c>2)&&(r<3))
     {
       int NumberOfEnemy = 0;
       int NumberOfMe    = 0;
        //Loop through the 4 in the group
        for(int i=0; i<4; i++)
         {    
            if(Position[c-i][r+i] == 1)
             NumberOfMe++;
            if(Position[c-i][r+i] == -1)
             NumberOfEnemy++;
         }
        //Evaluate that group
        ScoreForAllDiagonals += EvaluateGroup(NumberOfMe, NumberOfEnemy);
      }//UL
     /* 
        //if we can diagonal down to the right
    if((c<4)&&(r>2))
     {
       int NumberOfEnemy = 0;
       int NumberOfMe    = 0;
        //Loop through the 4 in the group
        for(int i=0; i<4; i++)
         {    
            if(Position[c+i][r-i] == 1)
             NumberOfMe++;
            if(Position[c+i][r-i] == -1)
             NumberOfEnemy++;
         }
        //Evaluate that group
        ScoreForAllDiagonals += EvaluateGroup(NumberOfMe, NumberOfEnemy);
      }//DR
      
        //if we can diagonal down to the left
    if((c>2)&&(r>2))
     {
       int NumberOfEnemy = 0;
       int NumberOfMe    = 0;
        //Loop through the 4 in the group
        for(int i=0; i<4; i++)
         {    
            if(Position[c-i][r-i] == 1)
             NumberOfMe++;
            if(Position[c-i][r-i] == -1)
             NumberOfEnemy++;
         }
        //Evaluate that group
        ScoreForAllDiagonals += EvaluateGroup(NumberOfMe, NumberOfEnemy);
      }//DL
     */
     }//r 
  }//c
  
  Evaluation = ScoreForAllRows + ScoreForAllColoums + ScoreForAllDiagonals;
}

I checked the updateboard and evaluateboard seperatly so I don't think that there's a problem there. Here's the MinMax class which actually uses the Negamax (same as minmax just instead of getting min and max values it always gets max and just flips the - sign) function ans AB:


class CMinMax{
 private:
  int m_iTotalDepth;
  SMove AlphaBeta(int depth, SBoard board, int alpha, int beta, int turn);
  vector<int> GenerateMoves(SBoard board, int depth);
 
 public:
  CMinMax(int d){m_iTotalDepth = d;}
  int GetNextMove(SBoard board);
};

////////////////////AlphaBeta/////////////////////////
//
// This is the heart of the AI.  It is a recursive
// negamax function with AB implemented.
//
//////////////////////////////////////////////////////
SMove CMinMax :: AlphaBeta(int depth, SBoard board, int alpha, int beta, int turn)
{
 counter++;
 //if we won return a huge number or a tiny one, depending on who won
 if(board.Win)
  return SMove(-turn*100000,0);
 
 //if we got to the end of the search return the static evaluation
 if(depth == 0)
  {
   board.EvaluateBoard();
   return SMove(board.Evaluation,0);
  }
 
 //if we havn't gotten to the end, search for best node
 else
  {
   int best = -100000; int move_score = 0; int best_move = 0;
   vector<int> moves = GenerateMoves(board, depth);
   //loop through all possible moves
   for(int i=0; i<moves.size(); i++)
   {
    SBoard new_board = board;  //IS THIS A PROBLEM??
    new_board.UpdateBoard(moves, turn);
    move_score = -AlphaBeta(depth-1, new_board, -beta, -alpha, -turn).score;
    
    //if this is better that the best move sofar
    if(move_score>best)
     {best=move_score; best_move=moves;}
    //alphabeta pruning
    if(best>alpha)
     alpha = best;
    if(alpha>beta)
     return SMove(beta, best_move);
   }//for i 
  
  //if we're still in the tree 9not at the base node
  //if(depth<m_iTotalDepth)
   return SMove(best, best_move); 
  //else
   //return best_move;
  }//else end
}

vector<int> CMinMax :: GenerateMoves(SBoard board, int depth)
{
 vector<int> moves;
 //go through all the coloums
 for(int c=0; c<7; c++)
  {
   if(board.Heights[c]<6)
    moves.push_back(c);
  }
 return moves;
} 

int CMinMax :: GetNextMove(SBoard board)
{
 counter = 0;
 int move = AlphaBeta(m_iTotalDepth, board, -100000, 100000, -1).move;
 return move;
}

In the game I have a board that I constantly update and to find the computer's move I do: move = Computer.GetNextMove(GameBoard); And one other thing, the variable "turn" in the AB function is 1 if the AB is finding a move for the computer, and -1 for the player. I got a little confused with were I should put -turn and were I should put turn so maybe that is the problem. And for some reason If in the GetNextMove I write 1(instead of -1) he does worse, even though it should really be 1 (cause it's the computer's move)? and that happens when m_iTotalDepth is odd but not when it's even?? Well anyway, what do you guys think? Thanks. [Edited by - daniel_i_l on July 7, 2006 4:14:11 AM]

"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the internet, we know this is not true." -- Professor Robert Silensky

daniel_i_l

295

Author

July 07, 2006 10:39 AM

Anything? How is the code structure? is there a way tp make it more efficiant?
Thanks.

"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the internet, we know this is not true." -- Professor Robert Silensky

NotAYakk

876

July 07, 2006 03:41 PM

You are using ints and flag values instead of enums with named values. This is a serious premature optimization which makes your code harder to follow.

typedef enum { player1, player2 } player;struct location {  bool occupied;  player which_side;};

Your AlphaBeta function is far too complicated.

Your evaluation function should take the board and the side, and generate the value of the board for that side.

You are needlessly storing state in the game board. As an example: Why in the hell does EvaluateBoard store the result of the evaluation, why doesn't it just return it?

I would also advise taking your long functions and breaking them up into smaller ones. UpdateBoard, EvaluateBoard -- they are both far far far too long. Heck, you have leftover junk code lieing around!

It may be possible to prevent all of that board copying. Are your moves invertable? If so, you could, with care, use the same board for every single recursive call, simply undoing the changes as you fall back up the stack. This is dangerous, but may give you a significant performance improvement. Naturally do not do this until your code is well structured and correct.

...

By breaking the code down into smaller pieces, it is far easier to check that each piece is doing something reasonably correct. It is also easier to see what each function does from start-to-end, because you can see each step written out as a descriptively named function call.

Once you have your code as a bunch of short, concice functions, you can start with tricks like "make the moves reversable". Or you can try to optimize one of the sub-functions by rewriting it, and then run test runs against the original -- checking to see that the rewrite does the same thing, faster -- and then replace the original subfunction.

[Edited by - NotAYakk on July 10, 2006 11:41:13 AM]

daniel_i_l

295

Author

July 08, 2006 02:40 PM

Thanks for that input! I'll try to break up the code more.

"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the internet, we know this is not true." -- Professor Robert Silensky

Coding an alphabeta algo

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Coding an alphabeta algo

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines