Higher Dimenional Tic Tac Toe

Question

Here we have a problem that seems very intuitive, but is hard to define mathematically.

In Tic Tac Toe, we can find an equivalent of the game in any number of dimensions, it seems.

The trick is to realize the the game is defined by lines on which the characters can be placed not how the board is drawn.

1D tic tac toe, for example, would be a single column of boxes.

2D tic tac toe, is the classic childrens game.

3D tic tac toe looks like this: (Thanks to PrintActivities.com for the image, which I've shrunk.)

Now, here is the pattern I've noticed:

1-dimensional:

• up/down

2-dimensional

• up/down
• left/right
• diagonal

3-dimensional

• up/down
• left/right
• diagonal
• vertical up down
• vertical diagonal

The number of possible winning combinations seem to be $2n-1$!

Now... how would I express this for the fourth spatial dimension? What ways can this be projected so some one with a worse short-term memory than Leonhard Euler can actually play it ?

This sounds fun (if challanging) to analyze myself, but the question is complicated enough I am interested in the insights of others!

Also, this question is to help assemble a computer game (I'm a programmer) but I intend to link back at least to this page from the game itself, credit where credit's due.

Answer 1

A relevant theorem is the Hales-Jewett theorem. Basically it states that the higher-dimensional, multi-player, $l$-in-a-row generalization of game of tic-tac-toe cannot end in a draw, no matter how large $l$ is, no matter how many people $k$ are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension

Answer 2

It sounds like you're asking about the different types of lines that have to be looked at, for instance all the possible lines through the center of the board. If this is so, then you left out two distinct classes in the 3d case. For convenience, I'm going to use coordinates that go from $0$ to $2$ in each direction, so the center of the board is at $(1,1,1)$. Now, the five different classes of line you mentioned in the 3d case are:

• up-down (which would go through $(1, 0, 1)$, $(1, 1, 1)$ and $(1, 2, 1)$)
• left-right (which would go through $(0, 1, 1)$, $(1, 1, 1)$ and $(2,1,1)$)
• 'flat diagonal' through $(0, 0, 1)$, $(1, 1, 1)$ and $(2, 2, 1)$
• vertical up-down through $(1, 1, 0)$, $(1, 1, 1)$ and $(1, 1, 2)$
• and now, you list 'vertical diagonal', but that's not quite informative enough. In fact, there are two different types of vertical diagonal:
  • one that goes left-right and vertical — or in other words, through $(0, 1, 0)$, $(1, 1, 1)$ and $(2, 1, 2)$...
  • ...and one that goes north-south and vertical — or in other words one that goes through $(1, 0, 0)$, $(1, 1, 1)$ and $(1, 2, 2)$

What's more, there's also another 'long diagonal' that you missed: it goes through $(0, 0, 0)$, $(1, 1, 1)$ and $(2,2,2)$. This gives a total of 7 different 'line classes' in the 3d case.

More generally, in $n$ dimensions there are $2^n-1$ different 'classes' of line by your counting. These correspond perfectly to all the vectors in $\{0,1\}^n$ that aren't the zero vector; each vector of the form $(v_0, v_1, \ldots, v_n)$ corresponds to a line that goes through $(1-v_0, 1-v_1, \ldots, 1-v_n)$, $(1, 1, \ldots, 1)$ and $(1+v_0, 1+v_1, \ldots, 1+v_n)$. This scheme doesn't really work out well for enumerating all of the lines to be checked, though, because it misses things like the distinction between 'diagonals up' and 'diagonals down' - the two different diagonals of the original square, for instance, or the four distinct long diagonals of the cube, etc.

A better count would be the total number of lines; this is eight for the 3x3 game (three horizontal, three vertical, and four diagonals), whereas for the 3x3x3 game it's forty-nine distinct lines (nine horizontal, nine vertical, nine up/down; eighteen 'short diagonal' lines; and four 'long diagonal' lines).

Answer 3

It all depends what you are trying to count. Your terminology is not helpful. Note that in three dimensions you have diagonals in three planes plus body diagonals, for example from "bottom, front, left" to "top, back, right".

One way of looking at the lines you can get is to extend your hypercube one unit in each direction (so that the length of a side is 5). Each line in your $3 \times 3 \times \dots$ can be extended one unit at each end, and no point in the extended cube is at the end of two different lines.

In dimension $r$ the number of lines is therefore $\cfrac {5^r-3^r}2$. The types of line (if you want to analyse) can be organised by whether they hit the outer cube in a corner, edge, face etc (organised by dimension) and the number of "kinds" for each dimension can be counted by counting the number of corners, edges etc (remembering there is one at each end).

So in the cube there are eight corners, so four body diagonals (each hits two opposite corners). There are twelve edges, so six kinds of plane diagonals, two kinds in each plane. There are six faces so three kinds of "straight" line.

Answer 4

The list of winning combinations does not distinguish between e.g. top-left to bottom right diagonal and top-right to bottom left. The $2n-1$ comes from $n$ axes and the $n-1$ kinds of digonals that occur when each box in the line is shifted from the previous along $k$ axes, where $2\leq k \leq n$.

The $4$D board could be represented by three $3$D boards, each is which is represented by three $2$D boards.

Answer 5

I play tic-tac-toe frequently. 4D is the most frequently played game for my group, but 6D's a close second.

Here is 2D:

_|_|_  
_|_|_  
 | |   

Here is 3D:

_|_|_|_
_|_|_|_
_|_|_|_
 | | |

_|_|_|_
_|_|_|_
_|_|_|_
 | | |

_|_|_|_
_|_|_|_
_|_|_|_
 | | |

_|_|_|_
_|_|_|_
_|_|_|_
 | | |

Here is 4D. Be aware even the provided 3D board is a first player win (but a very difficult one). The provided 4D board thus is obviously an even stronger first player win. In practice it works as a fun game. Because of the addition of the middle square, 5X5X5X5 boards actually feel less strategic (sense so much value is caught up in that middle space).

_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
 | | |      | | |      | | |      | | | 

_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
 | | |      | | |      | | |      | | | 

_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
 | | |      | | |      | | |      | | | 

_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
_|_|_|_    _|_|_|_    _|_|_|_    _|_|_|_
 | | |      | | |      | | |      | | | 

If you go to 5D add two spaces in each direction, that should tide you over through 6D.

And your 2n-1 is wrong. In 2 dimensions you have 3 kinds of lines that can be formed, yes. But in 3 dimensions you have 7 kinds of lines, not 5. If left/right, top/bottom, and front/back are different kinds, then each combination of these kinds should be considered to form a unique kind of diagonal. In general the number of kinds of line is (possible combinations of 1 element of N)+(possible combinations of 2 elements of N)+(possible combinations of 3 elements of N)+...(possible combinations of N elements of N).

So that's N!/(1!(N-1)!)+N!/(2!(N-2)!)+N!/(3!(N-3)!)...+N!/(N!(N-N)!)

or $2^N-1$

For 3 dimensions, though, this clearly yields 3+3+1=7 kinds of line.