tima_tac_toe AI的minimax中的错误

Question

我一直在尝试使用带有alpha-beta修剪的minimax为计算机实现AI，但我面临一个无法识别的bug。该算法应该计算自己和其他玩家的所有可能的移动，但它不会以它应该的方式回放。

这是我的极小极大代码：

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

但它仍然没有认识到我的胜利举动。

所有其他功能在用户对抗用户时都已经过测试，并且它们都运行良好。我将不胜感激。

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

Answer 1

几点意见。

1）if (depth == 0) return 0;应改为类似的东西

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

因为目前你的算法在到达深度零时将返回0（得分，对应于平局）（而在零深度的实际位置可能不相等 - 例如，其中一方可以具有巨大的优势）。 EvaluatePosition()函数应该反映当前的董事会职位（它应该说“X有优势”，“O正在失去”，“职位或多或少等于”等，表示为数字）。请注意，这仅在触发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修剪的情况下检查您的算法是否正确。普通minimax和alpha-beta修剪minimax的结果应该是相同的，但是普通的minimax更容易理解，编码和调试。在您的普通极小极大运行正常后，添加增强功能，如alpha-beta修剪等。