java - 国际象棋 alpha beta 返回棋盘的错误 Action

Question

我正在尝试使用 alpha beta 剪枝实现一个国际象棋游戏。以下几乎可以正常工作，但它会返回错误的 Action 。

例如，可能会发生以下情况。

白色(用户)移动，白色王位 - a1/黑色(计算机)，黑色王位 - h1

白方将王从 a1 - a2 下，然后黑方还手 g2 - g1???

计算机似乎返回了错误节点(棋盘表示)的着法，就好像给定棋盘位置的最佳评估没有一直传播到树上。因此，在探索的一个模拟位置中，计算机“想象”它的国王移动到 g2，然后返回从这个位置开始的移动，没有意识到这个位置是一个模拟位置而不是实际棋盘的表示(根节点？)。

我如何更正代码以使计算机返回实际棋盘表示的移动而不是错误的模拟之一？

谢谢。

初始调用 alphaBeta(3, ChessEngine.invertBoard(ChessEngine.board), -10000, 10000, true);

private static int alphaBetaEvaluate = 0;
private static int alphaBetaSelectedSquare = 0;
private static int alphaBetaMoveToSquare = 0;
public static int alphaBeta(int depth, char[] board, int alpha, int beta, boolean maxPlayer) {

    //create a copy of the board
    char[] boardCopy = board.clone();

    //if terminal state has not been met, keep searching
    if (maxPlayer == true && depth > 0) {

        //for all of the moves that max can make
        for (int i = 0; i < board.length; i++) {
            for (int move : ChessEngine.getValidMoves(i, boardCopy)) {

                //make the move
                boardCopy[move] = boardCopy[i];
                boardCopy[i] = '.';

                alphaBetaEvaluate = rating(board, boardCopy, i, move);

                //store the best move to make
                int temp = alphaBeta(--depth, ChessEngine.invertBoard(boardCopy), -10000, 10000, false);
                if (temp > alpha) {
                    alphaBetaSelectedSquare = i;
                    alphaBetaMoveToSquare = move;           
                    alpha = temp;
                }

                //reset the board for the next simulated move
                boardCopy = board.clone();

                if (beta <= alpha) {
                    break;
                }
            }
        }
        return alpha;
    } else if (maxPlayer == false && depth > 0) {

        //for all of the moves that min can make
        for (int i = 0; i < board.length; i++) {
            for (int move : ChessEngine.getValidMoves(i, boardCopy)) {

                //make the move
                boardCopy[move] = boardCopy[i];
                boardCopy[i] = '.';
                beta = Math.min(beta, alphaBeta(--depth, ChessEngine.invertBoard(boardCopy), -10000, 10000, true));

                //reset the board for the next simulated move
                boardCopy = board.clone();

                if (beta <= alpha) {
                    break;
                }
            }
        }
        return beta;
    }
    return alphaBetaEvaluate;
}

Answer 1

毕竟我没有得到你的实现。首先你要做的是创建一棵树。决策树并向上传播决策。您希望最大化您的评价，并期望敌人会选择使您的评价最小化的举 Action 为返回。

因此，除非您知道您根据情况所做的评估是正确调整的，否则反转董事会对我来说听起来不太合理。

对我来说另一个严重的问题是，你总是用 -10k 和 10k 作为 alpha 和 beta 的边界来调用下一步的最小值/最大值。这样你的算法就不会从以前的 Action 中“学习”。

您需要再次检查算法(例如我使用的维基百科)并查看它们使用的 alpha 和 beta 被之前的评估修改过。这样，更高深度的计算可以首先停止，其次更好地评估最佳着法。

我不是这方面的专家。几十年前，当我编写我的实现时，我使用了一些不同的东西。

另一个想法是不要在同一个方法中使用 min 和 max，而是使用 min 和 max 方法。它使您更有可能发现其他缺陷。

也不要用二王来评价。那没有目标。两个国王是随机的，不能赢。一件事可能是两个骑士或四个女王等等。它不是那么随机，您可以看到皇后在周围跳舞而无法互相捕获。或者使用三个骑士对一个女王。

并尝试围绕其他部分为自己创建一些单元测试。只是为了确保零件独立正常工作。为什么要使用字符？为什么不使用枚举或对象。您可以为每个字段重复使用对象(它更像是各种数字)。

但无论如何这是风格而非算法正确性。