将 alpha beta 添加到 negamax

Question

我正在为 "Chain Reaction" 游戏实现一个 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; 
}

现在，我想将 alpha-beta 修剪添加到我的代码中。所以我在网上看到了伪代码，我修改了这样的代码：

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

问题是 alpha-beta 版本 returns 对我来说是一个错误的结果，我不知道为什么。有人可以帮我解决这个问题吗？

Answer 1

您的 alpha-beta 修剪代码没有问题，所以您的问题一定出在程序的其他部分。虽然我会警告不要使用 Integer.MIN_VALUE 作为最低限度，因为 -Integer.MIN_VALUE != Integer.MAX_VALUE。

将 alpha beta 添加到 negamax

adding alpha beta to negamax

alpha

beta

pruning

negamax