alphabetapruningnegamax

adding alpha beta to negamax


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?


Solution

  • 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.