TicTacToe Minimax 算法总是 Returns 最低值

Question

我正在尝试使用 minimax 算法实现 TicTacToe AI。

轮到 AI 下棋时，我调用 ComputerTurn（它接收棋盘状态，一个整数数组，用于跟踪正方形是 X、O 还是空）。 ComputerTurn 然后调用 minimax（minimax 算法）和 win（连续检查 3 个）。

当我运行脚本时，算法总是决定return最低的合法播放。 IE，只要左上角的方块（tile 0）可用，它总是先 return 它。如果该方块被占用，它将 return 顶部中间（图块 1）等

我不确定这里发生了什么，我的传统调试技术（Debug.Log 或打印）导致 Unity 在我想查看的许多地方崩溃。

void ComputerTurn(int[] board)
{
    int move = -1;
    int score = -2;
    int i;
    for (i = 0; i < 9; ++i)
    {
        if (board[i] == 0)
        {
            board[i] = 1;
            int tempScore = -minimax(board, -1);
            board[i] = 0;
            if (tempScore > score)
            {
                score = tempScore;
                move = i;
            }
        }
    }

    board[move] = 1;
    if (PlayerTurn == 1)
    {
        //Draw an O
        Board[move] = -1;
    }
    else
    {
        //Draw an X
        Board[move] = 1;
    }
    //Changes to player's turn
}

int minimax(int[] board, int player)
{
    int winner = win(board);
    if (winner != 0) return winner * player;

    int move = -1;
    int score = -2;//Losing moves are preferred to no move
    int i;
    for (i = 0; i < 9; ++i)
    {//For all moves,
        if (board[i] == 0)
        {//If legal,
            board[i] = player;//Try the move
            int thisScore = -minimax(board, player * -1);
            if (thisScore > score)
            {
                score = thisScore;
                move = i;
            }//Pick the one that's worst for the opponent
            board[i] = 0;//Reset board after try
        }
    }
    if (move == -1) return 0;
    return score;
}

int win(int[] board) 
{
    //determines if a player has won, returns 0 otherwise.
    int[,] wins = new int[8, 3] { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } };
    int i;
    for (i = 0; i< 8; ++i)
    {
        if (board[wins[i, 0]] != 0 &&
            board[wins[i, 0]] == board[wins[i, 1]] &&
            board[wins[i, 0]] == board[wins[i, 2]])
        {
            return board[wins[i, 2]];
        }
    }
    return 0;
}

Answer 1

它并不总是 return 第一个空单元格。例如，尝试用 [0, 0, 0, -1, 0, -1, 1, 0, 1] 位置喂它：它不会 return 0，它会选择 4。您的实施不包含任何错误。

问题出在算法上。由于您的权重函数只能导致 1、0 或 -1，您的程序只能查看是否有可能在该回合获胜，但看不到强步（胜利输出高）和弱步之间的任何区别（有可能获胜，但可能性不大）。它过滤掉了松动的动作，正如您从提供的示例中看到的那样。

Answer 2

编辑：如何将其标记为已解决

我知道发生了什么事。

board[move] = 1;
if (PlayerTurn == 1)
{
    //Draw an O
    Board[move] = -1;
}
else
{
    //Draw an X
    Board[move] = 1;
}
//Changes to player's turn

实际上应该是

Board[move] = 1;

if (PlayerTurn == 1)
{
    //Draw a Y
}
else
{
    //Draw an X
}

//Change turn

我的玩家回合也有错误。感谢所有看过我问题的人。

TicTacToe Minimax 算法总是 Returns 最低值

TicTacToe Minimax Algorithm Always Returns Lowest Value

c#

algorithm

debugging

unity3d

minimax