TicTacToe Design in C++

By Atakan SARIOGLU in Software Design 30/09/2020

After some time, I have a fun idea! Let’s design tic-tac-toe game (or XO-game) in C++ with an object oriented approach. For the ones who don’t know it, just play a turn here directly. It is very simple, you see. In my design, you play versus a computer. You make the first move and the computer player moves after you.

1 Implementation in C++
- 1.1 Components of TicTacToe
- 1.2 See the Action
2 Big-O Complexity
3 Playable Front-End
4 Final Words

Implementation in C++

Now we should think of adapting the idea to C++ in an easily extendable way. Other than fancy classes, we will eventually have a method to call. It should return the GameState whether the player WON the game, or LOST the game. Otherwise NONE is returned if not DRAW. Also INVALID is returned for illegal moves.

Components of TicTacToe

GameState and Coordinate

An enumeration to represent the game state and a using directive for type alias.

enum class GameState { NONE = 0, WON = 1, LOST = -1, INVALID = -2, DRAW = 2 };

1	enum class GameState { NONE = 0, WON = 1, LOST = -1, INVALID = -2, DRAW = 2 };

using Coordinate = std::pair<int, int>;

1	using Coordinate = std::pair<int, int>;

Strategy Interface for Computer Player

Here I want to enable different strategies for computer player such as a basic random move as well as a reinforced learning AI algorithm.

class Strategy {
public:
    virtual Coordinate FindMove(TicTacToe&, int) = 0;
    virtual ~Strategy() = default;
};

class Strategy {

public:

virtual Coordinate FindMove(TicTacToe&, int) = 0;

virtual ~Strategy() = default;

};

Implement your own strategy by inheritance from the interface. Though I only implemented the random one below. This is a strategy pattern that will be an aggregate object within the game class.

class RandomPlay : public Strategy {
public:
    Coordinate FindMove(TicTacToe& game, int player) {
        auto N = game.GetBoardSize();
        auto rand = std::default_random_engine{};
        while (game.GetMovesLeft()) {
            int r = rand() % N;
            int c = rand() % N;
            auto dest = game.GetCell(r, c);
            if (dest != player && dest != -player) return Coordinate{ r, c };
        }
        return Coordinate{ -1, -1 };
    }
};

class RandomPlay : public Strategy {

public:

Coordinate FindMove(TicTacToe& game, int player) {

auto N = game.GetBoardSize();

auto rand = std::default_random_engine{};

while (game.GetMovesLeft()) {

int r = rand() % N;

int c = rand() % N;

auto dest = game.GetCell(r, c);

if (dest != player && dest != -player) return Coordinate{ r, c };

}

return Coordinate{ -1, -1 };

}

};

It is a naive brute-force algorithm that tries until it finds a valid move.

TicTacToe Class

We need a TicTacToe class to manage the game logic. It knows about the board, past moves and how to handle another move.

class TicTacToe {
    Strategy& strategy;
    int N;
    std::vector<std::vector<int>> board;
    std::vector<int> rows;
    std::vector<int> cols;
    std::vector<int> diag;
    int movesLeft;
    GameState gameState;

public:
    TicTacToe(Strategy& strategy, int boardSize = 3) :
        strategy(strategy),
        N(boardSize),
        board(N, std::vector<int>(N)),
        rows(N),
        cols(N),
        diag(2),
        movesLeft(N* N),
        gameState(GameState::NONE) { }

    int GetCell(int r, int c) const {
        if (!validateMove(r, c)) return 0;
        return board[r][c];
    }

    int GetBoardSize() const {
        return N;
    }

    GameState GetGameState() const {
        return gameState;
    }

    int GetMovesLeft() const {
        return movesLeft;
    }

    GameState Play(int r, int c) {
        if (GetGameState() != GameState::NONE) return GetGameState();

        auto selfResult = playHelper(r, c, 1);
        if (selfResult == GameState::WON) return gameState = GameState::WON;
        if (selfResult == GameState::INVALID) return GameState::INVALID;

        if (GetMovesLeft()) {
            auto coord = strategy.FindMove(*this, -1);
            auto otherResult = playHelper(coord.first, coord.second, -1);
            if (otherResult == GameState::WON) return gameState = GameState::LOST;
        }

        if (GetMovesLeft()) return gameState = GameState::NONE;
        else return gameState = GameState::DRAW;
    }

private:
    GameState playHelper(int r, int c, int player) {
        if (gameState != GameState::NONE) return GameState::INVALID;
        if (!validateMove(r, c)) return GameState::INVALID;
        if (!validatePlayer(player)) return GameState::INVALID;
        if (board[r][c] != 0) return GameState::INVALID;
        if (!movesLeft) return GameState::INVALID;

        --movesLeft;
        board[r][c] = player;

        rows[r] += player;
        cols[c] += player;
        if (r == c) diag[0] += player;
        if (r + c + 1 == N) diag[1] += player;

        if (rows[r] == N * player) return GameState::WON;
        if (cols[c] == N * player) return GameState::WON;
        if (diag[0] == N * player) return GameState::WON;
        if (diag[1] == N * player) return GameState::WON;

        return GameState::NONE;
    }

    bool validateMove(int r, int c) const {
        if (r < 0 || r >= N) return false;
        if (c < 0 || c >= N) return false;
        return true;
    }

    bool validatePlayer(int player) const {
        return player * player == 1;
    }
};

class TicTacToe {

Strategy& strategy;

int N;

std::vector<std::vector<int>> board;

std::vector<int> rows;

std::vector<int> cols;

std::vector<int> diag;

int movesLeft;

GameState gameState;

public:

TicTacToe(Strategy& strategy, int boardSize = 3) :

strategy(strategy),

N(boardSize),

board(N, std::vector<int>(N)),

rows(N),

cols(N),

diag(2),

movesLeft(N* N),

gameState(GameState::NONE) { }

int GetCell(int r, int c) const {

if (!validateMove(r, c)) return 0;

return board[r][c];

}

int GetBoardSize() const {

return N;

}

GameState GetGameState() const {

return gameState;

}

int GetMovesLeft() const {

return movesLeft;

}

GameState Play(int r, int c) {

if (GetGameState() != GameState::NONE) return GetGameState();

auto selfResult = playHelper(r, c, 1);

if (selfResult == GameState::WON) return gameState = GameState::WON;

if (selfResult == GameState::INVALID) return GameState::INVALID;

if (GetMovesLeft()) {

auto coord = strategy.FindMove(*this, -1);

auto otherResult = playHelper(coord.first, coord.second, -1);

if (otherResult == GameState::WON) return gameState = GameState::LOST;

}

if (GetMovesLeft()) return gameState = GameState::NONE;

else return gameState = GameState::DRAW;

}

private:

GameState playHelper(int r, int c, int player) {

if (gameState != GameState::NONE) return GameState::INVALID;

if (!validateMove(r, c)) return GameState::INVALID;

if (!validatePlayer(player)) return GameState::INVALID;

if (board[r][c] != 0) return GameState::INVALID;

if (!movesLeft) return GameState::INVALID;

--movesLeft;

board[r][c] = player;

rows[r] += player;

cols[c] += player;

if (r == c) diag[0] += player;

if (r + c + 1 == N) diag[1] += player;

if (rows[r] == N * player) return GameState::WON;

if (cols[c] == N * player) return GameState::WON;

if (diag[0] == N * player) return GameState::WON;

if (diag[1] == N * player) return GameState::WON;

return GameState::NONE;

}

bool validateMove(int r, int c) const {

if (r < 0 || r >= N) return false;

if (c < 0 || c >= N) return false;

return true;

}

bool validatePlayer(int player) const {

return player * player == 1;

}

};

Keep an eye on Play method. First, it verifies the validity of the coordinate and the player ID. Here I have to mention that, for sake of simplicity, human player is 1 and computer is -1. Notice that I keep sum of the values on each row, column as well as both diagonals (see lines 67-70) and then check if the value on a row reached to N*player which is 3 for human player and -3 for computer on a 3×3 board. Also on line 48, I play an automated move for computer player, just after the human player’s move. To decide where to put the mark for computer, I use the provided strategy.

GamePrinter Class

I wanted to print the board to visualize it since there is no UI here.

struct GamePrinter {
    static void Print(const TicTacToe& game) {
        auto N = game.GetBoardSize();
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                std::cout << game.GetCell(r, c) << ", ";
            }
            std::cout << std::endl;
        }
    }
};

struct GamePrinter {

static void Print(const TicTacToe& game) {

auto N = game.GetBoardSize();

for (int r = 0; r < N; ++r) {

for (int c = 0; c < N; ++c) {

std::cout << game.GetCell(r, c) << ", ";

}

std::cout << std::endl;

}

};

See the Action

Below is the driver code to simulate a human player.

int main() {
    RandomPlay strategy;
    TicTacToe game(strategy);

    game.Play(0, 0);
    game.Play(0, 1);
    game.Play(0, 2);

    GamePrinter::Print(game);

    std::cout << "res: " << static_cast<int>(game.GetGameState()) << std::endl;

    return 0;
}

int main() {

RandomPlay strategy;

TicTacToe game(strategy);

game.Play(0, 0);

game.Play(0, 1);

game.Play(0, 2);

GamePrinter::Print(game);

std::cout << "res: " << static_cast<int>(game.GetGameState()) << std::endl;

return 0;

}

I see the output below; result 1 represents WON state.

1, 1, 1,
0, 0, 0,
-1, 0, -1,
res: 1

1, 1, 1,

0, 0, 0,

-1, 0, -1,

res: 1

If you play differently and the game is LOST , you would see this.

1, 1, 0,
1, -1, 1,
-1, -1, -1,
res: -1

1, 1, 0,

1, -1, 1,

-1, -1, -1,

res: -1

If you could create a DRAW , the below output is displayed.

1, -1, 1,
1, -1, 1,
-1, 1, -1,
res: 2

1, -1, 1,

-1, 1, -1,

res: 2

Big-O Complexity

My implementation is based on sum checks and for example, there is a sum values for each row. this gives us a fair O(N) time complexity. However, if we consider the complexity of the strategy, it will be added to this value. To talk about space, consider the board member variable. It gives us O(N^2) space complexity.

Playable Front-End

In my next post, I created a user interface that can be played on you smart phone. Check it here!

Final Words

This implementation is expected to work for a variety of cases. However, unit tests are important for covering edge cases. Since the game is played with random strategy, it is out of our control where game ends. When writing unit tests, it would be wise to mock the random engine and pass it from constructor of the respective strategy via dependency injection. Also the try-em-all strategy for computer player can get slow when there are few unoccupied cells left. Use it for fun 🙃

Tags: cpp, game-programming, object-oriented, oopd, tic-tac-toe