# Is there any easy way to understand the Alpha Beta for Othello?

I'm stuck with coding the Alpha Beta algorithm for a console-based game I'm developping at the moment. I tried to understand how it works for a week but still no idea how to get started with it. Here is the algorithm in pseudo-code :

    minimax (in game board, in int depth, in int max_depth,
in boolean alpha_beta, in score black_best, in score white_best,
out score chosen_score, out score chosen_move)
begin
:
:
minimax(new_board, depth+1, max_depth,
alpha_beta, black_best, white_best,
the_score, the_move);
if (alpha_beta) then
if (to_move(black) and (the_score > black_best))
if (the_score > white_best)
break;  /*  alpha_beta cutoff  */
else
black_best = the_score;
endif
endif
if (to_move(white) and (the_score < white_best))
if (the_score < white_best)
break;  /*  alpha_beta cutoff  */
else
white_best = the_score;
endif
endif
endif
:
:
end.


I've already done the Min Max algorithm for a fixed depth of 2. Minmax pseudo-code :

minimax(in game board, in int depth, in int max_depth,
out score chosen_score, out score chosen_move)
begin
if (depth = max_depth) then
chosen_score = evaluation(board);
else
moves_list = generate_moves(board);
if (moves_list = NULL) then
chosen_score = evaluation(board);
else
for (i = 1 to moves_list.length) do
best_score = infinity;
new_board = board;
apply_move(new_board, moves_list[i]);
minimax(new_board, depth+1, max_depth, the_score, the_move);
if (better(the_score, best_score)) then
best_score = the_score;
best_move = the_move;
endif
enddo
chosen_score = best_score;
chosen_move = best_move;
endif
endif
end.


and my code (it is really messy sorry for that) :

char *minimax (Data *t, Data *u)
{
int bestScore1=0, bestScore2=0, i,p,k,pn1=0,pb1=0,pn2=0,pb2=0, bestMove=0,score1=0,score2=0;
Data *saveState1,*saveState2;
saveState1=malloc(sizeof(Data));
saveState2=malloc(sizeof(Data));
*saveState1=*t; //Saving the state of the game before testing a move (first row which is AI's move)

for (i=11; i<89; i++)
{
*t=*saveState1;

if (check(i,t,u,1) > 0) //We're checking if the cell i is playable for WHITES
{
t->p[i]=BLANC; //Make the move (BLANC = WHITE in french)

pn1=0; pb1=0; //PN1: number of BLACKS PB1: number of WHITES
for (k=11;k<89;k++) //counts the white and black game pieces
{
if(t->p[k]==NOIR)
pn1++;
else if(t->p[k]==BLANC)
pb1++;
//printf("\npb1=%d",pb1); //DEB
}
score1=pb1-pn1; //Save the score
if (score1 > bestScore1) //Set as best score if better than previous
bestScore1=score1;
*saveState2=*t; //Saving state for second row which is the player's move
//printf("\n%s played by white",tostring(i)); //DEB
for (p=11; p<89; p++) //Testing all the cells of the game
{
*t=*saveState2; //saving state before making a move

if (check(p,t,u,-1)) //Checking if BLACK can play the cell i
{
t->p[p]=NOIR; //Do the actual move

pn2=0; pb2=0; //PN: number of BLACKS PB: number of WHITES
for (k=11;k<89;k++) //Counts the white and black game pieces
{
if(t->p[k]==NOIR)
pn2++;
else if(t->p[k]==BLANC)
pb2++;
//printf("\npb2=%d",pb2); //DEB
}
score2=pb2-pn2; //Saving score for second row
if (score2 > bestScore2) //Setting score as bestScore if better than previous
{
bestScore2=score2;
bestMove=i;
}
else if (score2 == 0 || score1 == 0) //Setting default move if scores are ex aequo
{
bestMove=i;
}
else if (score2 < 0 || score1 < 0) //Setting default move if both scores are making the AI lose points
{
bestMove=i;
}
//printf("\n%s played by black",tostring(p)); //DEB
//printf("\nscore1=%d\tscore2=%d\tbestMove=%s",bestScore1,bestScore2,tostring(bestMove)); //DEB
}
}
}
}
return bestMove;
}


Where *t is the array representing the current game and *u the precedent state of the game. Each array has 100 cells with the following values :

• 0 : black
• 1 : white
• 2 : empty
• 3 : border

Thanks for reading and sorry for the bad english skills. Sources : http://pressibus.org/ataxx/autre/minimax/node2.html

• Asking a bunch of people you don't know to read code you admit is messy is a sketchy proposition at best. – Almo Apr 10 '15 at 19:10
• @Almo Do you think I should delete this post? – Hardrow Apr 10 '15 at 19:18
• I would say that you should format your code properly so it's more legible before asking other people to read it and help you find problems in it. Second, asking narrower questions gets better help faster. But I'm undecided about whether the question in its current form is ok for the site or not. Usually super-bad questions get flagged and held almost immediately, so maybe just edit the code bits for clarity and see what happens. Incidentally, my first minimax AI was for Othello. :) – Almo Apr 10 '15 at 19:41
• alpha-beta is a method to chose your next move, given the opponents most likely next move. In general each possible next position is evaluated via the min-max strength. (you want to maximize your position while minimizing the opponents position.) The alpha-beta algorithm is a method to eliminate non productive sequences of moves from consideration. you might want to read: <en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning> for details – user3629249 Apr 10 '15 at 19:41
• @Almo Thanks, I will make it as clear as I possibly can. – Hardrow Apr 12 '15 at 23:20