MiniMax Algorithm with Alpha Beta pruning
I successfully implemented a minimax algorithm whoever when alpha beta pruning is added, the algorithm does not function correctly. Here is the code currently being used as the algorithm:
publicint Negamax(int depth,char[][] charBoard,int player,int alpha,int beta){
int score = 0;
char chooseSymbol ='o';
if (player == 1)
chooseSymbol ='x';
if (depth == 0){
score = evalBoard.rateBoard(charBoard, player) - evalBoard.rateBoard(charBoard, player*(-1));
}elseif(evalBoard.checkWin(charBoard, player)){
score = Integer.MAX_VALUE - depth;
}elseif(evalBoard.checkWin(charBoard, player*(-1))){
score = Integer.MIN_VALUE + depth;
}elseif(evalBoard.checkTie(charBoard)){
return 0;
}else{
score = Integer.MIN_VALUE;
for (int i=0; i<7; i++){
if (fullRow(charBoard, i))
continue;
char[][] charNewBoard =newchar[7][6];
for (int j=0; j<7; j++){
for (int k=0; k<6; k++){
charNewBoard[j][k] = charBoard[j][k];
}
}
charNewBoard = addSymbol(charNewBoard, i, chooseSymbol);
int movescore = -Negamax(depth - 1, charNewBoard, player*(-1), -beta, -alpha);
if (movescore > score){
score = movescore;
bestMove = i;
}
//Start Section
if (movescore >= beta)// When commented out
return beta;// the entire algorithm
if (movescore > alpha)// functions correctly..
alpha = movescore;//
//End Section
}
}
return score;
}
As written in the comments, when the alpha beta section is commented out the algorithm functions correctly.
Any help with this problem would be greatly appreciated.
Thx Jon
> whoever when alpha beta pruning is added, the
> algorithm does not function correctly.
A little more detail there might prove useful to those who would help you.
You might even find that the exercise of describing the problem in detail leads to a head-smacking "D'OH! Of course!" moment. Happens to me all the time. :-)
jverda at 2007-7-14 17:59:08 >
> I successfully implemented a minimax algorithm> whoever when alpha beta pruning is added, the> algorithm does not function correctly. :-) "successfully implemented" followed by "the algorithm does not function correctly" .
> > I successfully implemented a minimax algorithm
> > whoever when alpha beta pruning is added, the
> > algorithm does not function correctly.
>
> :-) "successfully implemented" followed by "the
> algorithm does not function correctly" .
Yeah, that's what I thought at first. But I guess he means he sucessfully implemented a version without a/b pruning, but when he added the pruning, it no longer worked.
jverda at 2007-7-14 17:59:08 >
> > > I successfully implemented a minimax algorithm
> > > whoever when alpha beta pruning is added, the
> > > algorithm does not function correctly.
> >
> > :-) "successfully implemented" followed by "the
> > algorithm does not function correctly" .
>
>
> Yeah, that's what I thought at first. But I guess he
> means he sucessfully implemented a version without
> a/b pruning, but when he added the pruning, it no
> longer worked.
I suppose that since, other than reading a summary on Wikipedia, I don't know what a 'minimax algorithm' is and have never tried to implement one I should not make fun.
Sorry about not being more specific. This negamax function is to be used in a Connect Four game where it takes a board, the current player, the depth to be searched, and alpha/beta.It should return the highest score possible and store the bestMove in a global variable. The 'evalBoard' object has been tested tremendously and I am very sure it works perfectly.
When the alpha/beta code is removed, the bestMove function returns a number from 0 to 6.
However, when the alpha/beta code is added, the bestMove remains at zero until
if (fullRow(charBoard, i))
continue;
forces betMove to change to 1 and so on and so forth.
The Negamax function is called with:
int highScore = Negamax(6, charBoard, player, Integer.MIN_VALUE, Integer.MAX_VALUE)
Hopefully this information helps.
Thanks again
> I suppose that since, other than reading a summary on Wikipedia, I
> don't know what a 'minimax algorithm' is and have never tried to
> implement one I should not make fun.
The idea is quite simple: your best move e.g. in a board game is my worst
result and vice versa. If I can minimize your best move I have maximized
my best move (and that's the move I'll play).
Now suppose my best move somewhere in that game tree turns out
to be worse than another best move of mine somewhere else in that
same tree, there is no need anymore for me to explore the rest of that
subtree. That's the alpha pruning part. The same counts for you and
that's the beta pruning part.
alpha-beta pruning reduces the number of nodes to be examined to
O(sqrt(n)) where n are all the nodes in the fully examined tree. It is
quite a nice algorithm although quite tricky too when you have to build it.
The best reference I can think of now is the old book "Data Structures"
by Horrowitz and Sahni.
kind regards,
Jos
JosAHa at 2007-7-14 17:59:08 >
> The idea is quite simple: your best move e.g. in a> board game is my worstThanks Jos. I suppose I should apply it to Bridge.
> > The idea is quite simple: your best move e.g. in a
> > board game is my worst
>
> Thanks Jos. I suppose I should apply it to Bridge.
Bridge is a funny game; most of the information comes from the bidding
phase. Playing the cards afterwards isn't much of a problem when the
bidding gave enough information.
Of course I can only play basic Acol Bridge but I'm very good at bluffing
and cheating ;-)
kind regards,
Jos ( < poker face )
JosAHa at 2007-7-14 17:59:08 >
Try to invoke the function withint highScore = Negamax(6, charBoard, player, Integer.MIN_VALUE + 1, Integer.MAX_VALUE)
Due to the two's complement representation of integers negating Integer.MIN_VALUE will result again in Integer.MIN_VALUE. This destroys your logic when you negate alpha and beta in the recursive call.
Yes that works perfectly! It makes sense too. Thanks for pointing out my mistakeJon
I had exactly the same problem with this algorithm in a board game I'm currently developing! Thanks very much guys for pointing out the solution, I was lost in the dark for this for quite a long time that made me almost abandon the alpha-beta pruning optimisation for my board game. Thanks again!
