在 Minimax 算法中，如果 AI 在达到深度 0 之前没有达到终止状态，会发生什么情况？

Question

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

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

我设置了评估算法，因此 returns -1 如果循环获胜，0 表示平局，1 表示交叉获胜。如果游戏在 depth==0 还没有结束，我应该 return 做什么才不会搞乱算法的 maximizing/minimizing？

评价码：

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;
}

minimax代码（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;
    }
}

Answer 1

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

例如在国际象棋中，您可以编写一些函数来尝试估计谁是赢家：

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

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

Answer 2

首先你的代码有一些问题：

你写（正确地）平局被评估为 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;
```
最后的 return 0 只能在 if 条件永远不为真时执行，如果我们仔细观察的话，这意味着 all细胞是空的！这显然是错误的。 if条件应该是：
```
    if (board[i][j] == FieldStatus::EMPTY) {
```
，现在 -5 将是 return 值，只要在游戏尚未结束的状态下调用 getGameResult 。它表示类似于 “我不知道值是什么”。
因为你有一个 getGameResult 函数，它会正确地识别游戏是否结束，所以你真的不需要 gameOver 作为一个单独的函数。如果 getGameResult returns -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不应该放在这里，而是作为一个单独的案例在处理完game-over的情况后：

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

在 Minimax 算法中，如果 AI 在达到深度 0 之前没有达到终止状态，会发生什么情况？

In a Minimax algorithm, what happens if an AI doesn't reach a terminal state before hitting depth 0?

javascript

python

algorithm

tic-tac-toe