想请教一下关于井字棋minimax算法的问题

Question

为什么minimax算法在这种情况下会下在阻止O获胜的位置而不是使自己获胜，还有就是它好像看不到几步之后

下面是我的代码

public class TicTacToe {

// 用于表示棋盘的状态，其中玩家的棋子用 1 和 -1 表示，空位用 0 表示
private static final int EMPTY = 0;
private static final int X = 1;
private static final int O = -1;

// 判断游戏是否结束，并返回赢家
private static int evaluate(int[][] board) {
    for (int i = 0; i < 3; i++) {
        // 检查行和列
        if (board[i][0] == board[i][1] && board[i][0] == board[i][2]) {
            if (board[i][0] != EMPTY) return board[i][0];
        }
        if (board[0][i] == board[1][i] && board[0][i] == board[2][i]) {
            if (board[0][i] != EMPTY) return board[0][i];
        }
    }

    // 检查对角线
    if ((board[0][0] == board[1][1] && board[0][0] == board[2][2]) || (board[0][2] == board[1][1] && board[0][2] == board[2][0])) {
        if (board[1][1] != EMPTY) return board[1][1];
    }

    // 没有赢家返回0
    return EMPTY;
}

// 判断棋盘上是否还有空位
private static boolean isMovesLeft(int[][] board) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == EMPTY) {
                return true;
            }
        }
    }
    return false;
}

// Minimax算法实现
private static int minimax(int[][] board, int depth, boolean isMax) {
    int score = evaluate(board);

    if (score == X) return score - depth; // 减去深度以优先走最快获胜路径
    if (score == O) return depth + score; // 

    if (!isMovesLeft(board)) return 0; // 平局

    if (isMax) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == EMPTY) {
                    board[i][j] = X;
                    best = Math.max(best, minimax(board, depth + 1, false));
                    board[i][j] = EMPTY;
                }
            }
        }
        return best;
    } else {
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == EMPTY) {
                    board[i][j] = O;
                    best = Math.min(best, minimax(board, depth + 1, true));
                    board[i][j] = EMPTY;
                }
            }
        }
        return best;
    }
}

// 该方法找到并返回最优的移动
public static int[] findBestMove(int[][] board) {
    int bestValue = Integer.MIN_VALUE;
    int[] bestMove = new int[]{-1, -1};

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == EMPTY) {
                board[i][j] = X;
                int moveValue = minimax(board, 0, false);
                board[i][j] = EMPTY;
                if (moveValue > bestValue) {
                    bestMove[0] = i;
                    bestMove[1] = j;
                    bestValue = moveValue;
                }
            }
        }
    }
    return bestMove; // 返回行列

｝
｝

Answer 1

基于Monster 组和AIGC的调写：若有帮助，还望采纳~~：

• Minimax算法在井字棋中的表现取决于几个关键因素。首先，要理解Minimax算法是基于评估函数的结果来决定下一步的最佳动作。在你提供的代码中，评估函数（evaluate）检查行、列和对角线以确定是否有获胜者。

• 在Minimax算法中，存在两种角色：最大化玩家（Maximizer）和最小化玩家（Minimizer）。最大化玩家试图最大化分数（在这里代表X玩家），而最小化玩家试图最小化分数（代表O玩家）。算法通过递归方式遍历所有可能的游戏状态，并根据评估函数的分数进行选择。

• 你的问题中提到的“阻止O获胜的位置而不是使自己获胜”通常发生在以下情况：

1. 防守优先：在某些情况下，算法可能判断阻止对方获胜比立即获胜更重要，特别是当对方有多种获胜方式时。这种情况下，算法会选择防守而不是进攻。

2. 评估函数的局限性：如果评估函数没有正确地评估特定的棋盘状态，或者没有考虑到所有获胜的可能性，算法可能会错过获胜的机会。

3. 搜索深度的限制：“看不到几步之后”可能是因为搜索深度的限制。如果搜索深度不够，算法可能无法预见到几步之后的获胜机会。

在你的代码中，每当发现获胜者时，分数会根据深度调整，这是为了优先选择最快的获胜路径。但如果评估函数无法准确评估所有可能的获胜状态，或者搜索深度不够，算法可能会错过某些获胜机会。

为了提高算法性能，你可以考虑以下改进：

• 增加搜索深度：这会让算法能够查看更多步骤，但也会增加计算复杂度。

• 改进评估函数：使其能更准确地评估棋盘状态，考虑所有可能的获胜路径。

• 考虑启发式方法：例如，优先考虑那些可能直接导致获胜或阻止对手获胜的动作。

最后，实际的游戏情况可能会影响算法的选择，所以理解算法的内部逻辑对于调试和优化至关重要。