minimax algorithm returning different value with alpha beta pruning
I am writing Minimax algorithm for Chess.
I get different final result values for minimax with out alpha beta pruning and minimax with alpha beta pruning.
My pseudo code is below. Can anyone help me?
miniMax()
public int miniMax(int depth, Board b, boolean maxPlayer) {
if(depth == 0)
return evaluateBoard(b);
if(maxPlayer) {
int bestMoveVal = 0;
for( each Max player's moves) {
// make a move on a temp board
int eval = miniMax(depth - 1, tempBoard, false);
bestMoveVal = Math.max(bestMoveVal, eval);
}
return bestMoveVal;
}
else {
int bestMoveVal = 0;
for (each Min player's moves) {
// make a move on a temp board.
int eval = miniMax(depth - 1, tempBoard, true);
bestMoveVal = Math.max(bestMoveVal, eval);
}
return bestMoveVal;
}
}
alphabeta()
public int alphabeta(int depth, Board b, int alpha, int beta, boolean maxPlayer) {
if(depth == 0)
return evaluateBoard(b);
if(maxPlayer) {
for(each max player's moves) {
// make a move on a temp board
int eval = alphabeta(depth - 1, temp, alpha, beta, false);
alpha = Math.max(alpha, eval);
if(beta <= alpha) //beta cut off;
break;
}
return alpha;
}
else {
for(each of min's moves) {
// make a move on a temp board
int eval = alphabeta(depth - 1, temp, alpha, beta, false);
beta = Math.min(beta, eval);
if(beta <= alpha)
break; // alpha cut off;
}
return beta;
}
}
Board represents a the board. For every move, I make the move on a copy of the passed Board object and then pass this temporary Board onto to further calls.
evaluateBoard(Board b) takes in a Board and calculates a score based on the given Board scenario.
An big problem in your code is that alphabeta is not recursive, as it should be. It calls miniMax .
The recursive calls in alphabeta should call alphabeta , otherwise it is fundamentally wrong. That is to say, the alpha-beta pruning is applied at each depth level, not only the top level.
In the minMax function you have bestMoveVal = Math.max(bestMoveVal, eval); for both the minimizing and maximizing player.