我尝试使用带有alpha-beta剪枝的极小化极大算法来实现计算机的AI，但遇到了一个无法识别的错误。该算法应该计算自己和对手的所有可能移动，但它并没有按预期的方式进行回放。

这是我的极小化极大算法代码：

public int minimax(int[] board, char symbol, int alpha, int beta, int depth = 2){    int win = util.checkwin(board);    int nsymbol = (symbol == 'X' ? 1 : 2);    int mult = (symbol == compside ? 1 : -1);    if (win != -1)    {        if (win == nsymbol)            return mult;        else if (win != 0)            return (mult * -1);        else            return 0;    }    if (depth == 0)        return 0;    int[] newboard = new int[9];    Array.Copy(board, newboard, 9);    int score, i, pos = -1;    ArrayList emptyboard = new ArrayList();    emptyboard = util.filterboard(newboard);    for (i = 0; i < emptyboard.Count; i++)    {        if (i > 0)            newboard[(int)emptyboard[i - 1]] = 0;        newboard[(int)emptyboard[i]] = nsymbol;        score = minimax(newboard, util.changeside(symbol), alpha, beta, depth - 1);        if (mult == 1)        {            if (score > alpha)            {                alpha = score;                pos = (int)emptyboard[i];            }            if (alpha >= beta)                break;        }        else        {            if (score < beta)                beta = score;            if (alpha >= beta)                break;        }    }    if (depth == origdepth)        return pos;    if (mult == 1)        return alpha;    else        return beta;}

未定义函数的详细信息：

util.checkwin(int[] board) = 检查棋盘是否有赢家或平局或未完成的棋局，并返回赢家为1或2（玩家X或O），平局返回0，未完成的棋局返回-1。

util.filterboard(int[] newboard) = 返回一个包含棋盘上所有空位置的ArrayList。

util.changeside(char symbol) = 简单地将X翻转为O，将O翻转为X，并返回结果。

我尝试将深度设置为2，这意味着它将计算接下来的两步（如果它能赢和如果对手能赢）。但结果与我预期的不符，并且它偶尔会尝试在已填充的位置下棋。

这是输出（深度=2）：

 Turn: X  |   |1 | 2 | 3__|___|__  |   |4 | 5 | 6__|___|__  |   |7 | 8 | 9  |   |Enter Your Choice: Turn: O  |   |1 | 2 | 3__|___|__  |   |X | 5 | 6__|___|__  |   |7 | 8 | 9  |   |Enter Your Choice: 5 Turn: X  |   |1 | 2 | 3__|___|__  |   |X | O | 6__|___|__  |   |7 | 8 | 9  |   |Enter Your Choice: Turn: O  |   |1 | X | 3__|___|__  |   |X | O | 6__|___|__  |   |7 | 8 | 9  |   |Enter Your Choice: 1 Turn: X  |   |O | X | 3__|___|__  |   |X | O | 6__|___|__  |   |7 | 8 | 9  |   |Enter Your Choice: Turn: O  |   |O | X | 3__|___|__  |   |X | O | 6__|___|__  |   |7 | X | 9  |   |Enter Your Choice: 9  |   |O | X | 3__|___|__  |   |X | O | 6__|___|__  |   |7 | X | O  |   |O Wins

但它仍然无法识别我的获胜移动。

所有其他功能在用户对用户的游戏中都已测试过，并且都正常工作。我希望能得到一些帮助。

如果需要，我很乐意提供我的完整代码，以及任何其他所需的信息。

回答：

有几个观察点。

1) if (depth == 0) return 0; 应该改为类似于

if (depth == 0) return EvaluatePosition();,

因为目前你的算法在达到零深度时会返回0（对应于平局），而实际在零深度的位置可能并不相等——例如，一方可能有巨大的优势。EvaluatePosition() 函数应该反映当前棋盘位置（它应该表示“X有优势”，“O正在输”，“位置大致相等”等，用数字表示）。请注意，只有在触发depth == 0条件时，这才重要，否则无关紧要。

2) 你真的需要这个emptyboard东西吗？你可以遍历newboard的所有方格，一旦找到一个空方格，就复制原始棋盘，在这个空方格上进行移动，并使用复制的和更新的棋盘调用极小化极大算法。伪代码看起来像这样：

for square in board.squares: if square is empty: board_copy = Copy(board) board_copy.MakeMove(square) score = minimax(board_copy, /*other arguments*/) /*极小化极大函数的其余部分*/

3) if (alpha >= beta) break; 部分在两个分支中都存在（对于mult == 1和mult != 1），所以你可以将其放在if-else块之后，以减少代码重复。

4) 检查你的算法在没有alpha-beta剪枝的情况下是否正确。普通极小化极大算法和带alpha-beta剪枝的极小化极大算法的结果应该相同，但普通极小化极大算法更容易理解、编写和调试。在你的普通极小化极大算法正常工作后，再添加像alpha-beta剪枝这样的增强功能和其他功能。