2
\$\begingroup\$

This was my previous post on Tic Tac Toe in C++. I received very good feedback and tried to implement all of the improvements. I could not implement some due to the AI needed functions or complexity.

I wanted to know where I could -

  • Optimize the performance.
  • Improve my Tic Tac Toe class.
  • Improve my AI.
  • Improve the UX.
  • Follow C++ conventions (I still prefer snake_case)

Here is my code:

#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;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Generally you should avoid using friend. Make the necessary objects public or create getters / setters. \$\endgroup\$
    – jdt
    Sep 28, 2021 at 20:31
  • \$\begingroup\$ Not sure if I agree with Johan exactly. But he is not entirely wrong either. The friend declaration has its uses, but I don't think the way you are using helps you or is good usage in this case. BUT getters/setters are also a bad pattern in C++ were you would normally use actions() (which is a better pattern, than z.set(doSomething(z.get())) ). But get/set does have its place just not here. \$\endgroup\$ Sep 30, 2021 at 3:17
  • \$\begingroup\$ @MartinYork That’s why I added the "Generally" disclaimer =) The way it was applied here just seemed lazy. \$\endgroup\$
    – jdt
    Sep 30, 2021 at 13:52

2 Answers 2

2
\$\begingroup\$

Improve my Tic Tac Toe class. Improve my AI. Improve the UX.

Maybe a redesign of the classes:

Not sure you have the greatest class break down.

The TikTakToa class seems to be a class that combines the state of the game the future state for the AI program and the game rules all in one.

The AI class seems to just embed the AI algorithm but it does not store state in there (which seems odd).

May I suggest a restructuring of the classe.

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();
     
}

Review of Code

I prefer camelCase and you say you prefer Snake_Case. Do be honest it does not matter that much. But it would be preferable to maintain one style or the other rather than have a combination of each.

class TicTacToe;
void play_game(TicTacToe game);

Why Not Tic_Tac_Toe?


class TicTacToe

This seems to be an uber class doing nearly everything:

Board State:

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

Game State:

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

AI State?

    std::list<int> move_stack;

Seems like play_game() should be a member of TicTacToe then it would not need to be a friend.

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

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

You passed game by value. So you are getting a copy of the game here:

void play_game(TicTacToe game)

You probably want to do:

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

You always want an AI? What happens with two humans? Or what about pitting two AI against each other? That could be really useful if you have a nerual network and want to train AI by playing them against each other.

    AI my_ai;

If you have two AI playing. Not sure I want the board to always be updated or printed to the UI. Make that part of the human players interface.

        game.print_board();

Not very fair to the AI to always go second?

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

The human input code should be put into its own function.

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

This works but not the typical way to write it:

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

I would write like this:

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

If the AI generates this move do you think it will change its mind if you ask again?

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

I think this check is for the human player only. Well the ouput anyway. So put this check with the human input in the function handling user input.

You may need an external check that exits the application if the game recieves an invalid move as otherwise the AI is going to go into an infinite loop.


You have two game states. playing and game.state. Keep this as one state so you simply exit the loop when the game is over. Then this output can be done outside the loop.

        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;
        };

This is not wrong.

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;
};

But I would do the precondition checks first and exit at the beginning of the function to show the preconditions had been broken:

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();
};

Here we are looking at an effeciency issue.

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;
}

This is being built every time around the loop. Why not build it once. Then take values off when you make a move. Then you can return a const reference to the list as the result of this function. This will prevent you from constantly rebuilding the list.


Do you need to check all possible states after each move?

You only need to check states that include the last move.

void TicTacToe::update_state()
{

OK. This is hard. I have no idea to tell if this is correct.

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)
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the review! Just to mention, I come from Python. In python its a convention to use PascalCase for classes and snake_case for variables. \$\endgroup\$ Sep 30, 2021 at 7:09
  • \$\begingroup\$ @Random_Pythoneer59 Did not know they were so loosey goosey over in Python :-) \$\endgroup\$ Sep 30, 2021 at 18:04
1
\$\begingroup\$

These are my thoughts to follow up on Martin York’s excellent review.

  1. Create enums for GameState and Symbols:
enum GameState : int
{
    Running,
    Draw,
    Win
};

enum Symbol : char
{
    Tic = 'X',
    Tac = 'O',
    Space = ' '
};
  1. Simplify the board class. You do not need to keep track of previous moves and the current player etc.
class TicTacToe
{
public:
    std::array<Symbol, 9> board;

    TicTacToe() {
        board.fill(Symbol::Space);
    }

    void 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---------\n";
        }
        std::cout << "\n\n";
    }

    GameState evalState(const Symbol symbol) {
        if (match(symbol, 0, 1, 2) || match(symbol, 3, 4, 5) || match(symbol, 6, 7, 8) || // Horizontal checks
            match(symbol, 0, 3, 6) || match(symbol, 1, 4, 7) || match(symbol, 2, 5, 8) || // Vertical Checks
            match(symbol, 0, 4, 8) || match(symbol, 2, 4, 6)) // Diagonal Checks
            return GameState::Win;
        if (std::count(board.begin(), board.end(), Symbol::Space) == 0)
            return GameState::Draw;
        return GameState::Running;
    }

private:
    bool match(const Symbol symbol, int i1, int i2, int i3) {
        return board[i1] == symbol && board[i2] == symbol && board[i3] == symbol;
    }
};
  1. The possible_moves list is unnecessarily cumbersome. You can simply enumerate over the cells and use the empty ones:
for (int i = 0; i < 9; i++) {
    if (game.board[i] == Symbol::Space) {
        // set move 
        game.board[i] = symbol;

        int score = minimax(game, depth + 1, !isMax, symbol);
        best = std::max(best, score);

        // undo move
        game.board[i] = Symbol::Space;
    }
}
  1. Playing against an unbeatable AI isn't much fun. You can consider adding maxdepth to the minimax to dumb it down. It's already unbeatable at maxDepth = 5 as far as I can tell. Selecting a random move from the best moves also makes the AI a bit more interesting.

Putting it all together:

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <ctime>

enum GameState : int
{
    Running,
    Draw,
    Win
};

enum Symbol : char
{
    Tic = 'X',
    Tac = 'O',
    Space = ' '
};

class TicTacToe
{
public:
    std::array<Symbol, 9> board;

    TicTacToe() {
        board.fill(Symbol::Space);
    }

    void 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---------\n";
        }
        std::cout << "\n\n";
    }

    static Symbol swap(const Symbol symbol) {
        return symbol == Symbol::Tic ? Symbol::Tac : Symbol::Tic;
    }

    GameState evalState(const Symbol symbol) {
        if (match(symbol, 0, 1, 2) || match(symbol, 3, 4, 5) || match(symbol, 6, 7, 8) || // Horizontal checks
            match(symbol, 0, 3, 6) || match(symbol, 1, 4, 7) || match(symbol, 2, 5, 8) || // Vertical Checks
            match(symbol, 0, 4, 8) || match(symbol, 2, 4, 6)) // Diagonal Checks
            return GameState::Win;
        if (std::count(board.begin(), board.end(), Symbol::Space) == 0)
            return GameState::Draw;
        return GameState::Running;
    }

private:
    bool match(const Symbol symbol, int i1, int i2, int i3) {
        return board[i1] == symbol && board[i2] == symbol && board[i3] == symbol;
    }
};

class Player
{
public:
    std::string name;
    virtual int getMove(TicTacToe&, const Symbol) = 0;
};

class PlayerHuman : public Player
{
public:
    virtual int getMove(TicTacToe& game, const Symbol symbol) override {
        int move = -1;
        while (move == -1) {
            std::cout << "Enter your move for " << symbol << " (1-9)\n";
            std::cin >> move;
            if (!std::cin.good()) {
                std::cin.clear();
                std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
            }
            --move;
            if (move < 0 || move > 8 || game.board[move] != Symbol::Space) {
                std::cerr << "Invalid input\n\n";
                move = -1;
            }
        }
        return move;
    };
};

class PlayerAI : public Player
{
public:
    int maxDepth = 10;
    virtual int getMove(TicTacToe& game, const Symbol symbol) override {
        std::cout << "AI thinking for " << symbol << "\n";
        // select random move if board is empty
        if (std::count(game.board.begin(), game.board.end(), Symbol::Space) == 9)
            return std::rand() % 9;
        // calculate best move with minimax
        int bestScore = -1000;
        std::vector<int> moves;
        for (int i = 0; i < 9; i++) {
            if (game.board[i] == Symbol::Space) {
                game.board[i] = symbol;
                int score = minimax(game, 0, false, symbol);
                if (score > bestScore) {
                    bestScore = score;
                    moves.clear();
                }
                if (score == bestScore)
                    moves.push_back(i);
                game.board[i] = Symbol::Space;
            }
        }
        return moves[std::rand() % moves.size()];
    }

protected:
    int minimax(TicTacToe& game, int depth, bool isMax, const Symbol symbol) {
        Symbol opponent = TicTacToe::swap(symbol);
        GameState state = game.evalState(symbol);
        if (state == GameState::Win)
            return 10 - depth;
        if (game.evalState(opponent) == GameState::Win)
            return -10 + depth;
        if (state == GameState::Draw || depth >= maxDepth)
            return 0;
        int best = isMax ? -1000 : 1000;
        for (int i = 0; i < 9; i++) {
            if (game.board[i] == Symbol::Space) {
                game.board[i] = isMax ? symbol : opponent;
                int score = minimax(game, depth + 1, !isMax, symbol);
                best = isMax ? std::max(best, score) : std::min(best, score);
                game.board[i] = Symbol::Space;
            }
        }
        return best;
    }
};

class Game
{
private:
    TicTacToe game;

public:
    void Play(Player& player1, Player& player2) {
        int index = std::rand() % 2;
        Symbol symbol = Symbol::Tic;

        GameState state = GameState::Running;
        while (state == GameState::Running) {
            Player& player = index ? player1 : player2;

            game.print_board();
            int move = player.getMove(game, symbol);

            std::cout << player.name << " selected " << move + 1 << "\n\n";
            game.board[move] = symbol;

            state = game.evalState(symbol);
            if (state != GameState::Running) {
                game.print_board();
                if (state == GameState::Win)
                    std::cout << player.name << " Won!";
                else
                    std::cout << "It's a Draw.";
            }
            else
            {
                index = !index;
                symbol = TicTacToe::swap(symbol);
            }
        }
    }
};

int main() {
    std::srand(static_cast<unsigned int>(time(0)));

    PlayerHuman player1;
    player1.name = "human";

    PlayerAI player2;
    player2.name = "AI";

    Game game;
    game.Play(player1, player2);
}
\$\endgroup\$
2
  • \$\begingroup\$ The class Symbol very Java like. You could use an enum and achieve the same affect. \$\endgroup\$ Oct 2, 2021 at 17:13
  • \$\begingroup\$ @MartinYork, I agree and have updated my answer. \$\endgroup\$
    – jdt
    Oct 2, 2021 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.