Greetings, fellow human! 👋

ℹ️ This post is part of a series, where I pen down my journey as I plan and build a tic-tac-toe game from ideation to release

Every project needs a space where you can jot down your thoughts, gather resources, and plan ahead. Some demand a robust project management system with all the latest features, some need nothing more than a todo list, and some do just fine with traditional pencil and paper.

The project hub of my choice is Notion, a great app/website that does it all—or at least, all that I need. I start off the planning process with a new project page, inside of which I have just two sections, nothing more. An inline database called Bucket will store everything I prepare to assist the process, and a Links section will be where I place articles and resources from the internet that I find useful.

With the project hub all set up, it is time to proceed. ⏩

Defining the app's functionality

With every programming venture, it is important to first identify and break down the app's functionality. What are the minimum necessary objectives that our app should be able to perform?

This helps plan out features extensively beforehand and assists in researching solutions to problems that we may encounter. It also provides a checklist of goals to mark off during development.

To implement this practically, we start off with broad objectives and then work our way backwards until we end up with highly specific, actionable goals.

Essentially, the app's objective is this:

1. Play game(s) of tic-tac-toe

But this doesn't help much when you're building it from scratch, and so we need to think more specifically. I would preferably want my app to have three stages:

1. Define game settings
2. Play a game or multiple games of tic-tac-toe
3. Keep track of scores

Now that the app has been broken down into three separate stages, we can identify the major objectives in each stage. Let's start by breaking down the first stage

Define game settings

What settings must the game require?

1. Game mode (PvP or PvC?)
2. Grid size (3 - 5)
3. Player name(s)

These are the three things I deem essential to have before the game can start. I am limiting the grid size to a maximum of 5x5 to avoid the cells from becoming too small on certain screens.

Play a game or multiple games of tic-tac-toe

What are the specific steps in each game?

1. Display empty grid
2. Allow the player to make a move
3. Switch players
4. For PvC: Deduce the optimal move for the computer
5. Identify a game result (win/draw)
6. If there is a result, display it
7. If there is a result, repeat from 1.
8. Otherwise, repeat from 2.

The game has now been outlined and each step is highly specific, which allows us to move towards the next and final objective.

Keep track of score

1. Initialize scores for both players to 0
2. If there is a win, increment the score of the winning player
3. If the settings are changed, repeat from 1.

Although this objective was not as in-depth or complex as the previous one, it is still a basic feature of our app and therefore equally important.

Final list of objectives

Let's see the complete list altogether

1. Define game settings
   1. Game mode (PvP or PvC?)
   2. Grid size (3 - 5)
   3. Player name(s)
2. Play a game or multiple games of tic-tac-toe
   1. Display empty grid
   2. Allow the player to make a move
   3. Switch players
   4. For PvC: Deduce the optimal move for the computer
   5. Identify a game result (win/draw)
   6. If there is a result, display it
   7. If there is a result, repeat from 1.
   8. Otherwise, repeat from 2.
3. Keep track of score
   1. Initialize scores for both players to 0
   2. If there is a win, increment the score of the winning player
   3. If the settings are changed, repeat from 1.

We now have a set of specific, actionable steps that can be implemented separately. Great!

Tackling logic problems beforehand

With the game broken down into individual pieces, let's talk about two important problems that I foresee to be especially complicated and my approach to solving them.

Deducing the game's result

Key question: How do you identify when a player has won the game?

There have been many approaches to this, and most people initially think of using loops coupled with conditional statements to check for matches. This results in code which looks something like this:

for row <- 1 to 3
    for col <- 1 to 2
        if grid[row][col] != grid[row][col + 1] then
            next row
    next col
    return true
next row
return false

Here, we are essentially looping through each row and then checking whether adjacent cells in each row contain the same value. If not, we skip to the next row. Once all cells in a particular row have been checked and there were no skips, this implies that there is a match in said row.

I do not like this approach as it involves a lot of looping and nesting, and even after the previous code, we still have to check for column matches and diagonal matches, leading to more lines, more bugs, and ultimately more headaches.

Instead, I prefer the use of counters, which will store the number of X's and O's in each row, column, and diagonal, and are updated after every move. This is illustrated below:

Each pair of values in this diagram is keeping a count of X's and O's in it's row/column/diagonal. As an example, there is 1 X and 1 O in the main diagonal, therefore the main diagonal counter stores the values (1, 1).

After every valid move, these counters need to be updated.

• The row and column counters will always be updated based on the row and column of the chosen grid cell.
• The main diagonal counter will be updated when the chosen grid cell lies on the main diagonal. This can be tested using the condition, row === column.
• The anti diagonal counter is similarly updated by testing the condition, row + column === size - 1, assuming that row and column are zero-indexed, and size stores the number of cells in any row/column.

In a tic-tac-toe grid of arbitrary size, a win is possible after exactly (size × 2) - 1 moves. This is because on the very next move, the starting player will have made enough moves to make a match. Let's denote this value by minMoves.

Following every move after minMoves, we will check the current state of all counters and check if any one contains a value equal to size. This would mean that a match has been made!

After size × size moves, we will do this check for the last time, and if there is still no win, a draw is declared and the game ends.

This approach has a time complexity of O(n), because the only looping required will be to go through the row/column counters to detect a match.

Compare this to the previous approach, which had a time complexity of O(n²) since it would loop through each row and each column to detect a match. We have ourselves a winner! 🥳

Deducing the optimal move for the computer

Key question: How can you identify which move promises the most favourable outcome on a given grid state?

This will be implemented through an application of the Minimax algorithm, which attempts to traverse all possible moves for the computer as well as the human player repeatedly until it reaches a terminal state, i.e. a win, draw, or loss. It then backtracks all moves and chooses the one which results in the most favourable outcome with the least number of moves.

Let's assume that it is X's turn and the current grid state is as follows:

X can make either of the following 3 moves:

We can see that move #3 is resulting in a win for X, and therefore we assign a value of +1 to that move. For the other two moves however, we have not reached a terminal state, therefore we shall keep traversing possible moves, but this time for O.

We can see that moves #1.1 and #2.2 are resulting in a loss for X, therefore we assign a value of -1 to those moves.

Since it is obvious that the the other two moves (#1.2 and #2.1) are a win for X, we assign a value of +1 to those moves. There is no need to illustrate further moves.

We now have the following tree of possible moves with their respective score values:

X will now make the most optimal move from the options it has using each possible move's score value. We still however haven't assigned a score value to moves #1 and #2. This can be tackled by assessing the very next set of moves and choosing the score value of the optimal move (here -1).

This brings up an important idea, that an optimal move for X is one with a higher score value, while the optimal move for O is one with a lower score value. X is therefore the maximizing player and O is the minimizing player. Hence the name, minimax.

The possible moves for X on the next turn, along with their respective score values are now as follows:

X thus chooses it's optimal move, and since it is a maximizing player, it chooses the move with the highest score, leading to a win for X.

There are further edge cases to this algorithm such as resolving ties using the number of moves until we reach a terminal state, but what we want right now is a general understanding and a good grasp of how the algorithm works. Implementation details can come later.

💭 Please comment on the job I did at explaining these algorithms. Are they understandable?

We now have a set of objectives for the game, as well as the knowledge essential to building tic-tac-toe in theory. What comes next?

⚡ Stay tuned for the next post in this series, where we will use these objectives to wireframe and design the look of our game.

❤ Remember to like this post and leave your thoughts in the comments!

Cover photo by Matthew Davis on Unsplash
Learn more about the Minimax algorithm