在Minimax算法中，如果AI在达到深度0之前没有达到最终状态会发生什么？-编程知识-白鹭情

我一直在撰写一个简单的 Minimax 算法，但偶然发现了一个我无法解决的问题。该算法首先确定游戏是否结束（通过平局或任一玩家获胜）或深度是否命中== 0（depth在每个递回呼叫中减少 1）。

我遇到的问题是算法通常会很快达到深度 0（因为初始深度很低）。但是，正如我给出的伪代码所指出的那样，如果发生这种情况，算法应该回传当前板的静态评估。就我而言，该棋盘处于CONTINUE（意味着没有满足游戏结束条件）的状态。

我设定了我的评估算法，所以如果圈子获胜，它回传 -1，平局回传 0，交叉获胜回传 1。如果游戏还没有结束，我应该回传什么depth==0才不会弄乱算法的最大化/最小化？

评估代码：

int getGameResult() {
    //check for possible win
    //check vertical lines
    for (int i = 0; i <= BOARD_SIZE - 4; i  ) {
        for (int j = 0; j < BOARD_SIZE; j  ) {
            //if circle has 4 verticals
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i   1][j] == FieldStatus::CIRCLE
                && board[i   2][j] == FieldStatus::CIRCLE
                && board[i   3][j] == FieldStatus::CIRCLE) {
                return -1;
            }
            //if cross has 4 verticals
            else if (board[i][j] == FieldStatus::CROSS
                && board[i   1][j] == FieldStatus::CROSS
                && board[i   2][j] == FieldStatus::CROSS
                && board[i   3][j] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //check horizontal lines
    for (int i = 0; i < BOARD_SIZE; i  ) {
        for (int j = 0; j <= BOARD_SIZE - 4; j  ) {
            //if circle has 4 horizontals
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i][j   1] == FieldStatus::CIRCLE
                && board[i][j   2] == FieldStatus::CIRCLE
                && board[i][j   3] == FieldStatus::CIRCLE) {
                return -1;
            }
            //if cross has 4 horizontals
            else if (board[i][j] == FieldStatus::CROSS
                && board[i][j   1] == FieldStatus::CROSS
                && board[i][j   2] == FieldStatus::CROSS
                && board[i][j   3] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //check diagonals
    //right diagonals
    for (int i = 0; i < BOARD_SIZE - 3; i  ) {
        for (int j = 0; j < BOARD_SIZE - 3; j  ) {
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i   1][j   1] == FieldStatus::CIRCLE
                && board[i   2][j   2] == FieldStatus::CIRCLE
                && board[i   3][j   3] == FieldStatus::CIRCLE) {
                return -1;
            }

            if (board[i][j] == FieldStatus::CROSS
                && board[i   1][j   1] == FieldStatus::CROSS
                && board[i   2][j   2] == FieldStatus::CROSS
                && board[i   3][j   3] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //left diagonals
    for (int i = BOARD_SIZE - 1; i > BOARD_SIZE - 2; i--) {
        for (int j = 0; j < BOARD_SIZE - 3; j  ) {
            if (board[i][j] == FieldStatus::CIRCLE
                && board[i - 1][j   1] == FieldStatus::CIRCLE
                && board[i - 2][j   2] == FieldStatus::CIRCLE
                && board[i - 3][j   3] == FieldStatus::CIRCLE) {
                return -1;
            }

            if (board[i][j] == FieldStatus::CROSS
                && board[i - 1][j   1] == FieldStatus::CROSS
                && board[i - 2][j   2] == FieldStatus::CROSS
                && board[i - 3][j   3] == FieldStatus::CROSS) {
                return 1;
            }
        }
    }

    //check for draw
    for (int i = 0; i < BOARD_SIZE; i  ) {
    

        for (int j = 0; j < BOARD_SIZE; j  ) {
            if (board[i][j] != FieldStatus::EMPTY) {
                return -5; //!! This is the part that confuses me
            }
        }
    }

    return 0;
}

极小值代码（isCross基本上是指isMaximizer）：

int minimax(int depth, bool isCross) {
    //cross maximizes, circle minimizes
    //check if game is done
    if (depth == 0 && isGameOver()) {
        int result = getGameResult();
        
        if (result == -5 && isCross) {
            return 1;
        }
        else if (result == -5) {
            result = -1;
        }

        return result;
    }

    //if maximizing
    if (isCross) {
        int bestMoveScore = INT_MIN;
        for (int i = 0; i < BOARD_SIZE; i  ) {
            for (int j = 0; j < BOARD_SIZE; j  ) {
                if (board[i][j] == FieldStatus::EMPTY) {
                    board[i][j] = FieldStatus::CROSS;

                    int fieldScore = minimax(depth - 1, false);

                    board[i][j] = FieldStatus::EMPTY;
                    if (fieldScore > bestMoveScore) {
                        bestMoveScore = fieldScore;
                    }
                }
            }
        }
        return bestMoveScore;
    }
    else { //minimize
        int bestMoveScore = INT_MAX;
        for (int i = 0; i < BOARD_SIZE; i  ) {
            for (int j = 0; j < BOARD_SIZE; j  ) {
                if (board[i][j] == FieldStatus::EMPTY) {
                    board[i][j] = FieldStatus::CIRCLE;

                    int fieldScore = minimax(depth - 1, true);

                    board[i][j] = FieldStatus::EMPTY;

                    if (fieldScore < bestMoveScore) {
                        bestMoveScore = fieldScore;
                    }
                }
            }
        }
        return bestMoveScore;
    }
}

uj5u.com热心网友回复：

首先，您的代码中存在一些问题：

您写（正确地）平局被评估为 0，但代码没有这样做。相关代码为：
```
//check for draw
for (int i = 0; i < BOARD_SIZE; i  ) {    
    for (int j = 0; j < BOARD_SIZE; j  ) {
        if (board[i][j] != FieldStatus::EMPTY) {
            return -5; //!! This is the part that confuses me
        }
    }
}
return 0;
```
finalreturn 0只能在if条件永远不为真时执行，这 - 如果我们仔细观察 - 意味着所有单元格都是空的！这显然是错误的。的if条件应该是：
```
    if (board[i][j] == FieldStatus::EMPTY) {
```
并且 now-5将是在getGameResult游戏尚未结束的状态下呼叫时的回传值。它表示“我不知道价值是什么”之类的东西。
由于您有一个getGameResult函式可以正确识别游戏是否结束，因此您实际上并不需要gameOver单独的函式。如果getGameResult回传-5，那么游戏是不是结束，在所有其他情况下（-1,0或1），它是结束了。

您的代码并不总是检查游戏是否结束

int minimax(int depth, bool isCross) {
    //cross maximizes, circle minimizes
    //check if game is done
    if (depth == 0 && isGameOver()) {
        int result = getGameResult();

这段代码只会在depth为 0时检测游戏是否结束，但也有可能是游戏提前结束。所以这个条件depth == 0不应该放在这里，而是在处理完游戏结束的情况后作为一个单独的案例：

int result = getGameResult();
if (result != -5) { // Game is over!
    return result;
}
// Game is not over yet... check if we should search deeper
if (depth == 0) { // We should stop searching.
    return evaluate(); // Use some heuristic to give an estimated value
}

所以现在我们来解决你的核心问题：如何实作evaluate（在上面的代码块中使用）

对于手头的游戏，您可以使用以下特征来获得游戏的估计值：

计算一个玩家可能仍然可能的 4-in-a-row 数量。对于要计入该总和的一行 4 个单元格，它不应包含对手的任何动作。所以它们应该是空的或者有玩家自己的符号。如果对于 4 个单元格的行是这样，则它应该作为 1 贡献给为所有 4 个单元格的行计算的总和。从每个玩家的角度分别计算这个总和。
为了改进，如果在这些潜在的 4 行中，有一些被玩家占据了 3，那么给它们更多的权重（比如将它们计为 3 而不是总和中的 1）。类似地，对那些占用 2 个单元格的应用系数。
给定这样计算的两个总和，计算差异。如果为正，则表示它对 X 玩家有利，否则对 O 玩家有利。
最后转换这个数字（例如除以 1000），以保证它在 (-1, 1) 之间，并且与赢/输的值不同。使用整数可能会更好，因此使用值 1000 和 -1000 来表示输赢，而不是 1 和 -1。

uj5u.com热心网友回复：

如果您无法对树进行足够远的评估以到达游戏结束，那么您需要有一些函式可以为不完整的游戏状态生成近似分数。因此，如果 1 表示交叉获胜，那么 0 和 1 之间的数字表示他们获胜的可能性越来越大，而 0 和 -1 之间的数字表示他们可能会失败。这个评估函式的细节完全取决于你正在玩的游戏，可能并不明显这样做的“正确”函式是什么。

例如，在国际象棋中，您可以撰写以下一些函式来尝试估计谁获胜：

将玩家 A 的棋子数相加，减去玩家 B 的棋子数
与 #1 相同，但相对于它们通常的好坏来衡量棋子（例如，皇后比棋子更有价值）
与#2 相同，但撰写一些复杂的逻辑来查看片段的排列，以尝试猜测这种排列是否好。也许它会给有许多可用动作的棋子提供奖励，而不是被困在其他棋子后面，或者当棋子对角排列以相互支持时会增加奖励。
与 #3 相同，但使用神经网络和数十亿个训练游戏为您生成复杂的逻辑。

你的游戏有什么好的评价函式？恐怕我真的没有一个很好的答案给你。弄清楚这一点需要一些游戏专业知识，并且很可能需要一些实验。首先，也许您可??以做一些事情来确定哪些部分是“死的”（即，它们被包围，因此它们不能促成一行 4），然后总结剩余的部分。