# Coding an alphabeta algo

This topic is 4578 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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]

##### Share on other sites
Anything? How is the code structure? is there a way tp make it more efficiant?
Thanks.

##### Share on other sites
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]

##### Share on other sites
Thanks for that input! I'll try to break up the code more.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634089
• Total Posts
3015460
×