No.
The game
3D noughts and crosses, or 3D tic-tac-toe, is a variant of the classic game where you play on a $3 \times 3 \times 3$ cube. It’s easiest to represent this with three separate grids, where you can win in each grid individually but also get diagonals and straight lines through the cube. Here’s three different games, in three different columns:
The first shows a pretty clear win from $X$. The second is a more complicated game where $O$ wins, and the final is a game where the two players are cooperating in order to try make the game go on for as long as possible. If you want to try play for yourself, I’ve been procrastinating doing coursework for my A-levels and working on this website instead: https://projects.ollybritton.com/3d-noughts-and-crosses (source code here).
When you first play it, there’s a few ways you can win that are a little non-obvious. Here’s two additional ways of getting a line through a cube:
If the three grids represent the three layers of the cube extending into the $z$ dimension top-down, then the first represents a line starting in the bottom-left and extending to the upper-left at the back of the cube. The second represents a line ranging from the middle-left of the first face to the middle-right of the last face.
No fun
If you’ve played normal noughts and crosses for a while, it becomes clear that the game will always end in a draw unless either player makes a big mistake early on. For this game, the situtation is even worse, because it becomes clear that the $X$ player can easily force a win by playing in the very center square:
From this point onwards, $O$ can’t do anything to win or even draw. It’s not even like the $X$ player needs to be super smart and think several moves ahead: the $O$ player is stuck in a situation where it keeps having to block $X$’s attack, until a situation is reached where it would need to block in two places, leading to a depressing, but predetermined loss.
There are several ways you might consider trying to make the game fairer1:
- Prevent the first player from taking the center square. If you adopt this rule, the second player can easily force a win.
- Ban the center square altogether. This has no effect, the game can still easily be won by the first player.
- Pick who goes first randomly. This means its fair, but is no better than flipping a coin because the first player can always win.
The only real solution is to introduce a third player, which means that the perfect game can be played out until a draw kind of like in ordinary noughts and crosses.
The question
So it seems that it’s a lot easier for a player to win in this variant of noughts and crosses. In fact, if you play the game a few times, even deliberately badly, you will notice that there never seems to be a draw. A question you might ask is:
Can you ever draw in 3D noughts and crosses?
That is, is there some arrangement of $X$s and $O$s on the board such that the board is full and no player wins? The answer turns out to be no.
How can you prove it?
Proving that there is no way to draw in 3D noughts and crosses is actually a fun programming problem. If you want to give a go yourself, you might break it down into three stages:
- Representing the board
- Checking for winners
- Considering all possible games
For a hint for how to check for winners, consider how you’d check for winners in a normal tic-tac-toe game, and then about how you could reuse the same code for checking for wins in three dimensions with a slight change.
Representing the board
Let’s assume that the board information is laid out as a 2-dimensional array:
[
[None, None, None, None, None, None, None, None, None],
[None, None, None, None, None, None, None, None, None],
[None, None, None, None, None, None, None, None, None],
]
Each sub-array corresponds to the marks in each sub-grid indexed from $0$ and starting at the top left. For example, position $[1][3]$ would refer to the fourth square in the second grid. Here’s another example:
["X", "X", "O", "X", "O", "O", None, "X", "O"]
corresponds to…
Three of these together are enough to make up the state of the whole board. Alternatively, we could use a 3-dimensional array corresponding to the 3 dimensions of the cube, but this is unnecessary and makes the code for finding winners more complicated than it actually has to be.
Checking for winners
One way to check for winners in ordinary tic-tac-toe is to use a list like this one:
winning_positions = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[2, 4, 6],
]
Here, each list represents three positions that will lead to a win if the same player has all three of them. For example, the top list [0, 1, 2] corresponds a player getting three in a row at the top of the grid. Checking for a winner is then as simple as iterating through this list, and checking if the same player has a mark at all three locations.
We can use this same idea to check for winners in 3D noughts and crosses. As each of the three sub-grids can also be won in the same way as normal tic-tac-toe game, a good place to start would be checking if anybody has won in of the three grids. In Python, it might look like this:
for gridIndex, grid in enumerate(grids):
for position in winning_positions:
i, j, k = position
if grid[i] == grid[j] and grid[j] == grid[k] and grid[i] != None:
return True
Another way someone might be able to win is by getting a line straight through the cube, like the middle square on all three grids:
Checking for a win like this is simple too, just iterate iterate through the numbers $0$ to $8$ and check if a player has a mark in that location across all three grids. Again, the code might look like this:
for i in range(9):
if grids[0][i] == grids[1][i] and grids[1][i] == grids[2][i] and grids[0][i] != None:
return True
The most complicated bit is detecting wins that span across the three layers of the cube and aren’t as simple as straight lines through the same piece. Luckily, we can use the winning_postions list again to make this process easier. Wins “through” the cube must follow the same pattern as wins on an individual layer, but you’re increasing the depth with each position that you check. So for something like [0, 4, 8] on grid, you’d now have to check that the same player has a mark in location 0 on the first grid, 4 on the second grid and 8 on the final grid. Furthermore, you’d also have to check if a player got position 8 on the first grid, 4 on the second grid and 0 on the final grid as it would be the same but the direction of the diagonal would change.
Here’s a more visual illustration for the same [0, 4, 8] pattern:
The code for this might look something like this:
for position in winning_positions:
i, j, k = position
if grids[0][i] == grids[1][j] and grids[1][j] == grids[2][k] and grids[0][i] != None:
return True
if grids[0][k] == grids[1][j] and grids[1][j] == grids[2][i] and grids[0][k] != None:
return True
And with that third check, the algorithm for checking for a winner in 3D noughts and crosses is complete. Overall, the code looks something like this:
# assumes grids is a global variable
def check_winner():
for gridIndex, grid in enumerate(grids):
for position in winning_positions:
i, j, k = position
if grid[i] == grid[j] and grid[j] == grid[k] and grid[i] != None:
return True
for position in winning_positions:
i, j, k = position
if grids[0][i] == grids[1][j] and grids[1][j] == grids[2][k] and grids[0][i] != None:
return True
if grids[0][k] == grids[1][j] and grids[1][j] == grids[2][i] and grids[0][k] != None:
return True
for i in range(9):
if grids[0][i] == grids[1][i] and grids[1][i] == grids[2][i] and grids[0][i] != None:
return True
return False
Crunching the numbers
Now we can use the code to prove that there’s no possible states where a draw is reached. To do this, we could check all possible arrangements of $X$s and $O$s on the board which corresponds to $2^{27} = 134,217,728$ states assuming we naïvely pick $X$s or $O$s at random for each spot on the board. We can cut this exponent roughly in half by considering the fact that moves come in pairs, and that $O$s moves will have to be in the 13 spaces left over after $X$ makes 14 moves – this leaves us with $2^{14}$ states, which is $16,384$.
However, this measures possible states, not possible games. Included in this estimate are games that have $X$ or $O$ winning in multiple places at the same time, which couldn’t come up during normal play. We can deal with this problem and even further cut down on the states we need to analyse by considering the fact that all three of the grids must all be draws themselves, otherwise there would be a winner overall anyway.
Tic-tac-toe draws come in three flavours:
An “arrow”:
A “scorpion”:
And finally, an “island”:
All drawing noughts-and-crosses states are rotations of these three – there’s no other way to draw. That leaves a total of $4\times3 = 12$ different states we can pick from to assign to each individual sub-grid. Since we’re picking three things from a collection of twelve, and it’s with replacement, the number of total possibilities to consider is
$$ 12P3 = \frac{12!}{(12-3)!} = 1,320 $$
Here’s some quick code to get a list of all the possible permutations using itertools and numpy in Python:
import numpy as np
import itertools
drawing_positions = [
np.array([["X", "O", "O"], ["O", "X", "X"], ["X", "X", "O"]]), # Island
np.array([["X", "X", "O"], ["O", "O", "X"], ["X", "O", "X"]]), # Arrow
np.array([["X", "X", "O"], ["O", "O", "X"], ["X", "X", "O"]]), # Scorpion
]
for i in range(3):
drawing_positions.append(np.rot90(drawing_positions[i]))
drawing_positions.append(np.rot90(drawing_positions[-1]))
drawing_positions.append(np.rot90(drawing_positions[-1]))
perumutations = list(itertools.permutations(drawing_positions, 3))
And finally, we can check all states like so:
for perumutation in perumutations:
grids[0] = perumutations[0][0].flatten() # flatten() is needed because we're using a 1D array for each grid,
grids[1] = perumutations[1][0].flatten() # but numpy needs a 2D array for np.rot90() to work as we want it to.
grids[2] = perumutations[2][0].flatten()
if check_winner() == False:
print("Yay!")
If you run this, “Yay!” never gets printed and so there’s no winning combination. If you want the complete code for this, it’s available here on GitHub.
Conclusion
So that’s it – you can never draw in 3D noughts and crosses! I hope you enjoyed reading. There’s probably a much shorter proof out there that doesn’t require checking all states and instead relies on what you know must be true, but I haven’t been able to think of it. On the website I’ve been working on, there’s an option to “Optimise for game length” which means the AI tries to prevent anyone from winning, including itself. If you turn the depth limit up and get it to play against itself, it can get pretty close to filling up the grid without anyone winning but of course it fails in the last few moves.
Another fun variant of noughts and crosses you might want to try is ‘quantum noughts and crosses’ (Wikipedia, Play online) where your moves can be in two places at once.
Backlinks
Metadata
date: 2022-02-10 19:31
tags:
- '@?public'
- '@?blog'
- '@?safe-to-post-online'
title: Can you ever draw in 3D noughts and crosses?
Attachments
- arrow.png
- board-example.png
- force-win.png
- grids.png
- island.png
- non-obvious.png
- same-flavour.png
- scorpion.png
- through-center.png
-
This list comes from Wikipedia, https://en.wikipedia.org/wiki/3D_tic-tac-toe#3x3x3,_two-player ↩︎