具有奇怪行为的井字游戏极小极大算法（C++）

Question

前几天，我用c++为我儿子写了一个Tic-Tac-Toe的主机游戏。他想让我加一台电脑，我就结束了我们第一次使用 minimax 算法。我做了一些快速测试，但实际上只是在打印东西时就把我的笔记本电脑给了我的儿子，他玩了几小步舞曲。我查看了他的 sholder 一两次，发现它的播放效果不佳，我一直在尝试调试它，但我看不出哪里出了问题。我尝试摆脱 alpha beta 修剪，但这并没有改变任何东西。

对于上下文，在棋盘上计算机是-1，空白是0，玩家是1。

这是极小极大函数：

int minimax(int board[9], int depth, int alpha, int beta, bool isMaxizimaizingPlayer)
{
    bool found = false;
    for (int i = 0; i < 9; i++)
    {
        if (board[i] == 0)
        {
            found = true;
        }
    }
    if (!found)
    {
        return eval(board);
    }
    if (depth == 0 || eval(board) != 0)
    {
        return eval(board);
    }
    if (isMaxizimaizingPlayer) 
    {
        int maxEval = -2;
        for (int spot = 0; spot < 9; spot++) 
        {
            if (board[spot] == 0)
            {
                board[spot] = 1;
                int e = minimax(board, depth - 1, alpha, beta, false);
                if (e > maxEval)
                {
                    maxEval = e;
                }
                //if (beta < alpha) 
                //{
                //  break;
                //}
                board[spot] = 0;
            }
        }
        return maxEval;
    }
    else {
        int minEval = 2;
        for (int spot = 0; spot < 9; spot++)
        {
            if (board[spot] == 0)
            {
                board[spot] = -1;
                int e = minimax(board, depth - 1, alpha, beta, true);
                if (e < minEval)
                {
                    minEval = e;
                }
                //if (beta < alpha)
                //{
                //  break;
                //}
                board[spot] = 0;
            }
        }
        return minEval;
    }
}

为了完整起见，这是我的评估函数：

int eval(int board[9]) 
{
    /*horizontial*/
    for (int i = 0; i < 3; i++) 
    {
        if (board[i * 3] == board[i * 3 + 1] && board[i * 3 + 2] == board[i * 3] && board[i * 3] != 0) 
        {
            return board[i * 3];
        }
    }
    /*vertical*/
    for (int i = 0; i < 3; i++)
    {
        if (board[i] == board[i + 3] && board[i] == board[i + 6] && board[i] != 0)
        {
            return board[i];
        }
    }
    /*Both diags*/
    if (board[4] != 0) {
        if (board[0] == board[4] && board[0] == board[8])
        {
            return board[4];
        }
        if (board[2] == board[4] && board[4] == board[6])
        {
            return board[4];
        }
    }
    return 0;
}

这是初始调用：

            int spot = 0;
            int minEval = 2;
            for (int i = 0; i < 9; i++) 
            {
                if (board[i] == 0) 
                {
                    board[i] = -1;
                    int score = minimax(board, 3, -2, 2, false);
                    if (score < minEval) {
                        minEval = score;
                        spot = i;
                    }
                    board[i] = 0;
                }
            }
            std::cout << "The computer went in spot " << spot + 1 << std::endl;
            board[spot] = -1;
            printBoard(board);

Answer 1

看起来你只调用了深度为三的 minimax，所以算法只会向前看三步，如果你想要最优游戏你需要将深度设置为 > 9，这样代理是总是期待比赛的结束。

具有奇怪行为的井字游戏极小极大算法（C++）

Tic tac toe Minimax Algorithm Having Weird Behavior (C++)

c++

artificial-intelligence

tic-tac-toe

minimax