I have been asked, "How many solutions are there, how many ways can you win, in a three-dimensional game of Tic-Tac-Toe?"
Not regular Tic-Tac-Toe
This suggests that we have a three-dimensional tic-tac-toe board. This would be a volumetric board, akin to a 3x3x3 tensor, where each "space" is a three dimensional cube, not a two dimensional square. So you're not drawing on the outside of the cube; imagine that your cube is a stack of 27 boxes, arranged in a 3x3x3 pile, and for each move you open up one of the boxes and place an X or an O inside the box.
Stack three 2D boards to make a 3D board
There are multiple ways to solve this. The most obvious way might be to say "well, a 3D tic-tac-toe board is just a stack of three regular (2D) tic-tac-toe boards, and a regular game has eight solutions" (three rows, three columns, two diagonals). If a 2D board has x and y dimensions, then the 3D board has three of these 2D boards stacked one on top of another along the z dimension. Simple enough. So you have 8x3=24 solutions. But then, you can also play along x and z. And you can also play along y and z. So it's actually 8x3x3=72 solutions. But there's more! You also have completely new three-dimensional solutions that span x and y and z, that go from one corner of the cube to the exact opposite corner. These didn't exist in the 2D game at all! There are four of those. So now we have 76 solutions. I can't think of any more beyond those. So that's our max possible count.
One solution is found in two different planes
But I immediately see a problem. We've double-counted some of our solutions. Look at any edge of the cube. The solution that runs along that edge is contained in BOTH of the faces that meet at that edge. We've included this solution in both of our sets of eight for those two faces. And this problem is not limited to edges. Lines that run along the center of a face are also contained in two planes. And lines that run through the center of the cube are also contained in two planes. We've double counted a ton of solutions! Well, if we're careful and methodical, we can work through this and find that we've double counted 27 solutions. 76-27=49. And that is the correct answer. The 2D diagonals and those fancy new 3D diagonals are all independent. No double counting for those. But is there an easier, more organized way to solve this problem? There certainly is!
1D, 2D solutions on a 2D board
Instead of over-estimating and then subtracting, we can count all of our solutions in a more organized way from the beginning and not over-estimate anything. We can sort all of our solutions into categories and calculate those categories individually. I'm sure there's more than one way to do this, but the method that seems obvious to me is to categorize our solutions by their dimensionality. On a 2D board, we have two dimensions, x and y. As we said previously, we have rows and columns and diagonals. Well a row is one-dimensional. And a column is one-dimensional. And those diagonals are two-dimensional (the solution spans two dimensions). And that's as high as we can go on a 2D board. But that gives us 3x2=6 1D solutions and 2 2D solutions, which add up to the 8 that we expected.
1D, 2D, 3D solutions in a 3D board
What about three dimensions? We're expecting to get 49 total. Let's start out with 1D solutions. Looking at our 3x3x3 cube, there are clearly nine along each axis, and we have three axes, so 9x3=27. As for 2D solutions, those 2D diagonals that we saw on the 2D board, we have two of those in each plane. And we have nine planes, three stacked along each of three axes. So 2x3x3=18. As for 3D solutions, we have the same 4 as before. 27+18+4=49. Great. It works.
All the spaces on a 4D board
So that answers our original question, how many solutions are there in a 3D tic-tac-toe game. 49. Great. But why stop there? We now have a generic algorithm for solving an n-dimensional game. What's next? How about four dimensions? I spent a while ... I don't know how long exactly but a while ... counting solutions by hand. I can't visualize a 4D cube (though I wish so badly that I could! It seems like the imagination should be able to contain higher dimensions, but alas, I haven't figured it out.) so I drew out a 2D array of 2D squares. 2Dx2D=4D. All the cells of a 4D cube are there, just in a different arrangement. I can plot all possible solutions on this grid of grids. Each small board is x and y, and the rows of boards are z and the columns of boards are ... let's say w. Same algorithm as before, let's count the multiplicity of each solution type.
- For 1D, it's fairly straight forward. Let's look at solutions along the x axis. Each board contains 3 of them, three rows. Then we have 3x3 boards. So 3x3x3=27 1D solutions along the x axis. Then we have four axes, so 27x4=108 1D solutions in total.
- 2D goes more or less the same way. Our 2D solutions have to span two dimensions. Let's start with x and y. On each of our little boards we can draw two solutions, and then we multiply that times nine little boards. 2x9=18 solutions in x/y. But we have four dimensions available, so there are 4nCr2=6 combinations of two dimensions available. That gives us 18x6=108 2D solutions. (The fact that this count is equal to the 1D count is just a coincidence.)
- For 3D solutions, it'll help to visualize in 3D. If we look back at our 3D example, we know we have 4 3D solutions in a 3D space. And then we have three copies of that 3D space along our fourth dimension, so 4x3=12. Multiply that by the number of combinations of three dimensions (4nCr3=4) and we get 12*4=48 3D solutions in total.
- Last of all, 4D solutions. We know these have to start at one vertex and end at the opposite vertex. Each vertex has exactly one "opposite" vertex, so this last count is always going to be the number of vertices divided by two (because the solution going from a to b and the solution going from b to a are the same solution). Four dimensions means 2^4=16 vertices and therefore 16/2=8 4D solutions.
This all adds up to 108+108+48+8=272 solutions for a 4D tic-tac-toe board. Phew.
A 5D Hypercube, taken from Wikipedia
Should we count for a 5D board now? I ... honestly ... don't want to. Instead, I'd rather identify the pattern so I can just calculate the answer directly. Let's try that out. We've already calculated the multiplicity of each solution dimensionality for each board dimensionality, so let's put that in a table and see if any patterns jump out.
Counts of solution types according to dimensionality of board
Looking at all these numbers, there are obviously some patterns present. We see a lot of 3's, representing the size or length of the tic-tac-toe board. And we see lots of 2's, 3's, and 4's which clearly correspond to the dimensionality of the board or the dimensionality of the solution type. After staring at this for a while, and working through several iterations of equations, I came up with the following solution:
This actually works
where b is the dimensionality of the board, s is the size of the board (3 for standard tic-tac-toe) and d is the dimensionality of the particular solution.
This equation seems to work for all solution types up to 4D. Originally I created equations for each dimensionality, but eventually I realized that one equation could represent them all. So I can solve this one equation for each solution type, and add those up to get the total solutions for a given board dimensionality. And that means that I can write this out as a finite series instead of writing out different equations for each solution type.
Putting it into a series doesn't reduce the work to do, but it makes the notation simpler
That's pretty cool. I can now write a single equation that will calculate the total number of tic-tac-toe solutions for any board up to 4D at least, and I hope it's accurate for higher dimensional games as well. If we put in numbers for a 5D board, we get 405+540+360+120+16=1441. Woo. The count is growing fast, but this one equation makes it pretty easy.
The only thing I can think of that would be better than this simple finite series would be a closed form solution. But I've been out of college for a long time and I don't remember how to do anything like that. This is as far as my intuition will take me. But ... what advice could ChatGPT give me? I asked ChatGPT "How can I turn a sum or finite series into a closed-form solution?" ChatGPT gave me a very long and thorough, and frankly quite impressive, answer including solutions for a large variety of standard forms. I responded "My series is not a standard form. ∑(from n=1 to d) of 2^(n-1)*s^(d-n)*(d nCr n)". And then ChatGPT just solved it for me.
Good god. For the past several years I've been cautiously optimistic about LLMs, but rarely will I trust them enough to do anything important. This response floored me and for the first time I feel like my job might honestly be threatened in the near future. I plugged this closed form solution into a spreadsheet to test it out, and it gave different results than my finite series. I was confident that my finite series was right up to 4D. But I saw that ChatGPT's solutions were all simply off by a factor of 3. I told ChatGPT this, and it characteristically said "oh yes, you're right! I am wrong! Here's the correct answer!" And then it gave me several more pages of derivation, and in the very last step it made a very obvious mistake and replaced a 2 with a 3. So I'm a bit less concerned about being replaced by LLMs, at least as long as they're this sloppy and clueless. ChatGPT can convert a series to a closed form solution but it doesn't understand that 2x3 is 6 and not 3.
ChatGPT actually got it! (almost)
But most importantly, this works! At least up to 4D or 5D! That's amazing and I'm thrilled. If we continue that spreadsheet down a few more lines, we see that the number of solutions explodes as we move into higher and higher dimensions. By the time that we learn how to play 30-dimensional tic-tac-toe, there are 2.2 million times as many solutions as there are playable spaces!
That's all. That's the end. That's all I have to say. This was fun to work on. If anyone wants to play some high-dimensional tic-tac-toe, see if there are strategies more complex than those for the 2D version, let me know.