TicTacToe Design in C++

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.

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.

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.

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.

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.

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.

See the Action

Below is the driver code to simulate a human player.

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

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

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

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 🙃