时间戳

首页 > 解决方案 > Tic-Tac-Toe 的 Minimax 实现有什么问题？

c++ - Tic-Tac-Toe 的 Minimax 实现有什么问题？

问题描述

我想扩展我制作的一个较旧的井字游戏，两个玩家可以互相对战。我想让用户选择对抗一个困难的 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 值导致的越界错误。不过，我不确定如何更改。

标签： c++recursionminimax

解决方案

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

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

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

第三，scale设置错误的方式。和(player == 1 && first) || (player == 2 && !first)你一起检查它是否是人工智能在行动。但是你在下一步中这样做，在minimax潜在的获胜动作之后。因此，如果 AI 正在走棋并且游戏已经赢了，那么是对手走的，而不是 AI 走的。因此，规模应该是

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

反而。

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

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

    return score;
}

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

推荐阅读