tic_tac_toeAI的极小值错误

Question

我一直在尝试使用极小值和阿尔法-贝塔修剪为计算机实现人工智能，但我面临着一个无法识别的错误。算法应该计算自己和其他玩家的所有可能移动，但它没有以应有的方式回放。

这是我的最小值代码：

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[]棋盘）=检查棋盘是否有可能获胜或平局或不完整的棋盘，并将获胜者返回为1或2（玩家X或O），0表示平局，以及-1表示不完整的棋盘。

util。filterboard（int[]newboard）=返回一个数组列表，其中包含给定板中所有空位置的位置。

util.changeside（char符号）=简单地将X翻转到O，将O翻转到X并返回结果。

我尝试了深度为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）返回0 应该更改为

if（depth==0）返回EvaluatePosition（） ，

因为当前算法在达到深度0时将返回0（分数，对应于平局）（而在深度0处的实际位置可能不相等——例如，其中一条边可能具有巨大优势）EvaluatePosition（）函数应该反映当前的电路板位置（它应该说“X有优势”、“O正在失去”、“位置大致相等”等，用数字表示）。请注意，只有当触发了depth==0条件时，这才有意义，否则就无关紧要了。

2） 你真的需要这个emptyboard的东西吗？你可以在新棋盘的所有方块上迭代，一旦你找到一个空方块，复制原始棋盘，在这个空方块上移动，并用复制和更新的棋盘调用minimax。在伪代码中，它将如下所示：

用于板内正方形。方块：如果方块为空：board_copy=复制（board）board_copy。MakeMove（square）score=minimax（board_copy，/*其他参数*/）/*minimax函数的其余部分*/

3） if（α

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