最小最大算法驱动的C++ - Tac Tac Toe AI

Question

这是我在C++的Tac脚趾上的以前的职位。我收到了很好的反馈，并试图实施所有的改进。由于人工智能所需的功能或复杂性，我无法实现一些。

我想知道我能在哪里-

• 优化性能。
• 提高我的Tic Tac脚趾课。
• 提高我的人工智能。
• 改善UX。
• 遵循C++惯例(我仍然喜欢snake_case)

这是我的代码：

#include <iostream>
#include <list>
#include <algorithm>

class TicTacToe;
class AI;
void play_game(TicTacToe game);

class TicTacToe
{
private:
    char board[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '};
    char current_turn = 'X';
    char winner = ' '; // ' ' refers to None
    int state = -1;    // -1 refers to running
    std::list<int> move_stack;
    void swap_turn();
    void update_state();

public:
    friend class AI;
    friend void play_game(TicTacToe game);

    void print_board() const;
    int play_move(int index);
    void undo_move();
    std::list<int> get_possible_moves();
};

class AI
{
private:
    int max(TicTacToe board, char max_symbol, int depth);
    int min(TicTacToe board, char max_symbol, int depth);

public:
    int minmax(TicTacToe board, char max_symbol);
};

int main()
{
    TicTacToe game;
    play_game(game);
    return 0;
}

void play_game(TicTacToe game)
{
    bool playing = true;
    int move;
    int count = 0;
    AI my_ai;

    while (playing)
    {
        game.print_board();
        if (count % 2 == 1)
        {
            move = my_ai.minmax(game, game.current_turn);
        } else
        {
            std::cout << "Enter your move (1-9)\n";
            std::cin >> move;
            if (!std::cin) 
            {
                std::cerr << "Input error\n";
                return;
            }
            --move;
        }

        if (game.play_move(move) == 0)
        {
            std::cout << "Box already occupied\n";
            continue;
        }

        if (game.state == 1)
        {
            game.print_board();
            std::cout << game.winner << " wins the game!\n";
            playing = false;
        } else if (game.state == 0)
        {
            game.print_board();
            std::cout << "Draw!\n";
            playing = false;
        };
        ++count;
    };
};

void TicTacToe::print_board() const
{
    for (int i = 0; i < 9; ++i)
    {
        if (i % 3)
        {
            std::cout << " | ";
        }
        std::cout << board[i];
        if (i == 2 || i == 5)
        {
            std::cout << "\n";
            std::cout << "---------"
                      << "\n";
        }
    }
    std::cout << "\n";
};

void TicTacToe::swap_turn()
{
    current_turn = (current_turn == 'X') ? 'O' : 'X';
}

int TicTacToe::play_move(int index)
{
    if (index >= 0 && index < 9)
    {
        if (board[index] == ' ')
        {
            board[index] = current_turn;
            move_stack.push_back(index);
            update_state();
            swap_turn();
            return 1;
        }
    }
    return 0;
};

void TicTacToe::undo_move()
{
    int move = move_stack.back();
    board[move] = ' ';
    move_stack.pop_back();
    update_state();
    swap_turn();
};

std::list<int> TicTacToe::get_possible_moves()
{
    std::list<int> possible_moves;
    for (int i = 0; i < 9; ++i)
    {
        bool found = (std::find(move_stack.begin(), move_stack.end(), i) != move_stack.end());
        if (!found)
        {
            possible_moves.push_back(i);
        }
    }
    return possible_moves;
}

void TicTacToe::update_state()
{
    if (
        // Horizontal checks
        (board[0] == current_turn && board[1] == current_turn && board[2] == current_turn) ||
        (board[3] == current_turn && board[4] == current_turn && board[5] == current_turn) ||
        (board[6] == current_turn && board[7] == current_turn && board[8] == current_turn) ||
        // Vertical Checks
        (board[0] == current_turn && board[3] == current_turn && board[6] == current_turn) ||
        (board[1] == current_turn && board[4] == current_turn && board[7] == current_turn) ||
        (board[2] == current_turn && board[5] == current_turn && board[8] == current_turn) ||
        // Diagonal Checks
        (board[0] == current_turn && board[4] == current_turn && board[8] == current_turn) ||
        (board[2] == current_turn && board[4] == current_turn && board[6] == current_turn))
    {
        state = 1;
        winner = current_turn;
    }
    else
    {
        bool draw = true;
        for (int i = 0; i < 9; ++i)
        {
            if (board[i] == ' ')
            {
                draw = false;
                break;
            }
        };
        if (draw)
        {
            state = 0;
        }
        else
        {
            winner = ' ';
            state = -1;
        }
    }
};

int AI::minmax(TicTacToe board, char max_symbol)
{
    int best_score = -100;
    int best_move = -1; // -1 refers to none

    for (auto move : board.get_possible_moves())
    {
        board.play_move(move);
        int score = AI::min(board, max_symbol, 0);
        if (score > best_score)
        {
            best_score = score;
            best_move = move;
        }
        board.undo_move();
    }

    return best_move;
}

int AI::max(TicTacToe board, char max_symbol, int depth)
{
    if (board.state == 1)
    {
        if (board.winner == max_symbol)
        {
            return 10 - depth;
        }
        else
        {
            return -10 + depth;
        }
    }
    else if (board.state == 0)
    {
        return 0;
    }

    int best_score = -100;

    for (auto move : board.get_possible_moves())
    {
        board.play_move(move);
        int score = AI::min(board, max_symbol, depth + 1);
        if (score > best_score)
        {
            best_score = score;
        }
        board.undo_move();
    }
    return best_score;
}

int AI::min(TicTacToe board, char max_symbol, int depth)
{
    if (board.state == 1)
    {
        if (board.winner == max_symbol)
        {
            return 10 - depth;
        }
        else
        {
            return -10 + depth;
        }
    }
    else if (board.state == 0)
    {
        return 0;
    }

    int best_score = 100;

    for (auto move : board.get_possible_moves())
    {
        board.play_move(move);
        int score = AI::max(board, max_symbol, depth + 1);
        if (score < best_score)
        {
            best_score = score;
        }
        board.undo_move();
    }
    return best_score;
}

Answer 1

提高我的Tic Tac脚趾课。提高我的人工智能。改善UX。

也许是重新设计课程：

你不确定你有最棒的课程。

TikTakToa类似乎是一个将游戏状态、人工智能程序的未来状态和游戏规则结合在一起的类。

AI类似乎只是嵌入了AI算法，但它并没有在其中存储状态(这似乎很奇怪)。

我可以建议对这类人进行改组吗？

class Board
{
    int currentMove;
    public:
        // Players can interagate the board history
        // to work out the current state of the game
        // or keep track of that locally.
        int getCurrentMove() const;
        int getMove(int m)   const;

        // Only the Game (see below) can add moves as it
        // is the only object that will get a non const reference
        // to the board;
        void addMove(int m);
};

// An abstract player.
// Human or AI (could be either).
class Player
{
    public:
        virtual ~Player() {};

        // Players get a board to examine during there move
        // then they can decide return the best move to the game
        // who will apply the move after validation.
        virtual int getMove(Board const&) = 0;
};
class HumanPlayer
{
    public:
        // The human player may need to see a visualization
        // of the board (or just a list of moves) up to you.
        //
        // So the first step of the human player would be
        // to print the board then get input from the human.
        virtual int getMove(Board const&) override;
};
class AIPlayer
{
    public:
        virtual int getMove(Board const&) override;
};

// The game object takes two player
// Could be two humans or two AI or one of each.
// Then sequentially gets each player to make a move
// until it detects a winner.
class Game
{
    public:
        // Set up a game with the two players and a board.
        Game(Player& cross, Player& nott, Board& board);

        // Play a game asking each player for a move
        // until the game decides there is a winner.
        void playLoop();
};
 

int main()
{
    std::unique_ptr<Player>  p1 = getPlayer1();
    std::unique_ptr<Player>  p2 = getPlayer2();

    Board board;
    Game  game(*p1, *p2, board);
    game.play();
     
}

检讨守则

我更喜欢camelCase，你说你更喜欢Snake_Case。老实说这没什么大不了的。但最好保持一种或另一种风格，而不是每种风格的组合。

class TicTacToe;
void play_game(TicTacToe game);

为什么不是Tic_Tac_Toe？

class TicTacToe

这似乎是一个做几乎所有事情的uber类：

董事会国：

    char board[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '};
    char current_turn = 'X';

游戏状态：

    char winner = ' '; // ' ' refers to None
    int state = -1;    // -1 refers to running

艾州？

    std::list<int> move_stack;

似乎play_game()应该是TicTacToe的成员，那么它就不需要成为朋友了。

int main()
{
    TicTacToe game;
    play_game(game);

    // Don't need this. line
    return 0;
}

您按值传递了game。所以你在这里得到了游戏的副本：

void play_game(TicTacToe game)

你可能想做：

void play_game(TicTacToe& game)
          //            ^   pass the game by reference.

你总是想要人工智能？两个人会怎么样？或者让两个人工智能来对抗对方呢？如果你有一个神经网络，并且想通过相互对抗来训练人工智能，那就真的很有用了。

    AI my_ai;

如果你有两个人工智能游戏。不确定我希望董事会总是被更新或打印到UI。让人类玩家界面的那一部分。

        game.print_board();

对AI不太公平总是排在第二位？

        if (count % 2 == 1)
        {
            move = my_ai.minmax(game, game.current_turn);
        } else

人类的输入代码应该放在自己的功能中。

        {
            std::cout << "Enter your move (1-9)\n";
            std::cin >> move;
            if (!std::cin) 
            {
                std::cerr << "Input error\n";
                return;
            }
            --move;
        }

这是可行的，但并不是编写它的典型方式：

            std::cin >> move;
            if (!std::cin) 
            {
                std::cerr << "Input error\n";
                return;
            }

我会这样写：

            if (std::cin >> move) {
                // Good input
            }
            else {
                std::cerr << "Input error\n";
                return;
            }

如果AI产生这个动作，你认为如果你再问一次，它会改变主意吗？

        if (game.play_move(move) == 0)
        {
            std::cout << "Box already occupied\n";
            continue;
        }

我想这张支票只适用于人类玩家。不管怎么说都是排泄物。因此，将此检查与人工输入放在处理用户输入的函数中。

如果游戏接收到无效的移动，您可能需要外部检查退出应用程序，否则AI将进入无限循环。

你有两个游戏状态。playing和game.state.保持此状态为一种状态，因此在游戏结束时您只需退出循环即可。然后，这个输出可以在循环之外完成。

        if (game.state == 1)
        {
            game.print_board();
            std::cout << game.winner << " wins the game!\n";
            playing = false;
        } else if (game.state == 0)
        {
            game.print_board();
            std::cout << "Draw!\n";
            playing = false;
        };

这并不是错的。

int TicTacToe::play_move(int index)
{
    if (index >= 0 && index < 9)
    {
        if (board[index] == ' ')
        {
            board[index] = current_turn;
            move_stack.push_back(index);
            update_state();
            swap_turn();
            return 1;
        }
    }
    return 0;
};

但我会先进行先决条件检查，然后在职能开始时退出，以表明前提条件已被打破：

int TicTacToe::play_move(int index)
{
    if (index < 0 || index >= 9) {
        return 0;
    }

    if (board[index] != ' ') {
        return 0;
    }

    // Good Move.
    board[index] = current_turn;
    move_stack.push_back(index);
    update_state();
    swap_turn();
};

这里我们要讨论的是一个效率问题。

std::list<int> TicTacToe::get_possible_moves()
{
    std::list<int> possible_moves;
    for (int i = 0; i < 9; ++i)
    {
        bool found = (std::find(move_stack.begin(), move_stack.end(), i) != move_stack.end());
        if (!found)
        {
            possible_moves.push_back(i);
        }
    }
    return possible_moves;
}

这是每一次在循环周围建立。为什么不建一次呢。然后，当你移动的时候，把值取下来。然后，作为此函数的结果，可以返回对列表的const引用。这将阻止您不断地重新构建列表。

每次移动后，您需要检查所有可能的状态吗？

您只需要检查包含最后一步的状态。

void TicTacToe::update_state()
{

好的。这很难。我不知道这是否正确。

int AI::minmax(TicTacToe board, char max_symbol)
int AI::max(TicTacToe board, char max_symbol, int depth)
int AI::min(TicTacToe board, char max_symbol, int depth)