3D Noughts & Crosses

Information

Noughts and Crosses, or Tic-Tac-Toe, is the famous game about getting three \(X\)s or \(O\)s in a row. This website demonstrates a variant where you play in 3D, trying to get a line through a cube where each grid represents a layer.

By default, the AI is a bit stupid. That's because it becomes possible for the first player to force a win if they take the center square. The AI will realise this if you put its depth limit to roughly 8, so it becomes quite difficult to win after that point, unless you go first.

The algorithm used for the AI is minimax with alpha-beta pruning. This algorithm recursively considers all possible moves it could make and all possible responses to its moves so that it can pick one that it expects to maximise its chances of winning. Without alpha-beta pruning, it becomes computationally intractable much faster than it would otherwise. Since there's 27 possible moves at the start, thinking ten moves ahead without any special tricks requires considering \(27 \times 26 \times 25 \ldots \times 18 \times 17\) or \(520,431,047,136,000\) possibilities.

If each possible game took \(1\text{ns}\) to consider, this technique means the algorithm would finish running in 6 days. Alpha-beta pruning means you can vastly cut down on the amount of options you have to consider by "pruning" states that you know won't lead to anything as good as what you've found so far. The number of states pruned is displayed in the information section.

A transposition table is also used to speed up the program. This is effectively a hashmap that stores the results of previous searches, trading off memory usage for increased speed.

Controls

To begin playing, just click on any of the squares on the right-hand side, or scroll down if you're on mobile. By default, the AI will automatically respond to your moves. To turn this off, toggle the "Automatically respond to player moves" checkbox. You can also force the AI to make the next move for the current player by clicking the "Play next move" button. "Analyse" will have the AI look for all possible moves, but not make any and instead report the information finds in the "Information" section.

The slider at the top controls how many plys the AI will look ahead. One "ply" is one move by any player, a term used to avoid the ambiguity that comes with just saying "moves", which could mean either one action by one of the players, or a complete turn. The default is 6 and is reasonably easy to win against. Lowering the slider will make the AI worse but faster at making moves, and increasing the slider will make the AI better but much, much slower. Each successive notch on the slider corresponds to roughly a \(10 \times\) increase in waiting time.

You can see a heatmap of what the AI thinks are good moves and bad moves by toggling the "Show a heatmap of predicted wins/losses" checkbox. This won't have any affect until you're a few moves into the game, as the AI can't see far ahead enough into the future to decide whether a mood is good or bad. Once it does, it will color each box depending on if there's a big chance for \(X\) or a big chance for \(O\).

small \(X\)

big \(X\)

small \(O\)

big \(O\)

Finally, there is also the "Optimise for game length" option. This makes the AI try to avoid moves that will bring the game to an end, to see how long it's possible to go without anybody winning, including itself. If you click "Play next move" over and over, it will play against itself and you can see which player ends up making the move that wins the game. It turns out that drawing is actually impossible, see this blog post for why.

Other Variants

These are some other variants of noughts and crosses. This list comes from Wikipedia, "Tic-tac-toe variants":

Misere tic-tac-toe is where you try to avoid winning, force your opponent to get three in a row before you do. You can always win or draw if you go first by playing in the middle square and then mirroring your opponent's moves.
Quantum tic-tac-toe is a variant where moves are "quantum superpositions" of normal tic-tac-toe moves. Moves can be in two places at once until a cycle is formed, where the system is then "observed" and the game is forced into one definite state. It was invented as a way to explore the intuition behind quantum mechanics without any mathematics.
Numerical tic-tac-toe/number scrabble is a game mathematically equivalent to standard noughts and crosses where two players take turns naming numbers from 1 to 9, where you can't repeat numbers that have already been said. The first player who says any three numbers that sum to 15 wins. Because you can arrange the numbers on a 3 by 3 magic square, the game is isomorphic to tic-tac-toe.
Wild tic-tac-toe lets either player decide whether to use a \(X\) or a \(O\) on their turn. The first player to get any three in a row wins.
SOS is a similar game played on any sized \(N \times N\) grid. Players can use either an "S" or an "O" on their turn and the aim is to get as many sequences of "SOS" horizontally, vertically or diagonally as they can before the grid is full.
Treblecross looks like the least interesting variant you could imagine. It's like noughts and crosses, but you play in a \(1\times N\) grid and everyone is \(X\). The first one to get three in a row wins.

Thanks!

I hope you enjoyed the game. If you want to see the source code, it's available here on GitHub. If you want to see some of my other projects, check out my website. There's the old version of this project located here, and a demonstration of what it could actually look like in 3D here.