Добавив альфа-бета к Negamax

Question

Я реализую версию Negamax для игры "Цепная реакция". Здесь есть версия алгоритма, которая работает хорошо:

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; 
}

Теперь я хочу добавить обрезку альфа-бета в мой код. Итак, я увидел в интернете псевдокод и изменил код следующим образом:

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; 
}

Проблема в том, что альфа-бета-версия возвращает мне неверный результат, и я не могу понять, почему. Может кто-то помочь мне с этим?

Answer 1

Ваш код для обрезки альфа-бета в порядке, поэтому ваша проблема должна лежать в какой-то другой части программы. Хотя я бы предостерег от использования Integer.MIN_VALUE как минимум с -Integer.MIN_VALUE != Integer.MAX_VALUE,