Tic-Tac-Toe中的Java Alpha-Beta修剪

Question

我有一个Tic Tac Toe游戏，它使用了极大极小算法。我想通过添加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的枚举值。空，但可以用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做得更好。

然而，如果你做得比min-max差，你肯定在其他地方也有bug。我建议您仔细检查一下代码，看看哪里出了问题。