I'm implementing a version of Negamax for "Chain Reaction" game. Here there is a version of the algorithm that works good:
public int[] think(Field field, int profondita, int alpha, int beta,
int color) {
// TODO Auto-generated method stub
if (profondita == 0 || scacchiera.victory() != 0) {
int val = color * euristica.evaluate(field);
int[] res = new int[3];
res[0] = val;
return res;
}
int[] best_value = new int[3];
best_value[0] = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int[] new_move = new int[3];
if (scacchiera.validMove(color, i, j)) {
Field nuova = new Field(field);
nuova.insertPallino(color, i, j);
new_move = think(nuova, profondita - 1, -beta, -alpha, -color);
new_move[0] = -new_move[0];
if (new_move[0] > best_value[0]) {
best_value[0] = new_move[0];
best_value[1] = i;
best_value[2] = j;
}
}
}
}
return best_value;
}
Now, i want to add the alpha-beta pruning to my code. So i saw in internet the pseudocode, and i modified the code like this:
public int[] think(Field field, int profondita, int alpha, int beta,
int color) {
// TODO Auto-generated method stub
if (profondita == 0 || scacchiera.victory() != 0) {
int val = color * euristica.evaluate(field);
int[] res = new int[3];
res[0] = val;
return res;
}
int[] best_value = new int[3];
best_value[0] = Integer.MIN_VALUE;
boolean flag = true;
for (int i = 0; i < N && flag; i++) {
for (int j = 0; j < M && flag; j++) {
int[] new_move = new int[3];
if (scacchiera.validMove(color, i, j)) {
Field nuova = new Field(field);
nuova.insertPallino(color, i, j);
new_move = think(nuova, profondita - 1, -beta, -alpha, -color);
new_move[0] = -new_move[0];
if (new_move[0] > best_value[0]) {
best_value[0] = new_move[0];
best_value[1] = i;
best_value[2] = j;
}
alpha = Math.max(alpha, new_move[0]);
if (alpha >= beta) {
flag = false; //break
}
}
}
}
return best_value;
}
The problem is that the alpha-beta version returns to me a wrong result, and i don't can't figure out why. Can someone help me with this?
Your code for alpha-beta pruning is fine so your problem must lie in some other part of the program. Though I would caution against using Integer.MIN_VALUE
as a minimum since -Integer.MIN_VALUE != Integer.MAX_VALUE
.