Tic-Tac-Toe 的这个 Minimax 实现有什么问题？

Question

我想扩展我制作的一款较旧的井字游戏，让两个玩家可以互相对战。我想让用户选择与困难的 AI 对战。问题是 AI 不会一直选择最佳着法。例如，如果先走，它总是会选择位置 1。如果用户选择地点 2，它会选择地点 4。此后，无论用户选择什么（地点 7 除外），AI 都不会选择地点 7。AI 的胜利远非不可避免（用户仍然可以获胜此时的游戏），所以这不是问题。

感谢任何帮助。谢谢！

我确定问题出在我的 minimax 或 bestmove 函数上。可能只是我没有正确实现minimax函数，但我找不到问题。

#include <iostream>
#include <iomanip>
#include <string>
#include <array>

// This is a program to play a single game of tic-tac-toe
// between either two human (non-AI) players or an AI.

using namespace std;

void PrintBoard(array <char, 9>);
int programprogress();
int checkwin(array <char, 9>);
int minimax(array <char, 9>, int, int, bool);
int bestMove(array <char, 9>, int);
int Opposite(int);
char PlayerSymbol(int);

const int SIZE = 9;
array <char, SIZE> Pos = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
int player_number = 1;
int k = -11, result;
bool AI = false, first;

// Global variables used by 2 or more functions.
// Array had to be initialized with numbers instead of blank spaces
// because the check win function wouldn't work properly.

int main()
{
    string userinp;

    cout << "This is tic tac toe! Here's your board!" << endl;
    PrintBoard(Pos);

    cout << "Would you like to play versus an AI? (Y/N)" << endl;
    cin >> userinp;
    if (userinp[0] == 'Y')
    {
        cout << "Excellent! Would you like to start first, or second? (F/S)" << endl;
        cin >> userinp;
        if (userinp[0] == 'F')
        {
            cout << "You will start first!" << endl;
            first = false;
            player_number = 2;
        }

        else
        {
            cout << "The AI will start first!" << endl;
            first = true;
        }
        AI = true;
    }

    else
    {
        cout << "Excellent! Your game will start soon." << endl;
    }

    result = programprogress();
    player_number--;
    PrintBoard(Pos);

    if (result == 1)
        cout << endl << "Player " << player_number << " has won!!!\n";
    else if (result == 10)
        cout << endl << "The AI has won! Better luck next time!\n";
    else if (result = -10)
        cout << endl << "You beat the world's best AI! Congratulations!\n";
    else
        cout << endl << "The game has been drawn!" << endl;
    return 0;
}

void PrintBoard(array <char, 9> Pos)
{
    system("cls");
    cout << setw(6) << "|" << setw(6) << "|" << endl << setw(3) << Pos[0] << setw(3) << "|" << setw(3) << Pos[1] << setw(3) << "|" << setw(3) << Pos[2] << "     TIC           TOE" << endl;
    cout << "_____|_____|_____" << endl;
    cout << setw(6) << "|" << setw(6) << "|" << endl << setw(3) << Pos[3] << setw(3) << "|" << setw(3) << Pos[4] << setw(3) << "|" << setw(3) << Pos[5] << "            TAC   " << endl;
    cout << "_____|_____|_____" << endl;
    cout << setw(6) << "|" << setw(6) << "|" << endl << setw(3) << Pos[6] << setw(3) << "|" << setw(3) << Pos[7] << setw(3) << "|" << setw(3) << Pos[8] << "     TIC            TOE  " << endl;
    cout << "     |     |" << endl;
}


int programprogress()
{
    while (k == -11 && AI)
    {
        bool InvalidChoice = false;
        char letter;
        //player_number = (player_number % 2) ? 1 : 2;
        int PlayerChoice;

        if (player_number == 2)
        {
            cout << endl << "What is your move?" << endl;
            cin >> PlayerChoice;

            while ((PlayerChoice < 1) || (PlayerChoice > 9))
            {
                cout << "That's an invalid choice! Please choose a number that is 1-9!" << endl;
                cin >> PlayerChoice;
            }

            PlayerChoice--;
            letter = (!first) ? 'X' : 'O';

            if (Pos[PlayerChoice] == '1' || Pos[PlayerChoice] == '2' || Pos[PlayerChoice] == '3' || Pos[PlayerChoice] == '4' || Pos[PlayerChoice] == '5' || Pos[PlayerChoice] == '6' || Pos[PlayerChoice] == '7' || Pos[PlayerChoice] == '8' || Pos[PlayerChoice] == '9')
            {
                Pos[PlayerChoice] = letter;
                PrintBoard(Pos);
            }
            /*else
            {
                cout << "That space is already taken!" << endl;
                player_number--;
            }*/
            k = checkwin(Pos);
            if (k != -11)
                k = k * -10;
            player_number = 1;
        }
        else
        {
            cout << endl << "The computer has made its move!" << endl;

            letter = (first) ? 'X' : 'O';
            if (first)
                PlayerChoice = bestMove(Pos, 1);
            else
                PlayerChoice = bestMove(Pos, 2);

            Pos[PlayerChoice] = letter;
            PrintBoard(Pos);

            k = checkwin(Pos);
            if (k != -11)
                k = k * 10;

            player_number = 2;
        }
    }

    while (k == -11 && !AI)
    {
        bool InvalidChoice = false;
        char letter;
        player_number = (player_number % 2) ? 1 : 2;
        int PlayerChoice;

        cout << endl << "What's player " << player_number << "'s move?" << endl;
        cin >> PlayerChoice;

        while ((PlayerChoice < 1) || (PlayerChoice > 9))
        {
            cout << "That's an invalid choice! Please choose a number that is 1-9!" << endl;
            cin >> PlayerChoice;
        }

        PlayerChoice--;
        letter = (player_number == 1) ? 'X' : 'O';

        if (Pos[PlayerChoice] == '1' || Pos[PlayerChoice] == '2' || Pos[PlayerChoice] == '3' || Pos[PlayerChoice] == '4' || Pos[PlayerChoice] == '5' || Pos[PlayerChoice] == '6' || Pos[PlayerChoice] == '7' || Pos[PlayerChoice] == '8' || Pos[PlayerChoice] == '9')
        {
            Pos[PlayerChoice] = letter;
            PrintBoard(Pos);
        }
        else
        {
            cout << "That space is already taken!" << endl;
            player_number--;
        }
        k = checkwin(Pos);

        player_number++;
    }
    return k;
}

int checkwin(array <char, SIZE> Pos)
{
    if (Pos[0] == Pos[1] && Pos[1] == Pos[2])

        return 1;
    else if (Pos[3] == Pos[4] && Pos[4] == Pos[5])

        return 1;
    else if (Pos[6] == Pos[7] && Pos[7] == Pos[8])

        return 1;
    else if (Pos[0] == Pos[3] && Pos[3] == Pos[6])

        return 1;
    else if (Pos[1] == Pos[4] && Pos[4] == Pos[7])

        return 1;
    else if (Pos[2] == Pos[5] && Pos[5] == Pos[8])

        return 1;
    else if (Pos[0] == Pos[4] && Pos[4] == Pos[8])

        return 1;
    else if (Pos[2] == Pos[4] && Pos[4] == Pos[6])

        return 1;
    else if (Pos[0] != '1' && Pos[1] != '2' && Pos[2] != '3'
        && Pos[3] != '4' && Pos[4] != '5' && Pos[5] != '6'
        && Pos[6] != '7' && Pos[7] != '8' && Pos[8] != '9')

        return 0;
    else
        return -11;
}

int minimax(array <char, SIZE> newpos, int depth, int player, bool opp)
{
    int scale = 0;

    if ((player == 1 && first) || (player == 2 && !first))
        scale = 10;
    else
        scale = -10;
    //cout << scale;
    int score = scale*checkwin(newpos);

    if (score < 0)
        score += depth;
    else if (score > 0)
        score -= depth;

    if (score == -10 || score == 10 || score == 0)
        return score;

    if (opp)
    {
        int best = -1000;

        for (int i = 0; i < SIZE; i++)
        {
            if (newpos[i] != 'X' && newpos[i] != 'O')
            {
                char temp = newpos[i];

                newpos[i] = PlayerSymbol(player);

                best = max(best, minimax(newpos, depth + 1, Opposite(player), !opp));

                newpos[i] = temp;
            }
        }
        return best;
    }

    else
    {
        int best = 1000;

        for (int i = 0; i < SIZE; i++)
        {
            if (newpos[i] != 'X' && newpos[i] != 'O')
            {
                char temp = newpos[i];

                newpos[i] = PlayerSymbol(player);

                best = min(best, minimax(newpos, depth + 1, Opposite(player), !opp));

                newpos[i] = temp;
            }
        }
        return best;
    }

}

int bestMove(array <char, SIZE> newpos, int player)
{
    int best = -1000;
    int bestpos = -1;

    for (int i = 0; i < SIZE; i++)
    {
        if (newpos[i] != 'X' && newpos[i] != 'O')
        {
            char temp = newpos[i];

            newpos[i] = PlayerSymbol(player);

            int move = minimax(newpos, 0, player, !first);

            newpos[i] = temp;

            if (move > best)
            {
                //cout << "I like pineapple on pizza" << endl;
                bestpos = i;
                best = move;
            }
            /*if (move == best)
            {
                cout << "I like pineapple on pizza" << endl;
            }*/
        }
    }
    cout << bestpos;
    return bestpos;
}

int Opposite(int x)
{
    if (x == 1)
        return 2;
    else
        return 1;
}

char PlayerSymbol(int x)
{
    if (x == 1)
        return 'X';
    else
        return 'O';
}

由于 bestpos 的 -1 值导致越界错误。不过，我不确定如何更改它。

Answer 1

我能找到 4 个问题。解决它们似乎会导致预期的行为。

首先，当您从 bestMove 函数内部调用 minimax(newpos, 0, player, !first); 时，您传递的是 player 而不是 Opposite(player)，这表明第一个 minimax 步骤将由与 bestMove 步骤相同的玩家执行。换句话说：人工智能为自己做了两个连续的动作。因此 player 需要改为 Opposite(player).

其次，minimax 有一个名为 opp 的 bool 变量，它似乎表明是 AI 还是它的对手在移动。对于第一个minimax步，opp设置为!first，表示只有AI先走，对手才会在AI之后走。那是不正确的。始终是对手在 AI 之后采取行动。所以 bestMove 应该用 true 而不是 !first 来调用 minimax。顺便说一句，opp 是多余的，因为您可以使用 (player == 1 && first) || (player == 2 && !first) 来检查是 AI 还是它的对手在移动。

第三，scale设置错误。使用 (player == 1 && first) || (player == 2 && !first) 你可以检查 AI 是否在移动。但是您在下一步 minimax 中执行此操作，即在可能获胜的步骤之后。因此，如果 AI 正在下棋并且游戏已经获胜，那么是对手而不是 AI 下了制胜棋。因此，比例应该是

if ((player == 1 && first) || (player == 2 && !first))
    scale = -10;
else
    scale = 10;

相反。

最后，你在加上depth后检查score是10还是-10。如果 depth 不为 0，则此检查将始终失败。所以在深度 0 之后，AI 只能看到平局，而永远看不到胜利。你可以改写

if (score == -10 || score == 10 || score == 0)
{
    if (score < 0)
        score += depth;
    else if (score > 0)
        score -= depth;

    return score;
}

希望这能完全回答您的问题。

Tic-Tac-Toe 的这个 Minimax 实现有什么问题？

What's wrong with this Minimax implementation for Tic-Tac-Toe?

c++

recursion

minimax