Minimax 不能在井字游戏中正确计分分支

Question

我正在尝试用 C 语言创建完美的井字游戏。我正在使用 2D 数组来跟踪棋盘。

我已将问题缩小到我的 minimax 函数对每个潜在动作进行评分的方式，但我无法调试它，因为错误通常发生在第二步左右，而且我无法跟踪从那一点开始的所有潜在游戏状态。

计算机先行，永远是'X'。 minimax 是从 computerMove 函数中调用的，该函数尝试每个可用的移动，然后将它们最小化。它将从 minimax 中为潜在游戏状态返回的值作为临时分数，并将其与当前最高分数进行比较。我相信该计划的一部分正在发挥作用。问题出在minimax函数本身

这是我的代码的重要部分：

int minimax(char board[][3], char maxPlayer) // +10 -> X wins 
{                                            // -10 -> O wins
    char minPlayer;                          //   0 -> draw
    int scores[3][3];
    if (maxPlayer == 'X') minPlayer = 'O';
    else minPlayer = 'X';
    int topScore = 0;

    // initializing scores to ensure a move is selected
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scores[i][j] = -11;
        }
    }

    // check for terminal state
    if (isWinning(board,'X') || isWinning(board,'O') || 
    !moveAvailable(board)) {
        if (isWinning(board,'X')) return 10;
        else if (isWinning(board,'O')) return -10;
        else return 0;
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 'U') { 
                board[i][j] = maxPlayer;                // try the move
                scores[i][j] = minimax(board,minPlayer);// minimax it
                board[i][j] = 'U';                      // undo the move
            }
        }
    }  

    // if calling minimax for computer, maximize the score
    if (maxPlayer == 'X') {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (scores[i][j] > topScore && scores[i][j] != -11) 
                    topScore = scores[i][j];
            }
        }
    }

    // if calling minimax for human, minimize the score
    else if (maxPlayer == 'O') {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (scores[i][j] < topScore && scores[i][j] != -11) 
                    topScore = scores[i][j];
            }
        }
    }
    return topScore;
}

Answer 1

问题在于 topScore 初始化：

你应该将 topScore 初始化为 11 或 -11，这取决于谁玩，而不是 0，否则双方玩家都会相信他们至少总能达到平局（事实并非如此)，从深度 2 开始。
就良好实践（恕我直言）而言，我认为最后两个循环应该合并为一个，其中包含 if (maxPlayer == 'X') 条件，就在更新 [=10 之前=].另外，你应该跳过所有 board[i][j]!='U' 的位置，它比 lookinf for -11 in scores 更容易理解（虽然这很好）。

Minimax 不能在井字游戏中正确计分分支

Minimax not scoring branches correctly in tic-tac-toe

c

algorithm

tic-tac-toe

minimax