tic_tac_toe AI 的 minimax 错误

Question

我一直在尝试使用 minimax 和 alpha-beta 修剪为计算机实现 AI，但我遇到了一个无法识别的错误。该算法应该计算自己和其他玩家的所有可能移动，但它没有按照应有的方式回放。

这是我的 minimax 代码：

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) = 检查棋盘上可能获胜或抽出的棋盘或不完整的棋盘，returns 获胜者为 1 或 2（玩家 X 或 O），平局为 0，和 -1 表示不完整的板。

util.filterboard(int[] newboard) = returns 包含给定棋盘中所有空位置的数组列表。

util.changeside(char symbol) = 简单地将 X 翻转为 O，将 O 翻转为 X，然后 returns 结果。

我试过将深度设置为 2，这意味着它将计算接下来的 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

但它仍然无法识别我的胜利。

所有其他功能都已在用户对战用户时进行了测试，它们都运行良好。我将不胜感激。

我很乐意提供我的完整代码，如有必要和任何其他要求。

Answer 1

几点观察。

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

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

因为目前你的算法将 return 0（得分，对应于平局）每当它到达零深度时（而零深度的实际位置可能不相等 - 例如，其中一侧可以有很大的优势）。 EvaluatePosition() 函数应该反映当前的棋盘位置（它应该像 "X has an advantage"、"O is losing"、"The position is more or less equal" 等，用数字表示）。请注意，这仅在触发 depth == 0 条件时才有意义，否则无关紧要。

2) 你真的需要这个 emptyboard 东西吗？您可以遍历新棋盘的所有方块，一旦找到一个空方块，复制原始棋盘，在这个空方块上移动并使用复制和更新的棋盘调用 minimax。在伪代码中它看起来像这样：

for square in board.squares: if square is empty: board_copy = Copy(board) board_copy.MakeMove(square) score = minimax(board_copy, /*other arguments*/) /*the rest of minimax function*/

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

4) 检查你的算法在没有alpha-beta修剪的情况下是否正确。 plain minimax 和 alpha-beta pruning minimax 的结果应该是一样的，但是 plain minimax 更容易理解、编码和调试。在您的普通 minimax 正常工作后，添加增强功能，如 alpha-beta 剪枝等。

tic_tac_toe AI 的 minimax 错误

Bug in minimax for tic_tac_toe AI

c#

artificial-intelligence

tic-tac-toe

minimax