4x4x4 Tic-Tac-Toe is played on a 4x4x4 cube, containing 64 cells. The first player to get 4 of their own symbols in a row (in any orthogonal or diagonal direction, including the cube’s space diagonals) wins.

As with any tic-tac-toe-like game, a strategy-stealing argument proves that the second player (“O”) can never win 4x4x4 Tic-Tac-Toe, assuming perfect play by the first player (“X”). However, strategy-stealing cannot rule out that the game might be a draw. 3x3 tic-tac-toe draws with perfect play, as does 5x5 tic-tac-toe. See “How to Win at Tic-Tac-Toe” (Norman Do, Australian Mathematical Society Gazette 32:3, July 2005).

In 1976–1977, Oren Patashnik produced a computer-aided proof that 4x4x4 Tic-Tac-Toe is a win for X. He wrote it up in prose as “Qubic: 4x4x4 Tic-Tac-Toe” (Mathematics Magazine 53:4, September 1980); but even more usefully, Patashnik’s complete first-player strategy is available as a text file!

To represent a tic-tac-toe strategy unambiguously as text, suitable for “teaching” to a computer player, we write down a mapping from every reachable position to X’s best move in that position. For example, suppose we wanted to write down X’s winning strategy for a game of tic-tac-toe where the goal was to get three in a row, but played on a 4x4 board. If the position is:

....
.x..
.o..
....

then X’s best move is:

....
.xx.
.o..
....

because now he’s got two ways to win on his next move, and O can’t block both of them. To write down that position and its winning move as a nice linear string of text, we can just concatenate all the rows together, and mark the winning move with a capital X, like this:

.....xX..o......

In fact, we’ll have a lot of rows like that, because X doesn’t really care where O moves unless it actively interferes with X’s plan. So:

o....xX.........
.o...xX.........
..o..xX.........
...o.xX.........
....ox...X......
.....xo..X......
.....x.o.X......
.....xX.o.......
~~~

We can compress these runs of similar lines by marking O’s various (mutually exclusive) moves with O, like this:

OOOO.xX.OOOOOOOO
....OxOO.X......

That is, we have two cases for X’s second move: If O’s first move goes in one of the cells marked 1 below, then X should go at A; if O goes in one of the cells marked 2, then X should go at B.

1111  ....
.xA.  2x22
1111  .B..
1111  ....

In fact, situation B is just a reflection around the diagonal of situation A. Our strategy for X can handle any position as long as our dictionary contains any rotation or reflection of that position. So all we really need in our dictionary is the single string OO...xX.OOO.OOOO, representing these nine positions — which are all that exist, up to rotation and reflection:

11..
.xA.
111.
1111

For X’s third move, we have many more situations to consider; but again many of them are rotations or reflections of each other. For example, if we have the leftmost position below, then we don’t have to explicitly record the middle position.

.... .... ...O
.xo. .xxX ..x.
.xo. .oo. .xo.
.X.. .... X...

We needn’t record the rightmost position at all, because it isn’t reachable via our strategy: X will never play his first two moves diagonally like that. So even extended to include X’s third (and winning) move, our whole strategy can be expressed in this 12-line dictionary:

.....X..........
OO...xX.OOO.OOOO
oOOOOxxXOOOOOOOO
.oOOOxxXOOOOOOOO
..OOOxxXoOOOOOOO
..OOOxxX.oOOOOOO
..OOOxxX..oOOOOO
..OOOxxX...OoOOO
..OOOxxX...O.oOO
..OOOxxX...O..oO
..OOOxxX...O...o
OO..XxxoOOO.OOOO

We could even omit the last ten lines, if our computer player is smart enough to brute-force the final move. That is, we don’t have to roll the dictionary all the way out to the end of the game; we can cut it short in positions where X’s move is “obvious” — either because X wins, or (in more involved games) because X is forced to block a threat from O. Patashnik’s original Qubic program even considers a position “obvious” if it contains what he calls a “forced sequence”: any move by X that requires O to block, followed by any other move by X that requires O to block, and so on, ending in a double-threat that O cannot block. Finding the correct “forced sequence” for a given position requires a tree search, but because all of O’s moves are forced it’s a relatively quick tree search.

Patashnik’s program used this kind of smarts, and canonicalization (but not compression), to get its dictionary down to just 2929 lines.

Patashnik’s original 2929-line dictionary (as edited by Ken Thompson!) is here. In the compressed notation of this blog post, it takes only 951 lines; get that version here.

Programming challenge problems

Several utilities for manipulating these dictionaries would make excellent programming challenges — a bit much for an interview question IMHO, but good for an Advent of Code type of thing.

Compress a dictionary

Given an “uncompressed” dictionary like this:

Xx..oo
o...xX
Xx.o.o
.o..xX
Xx.oo.
Xxo..o

Produce a dictionary that represents exactly the same board positions, using the compressed O notation, like this:

OO..xX
XxOOOo
Xx.oo.

You can do this suboptimally in \(O(n^2)\) time with a greedy algorithm, but it’s not clear to me how to do it optimally. It feels NP-complete.

Patashnik’s dictionary seems like a good test case. I compressed it using a quick-and-dirty greedy algorithm (code here) and found that with the lines in Patashnik’s original order it compressed to 1008 lines; in sorted order, to 995; and in reverse-sorted order, to 1006. The smallest I managed to get it (merely by reordering the lines) was 951 lines.

Compress a dictionary up to rotation and reflection

Given a dictionary, plus a subroutine that knows all the symmetries of the board: Produce a dictionary that represents exactly the same board positions, up to rotation and reflection, using the O notation.

Make an unbeatable computer player

Given a dictionary, plus a subroutine that knows all the symmetries of the board: Write the code to play the game against a human player. At each move, look up the current board position in the dictionary (up to rotation and reflection) and play the move indicated.

Note that Patashnik’s dictionary doesn’t suffice for such a “dumb” computer player; a player using his dictionary would have to know about “forced sequences” and “blocking moves” in order to make up for the omissions in the dictionary.

Verify (or disprove) that a dictionary is exhaustive

Given a dictionary, plus a subroutine that knows all the symmetries of the board, plus a subroutine that can tell whether a given board position is won by X or not: Roll out the entire reachable game tree and print a reachable position for which the dictionary lacks any continuation. If there is no such position, then the dictionary is exhaustive, and constitutes a constructive proof that the game is a first-player win.

Bonus: Verify that each board position in the dictionary is in fact reachable; prune any that are not reachable; and see if you can re-compress the pruned dictionary to be any smaller.

I have not yet done this for the 12-line dictionary above; if you do, please tell me about it!

It would also be interesting to “complete” Patashnik’s dictionary, now that computer power and disk space are no obstacle. How many lines does the complete dictionary take?

My goal when I started out with this stuff was — and remains — to use it to concisely prove some results in Harary’s generalized tic-tac-toe. See my GitHub repo for some tools, currently very rudimentary.