井字游戏中的 Java Alpha-Beta 修剪

Question

我有一个使用 Minimax 算法的 Tic Tac Toe 游戏。我想通过添加 alpha-beta 修剪来改进它。然而，alpha-beta 方法似乎无法有效计算移动。它只是将其棋子放在下一个可用空间中，无论它是否是最佳着法。我对 minimax 方法没有这个问题。我确定这是我一直忽略的简单问题，所以请原谅我。我用了this minimax 和 this 教程alpha-beta 修剪教程。

这是 Minimax 类。它包括 alpha-beta 方法:

public class Minimax {

    private Token playerToken;
    private EndStates endStates;
    private Token opponentToken;

    public Minimax(Token playerToken, EndStates endStates) {
        this.playerToken = playerToken;
        this.endStates = endStates;
        opponentToken = makeOpponentToken();
    }

    public Token makeOpponentToken() {
        if (playerToken == Token.O) {
            return Token.X;
        }
        else {
            return Token.O;
        }
    }

    public Token getOpponentToken() {
        return opponentToken;
    }

    public int evaluate(Cell[] board) {
        //rows across
        if (endStates.checkWinByRow(board, playerToken) || endStates.checkWinByColumn(board, playerToken) || endStates.checkWinByDiagonal(board, playerToken)) {
            return 10;
        }
        else if (endStates.checkWinByRow(board, opponentToken) || endStates.checkWinByColumn(board, opponentToken) || endStates.checkWinByDiagonal(board, opponentToken)) {
            return -10;
        }

        return 0;
    }

    public boolean hasCellsLeft(Cell[] board) {
        for (int i=0; i<board.length; i++) {
            if (board[i].getToken() == Token.EMPTY) {
                return true;
            }
        }
        return false;
    }

    int MAX = 1000;
    int MIN = -1000;

    public int alphaBeta(Cell[] board, int depth, boolean isMax, int alpha, int beta) {
        int score = evaluate(board);
        if (score == 10) {
            return score;
        }

        if (score == -10) {
            return score;
        }
        if (hasCellsLeft(board) == false) {
            return 0;
        }
        if (isMax) {
            int best = MIN;
            for (int i=0; i<board.length; i++) {
                if (board[i].getToken() == Token.EMPTY) {
                    board[i].setToken(playerToken);
                    int val = alphaBeta(board,depth+1, !isMax, alpha, beta);
                    best = Math.max(best, val);
                    alpha = Math.max(alpha, best);
                    board[i].resetMarker();
                }
                 if (best <= alpha) {
                    break;
                }
            }
            return best;
        }
        else {
            int best = MAX;
            for (int i=0; i<board.length; i++) {
                if (board[i].getToken() == Token.EMPTY) {
                    board[i].setToken(playerToken);
                    int val = alphaBeta(board, depth+1, isMax, alpha, beta);
                    best = Math.min(best, val);
                    beta = Math.min(beta, best);
                    board[i].resetMarker();
                }
                if (beta <= alpha) {
                    break;
                }
            }
            return best;
        }
    }

    public int minimax(Cell[] board,  int depth, boolean isMax) {
        int score = evaluate(board);
        int best;

        if (score == 10) {
            return score;
        }

        if (score == -10) {
            return score;
        }
        if (hasCellsLeft(board) == false) {
            return 0;
        }
        if (isMax) {
            best = -1000;
            for (int i=0; i<board.length; i++) {
                if (board[i].getToken() == Token.EMPTY) {
                    board[i].setToken(playerToken);
                    best = Math.max(best, minimax(board, depth+1, !isMax));
                    board[i].resetMarker();
                }
            }
            return best;
        }
        else {
            best = 1000;
            for (int i=0; i<board.length; i++) {
                if (board[i].getToken() == Token.EMPTY) {
                    board[i].setToken(opponentToken);
                    best = Math.min(best, minimax(board, depth+1, !isMax));
                    board[i].resetMarker();
                }
            }
            return best;
        }
    }

    public int findBestMove(Cell[] board) {
        int bestValue = -1000;
        int bestMove = -1;
        for (int i=0; i<board.length; i++) {
            if (board[i].getToken() == Token.EMPTY) {
                board[i].setToken(playerToken);
                //int moveValue = minimax(board, 0, false);
                int moveValue = alphaBeta(board, 0, true, -1000, 1000);
                board[i].resetMarker();
                if (moveValue > bestValue) {
                    bestMove = i;
                    bestValue = moveValue;
                }
            }
        }
        return bestMove;
    }
}

棋盘是一个包含 9 的数组，其中包含 Token.Empty 的枚举值，但可以分别替换为 Token.X 或 Token.O。

这是调用使用算法的类:

public class ComputerPlayer(Token token, Algorithm minimax ) {
   private Token playerToken;
   private Algorithm minimax;

    public ComputerPlayer(Token playerToken, Algorithm minimax) {
        this.playerToken = playerToken;
        this.minimax = minimax;
    }

    public Token getPlayerToken() {
        return playerToken;
    }

   public void makeMove(Cell[] board) {
        int chosenCell;
        chosenCell = minimax.findBestMove(board);
        board[chosenCell].setToken(playerToken);
        System.out.println("Player " + playerToken + " has chosen cell " + (chosenCell+1));
    }
}

Answer 1

Alpha-Beta 剪枝需要一个良好的未完成游戏状态评估函数才能有效。它应该能够准确评估一名玩家何时“更有可能”获胜。它将使用评估来修剪看起来没有希望的变体。

现在你的评估函数只区分游戏结束和游戏进行中，所以你不能比最小-最大做得更好。

但是，如果你做的比 min-max 还差，那么你一定在其他地方也有错误。我建议单步执行代码并尝试查看哪里出了问题。