Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Introduction

In this tutorial, we’ll show how to find all the ways to win a game of tic-tac-toe.

2. Problem Statement

Even though we’re dealing with a game that we can play using an adversarial search algorithm such as minimax or Monte Carlo Tree Search, we should note that the problem we’re solving now isn’t that of game playing. Instead of winning a single game against an actual opponent, we want to find all the states of the tic-tac-toe grid that represent a victory for player \boldsymbol{X} or player \boldsymbol{O}.

Another thing we should note is that this also isn’t a problem we can classify as a traditional search for the best solution because we’re not interested in the shortest sequence of winning moves. Instead, we consider all the victories equal, no matter the number of moves, and want to discover them all.

3. The Brute-Force Solution

The simplest way is to iterate over all the states of tic-tac-toe and return only those in which a player wins.

3.1. States

To do so, we first have to define a tic-tac-toe state. Since we play it on a 3\times 3 grid, and each cell can be either blank or marked with X or O, we can define the states of the game as 3\times 3 matrices. For example:

    \[\begin{bmatrix} X &   &   \\   & X &   \\   &   & O \\ \end{bmatrix}\]

There are 3^{3 \cdot 3}=3^9=19,683 states the grid can be in, but not all of them are legal. Since players X and O alternate, the difference of the number of \bold{X}s and \bold{O}s on the grid at any point in the game can be at most 1. For instance, the following state isn’t legal because X made three moves while O made only one.

    \[\begin{bmatrix} X &   &   \\ X & X &   \\   &   & O \\ \end{bmatrix}\]

3.2. States and Matches

Each state corresponds to several matches. If the player X occupies n_X cells, and O fills n_O cells, then there are n_X!\cdot n_O! sequences of moves that lead to that state. For example, these two sequences finish in the same state:

    \[ \begin{aligned} \begin{bmatrix} X & \; & \; \\   &    &    \\   &    &    \\ \end{bmatrix} &\rightarrow \begin{bmatrix} X & O & \; \\ & & \\ & & \\ \end{bmatrix} &\rightarrow \begin{bmatrix} X & O & \; \\   & X & \\   &   & \\ \end{bmatrix} &\rightarrow \begin{bmatrix} X & O & O \\   & X & \\   &   & \\ \end{bmatrix} &\rightarrow \begin{bmatrix} \boldsymbol{X} & O & O \\   & \boldsymbol{X} & \\   &   & \boldsymbol{X} \\ \end{bmatrix} \\ \begin{bmatrix} X & \; & \; \\ & & \\ & & \\ \end{bmatrix} &\rightarrow \begin{bmatrix} X & \; & O \\ & & \\ & & \\ \end{bmatrix} &\rightarrow \begin{bmatrix} X & \; & O \\   &    & \\   &    & X\\ \end{bmatrix} &\rightarrow \begin{bmatrix} X & O & O \\ &  & \\ & &  X\\ \end{bmatrix} &\rightarrow \begin{bmatrix} \boldsymbol{X} & O & O \\ & \boldsymbol{X} & \\ & & \boldsymbol{X} \\ \end{bmatrix}  \end{aligned} \]

There are 3!\cdot 2!=12 move sequences that end the same way.

3.3. Win States

Let’s define a test to check if a legal grid state A represents a victory for player P\in\{X, O\}.

The first thing that we should check is if \boldsymbol{A} contains a row, a column, or a diagonal comprised of all \boldsymbol{P}s. However, although this test would capture all the grid states in which P wins, it would produce a significant number of false victories. For instance, the following grid state passes this test for player X:

    \[\begin{bmatrix} O & O & \\ \boldsymbol{X} & \boldsymbol{X} & \boldsymbol{X}\\ O & & \\ \end{bmatrix}\]

even though it’s not possible to encounter it in an actual game! As soon as X filled the middle row, the game stopped, and O couldn’t mark its third cell, so one O is illegal.

Therefore, if player X wins, it will have one cell more than player O. But, if player O wins, it will always have the same number of cells as player X. That’s because X has the first move, and the game stops after the winner makes its last move.

For the same reason, \boldsymbol{X} can win only in the odd turn, while \boldsymbol{O} can win only in the even turn. If the number of filled cells is even, and both \boldsymbol{X} and \boldsymbol{O} qualify for a win, then we know that the state is illegal. Since X wins in the odd turn, the game would have ended before O would get to connect its three cells.

So, this is the pseudocode to check if player P \in \{X, O\} has won:

Rendered by

3.4. Pseudocode

Finally, we formulate our brute-force approach as follows:

Rendered by

3.5. Complexity

Both the space and time complexities of our algorithm depend on the size of the search space. We calculated that there were 19,683 states in total. Modern computers can easily store all of them in the main memory. So it’s reasonable to expect that it won’t take much time to run this algorithm, depending on the actual hardware used and other jobs our CPUs are executing concurrently.

That’s why a brute-force approach is justified in this case. Since the problem is tractable, a simple algorithm without complex logic can handle it.

4. Generalizations of Tic-Tac-Toe

However, generalizations of tic-tac-toe require a more sophisticated approach.

In them,n,k-game, we play tic-tac-toe on a m\times n grid. The winner is the player that first connects k cells horizontally, vertically, or diagonally. An m\times n grid can have 3^{mn} states. For example, the 7\times 7 board has 2.393\times 10^{23} states. So, even for small values of m and n, there are too many states for a brute-force solution to be efficient.

Similar holds for the three-dimensional tic-tac-toe usually played in a 4 \times 4 \times 4 cube of cells.

To find all the win states in these forms of tic-tac-toe, we’d have to use a more efficient constraint-satisfaction technique. We’d define constraints on the grid cells that win states fulfill and then construct the state cell by cell. If we realize that a state is illegal or infer that no player can win, then we backtrack and change the assignment of one of the cells we previously left blank or filled with X or O. Once we find a win state, we record it, backtrack, and continue the search.

5. Conclusion

In this article, we showed how to find all the tic-tac-toe grids that represent a win. Even though a simple brute-force algorithm proved sufficient to handle the standard 3\times 3 game, the generalizations of tic-tac-toe to three dimensions and larger grids require a more efficient approach.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!