Winning strategies in multidimensional tic-tac-toe
This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a conjecture. Now, after several years of mathematical training at a university, I am still unable to settle the conjecture, so I present it to you.
The classical tic-tac-toe game is played on a $3\times3$ grid and two players take turns to put their mark somewhere in the grid. The first one to get three collinear marks wins. Collinear includes horizontal, vertical and diagonal lines. Experience shows that the game always ends in a draw if both players play wisely.
Let us write the grid size $3\times3$ as $3^2$. We can change the edge length by playing on any $a^2$ grid (where each player tries to get $a$ marks in a row on the $a\times a$ grid). We can also change dimension by playing on any $a^d$ grid, for example $3^3=3\times3\times3$. I want to understand something about this game for general $a$ and $d$. Let me repeat: The goal is to make $a$ collinear marks.
I assume both players play in an optimal way. It is quite easy to see that the first player wins on a $2^d$ grid for any $d\geq2$ but the game is a tie on $2^1$. The game is a tie also on $3^1$ and $3^2$, but my experience suggests that the first player wins on $3^3$ but the game ties on $4^d$ for $d\leq3$. It seems quite credible that if there is a winning strategy on $a^d$, there is one also on $a^{d'}$ for any $d'\geq d$, since more dimensions to move in gives more room for winning rows. This answer to a related question tells that for any $a$ there is $d$ so that there is a winning strategy on $a^d$.
This brings me to the conjecture:
There is a winning strategy for tic-tac-toe on an $a^d$ grid if and only if $d\geq a$.(Refuted by TonyK's answer below.)
Is there a characterization of the cases where a winning strategy exists? It turns out not to be as simple as I thought.
To fix notation, let $$ \delta(a)=\min\{d;\text{first player wins on }a^d\} $$ and $$ \alpha(d)=\max\{a;\text{first player wins on }a^d\}. $$ The main question is:
Is there an explicit expression for either of these functions? Or decent bounds? Partial answers are also welcome.
Note that the second player never wins, as was discussed in this earlier post.
A remark for the algebraically-minded: We can also allow the lines of marks to continue at the opposite face when they exit the grid; this amounts to giving the grid a torus-like structure. Now there are no special points, unlike in the usual case with boundaries. Collinear points on a toric grid of size $a^d$ corresponds to a line (maximal collinear set) in the module $(\mathbb Z/a\mathbb Z)^d$. (If $a$ is odd, then $a$ collinear points in the mentioned module add up to zero, but the converse does not always hold: the nine points in $(\mathbb Z/9\mathbb Z)^3$ with multiples of three as all coordinates add up to zero but are not collinear.) This approach might be more useful when $a$ is a prime and the module becomes a vector space. Anyway, if this version of the game seems more manageable, I'm happy with answers about it as well (although the conjecture as stated is not true in this setting; the first player wins on $3^2$).
I will quote some results and problems from the book Combinatorial Games: Tic-Tac-Toe Theory by József Beck, some of which were also quoted in this answer.
The terms "win" and "draw" refer to the game as ordinarily played, i.e., the first player to complete a line wins. The term "Weak Win" refers to the corresponding Maker-Breaker game, where the first player ("Maker") wins if he completes a line, regardless of whether the second player has previously completed a line; in other words, the second player ("Breaker") can only defend by blocking the first player, he cannot "counterattack" by threatening to make his own line. (Note that ordinary $3\times3$ tic-tac-toe is a Weak Win.) A game is a "Strong Draw" if it is not a Weak Win, i.e., if the second player ("Breaker") can prevent the first player from completing a line.
Theorem 3.1 Ordinary $3^2$ Tic-Tac-Toe is a draw but not a Strong Draw.
Theorem 3.2 The $4^2$ game is a Strong Draw, but not a Pairing Strategy Draw (because the second player cannot force a draw by a single pairing strategy.)
Theorem 3.3 The $n\times n$ Tic-Tac-Toe is a Pairing Strategy Draw for every $n\ge5.$
For a discussion of Oren Patashnik's computer-assisted result that $4^3$ tic-tac-toe is a first player win, Beck refers to Patashnik's paper:
Oren Patashnik, Qubic: $4\times4\times4$ Tic-Tac-Toe, Mathematics Magazine 53 (1980), 202-216.
Not much more is known about multidimensional tic-tac-toe, as can be seen from the open problems:
Open Problem 3.2 Is it true that $5^3$ Tic-Tac-Toe is a draw game? Is it true that $5^4$ Tic-Tac-Toe is a first player win?
The conjecture that "if there is a winning strategy on $a^d$, there is one also on $a^{d'}$ for any $d'\geq d$" is given as an open problem:
Open Problem 5.2 Is it true that, if the $n^d$ Tic-Tac-Toe is a first player win, then the $n^D$ game, where $D\gt d$, is also a win?
Open Problem 5.3. Is it true that, if the $n^d$ game is a draw, then the $(n+1)^d$ game is also a draw?
To see that the intuition "adding more ways to win can't turn a winnable game into a draw game" is wrong, consider the following example of a tic-tac-toe-like game, attributed to Sujith Vijay: The board is the set $V=\{1,2,3,4,5,6,7,8,9\};\ $ the winning sets are $\{1,2,3\},$ $\{1,2,4\},$ $\{1,2,5\},$ $\{1,3,4\},$ $\{1,5,6\},$ $\{3,5,7\},$ $\{2,4,8\},$ $\{2,6,9\}$. As in tic-tac-toe, the two players take turns choosing (previously unchosen) elements of $V;$ the game is won by the first player to succeed in choosing all the elements of a winning set. It can be verified that this is a draw game, but the restriction to the board $\{1,2,3,4,5,6,7\}$ (with winning sets $\{1,2,3\},$ $\{1,2,4\},$ $\{1,2,5\},$ $\{1,3,4\},$ $\{1,5,6\},$ $\{3,5,7\}$) is a first-player win.
$4^3$ ("Qubic") is a win for the first player. According to this link, it was first proved by Oren Patashnik in 1980. The proof is complicated. It took 12 years for this proof to be converted into a practical computer algorithm; I was present at the 1992 Computer Olympiad where the program of Victor Allis and Patrick Schoo romped to victory.
Based on what I remember from playing such games twenty-five years ago,
The $3^3$ version is a guaranteed win for the first player, by going in the middle square. There are so many lines through it that the first player can always force moves. After the 2nd player places his irrelevant O, the first player chooses a plane through the middle X that doesn't contain that one O. Then, the game is henceforth played in that plane, where the first player effectively takes the first two moves in a row and forces a win.
Because of the forced moves, $3^n$ is equally a win for the first player for all $n\ge 3$.
The $4^3$ version does not admit such a simple strategy (nor does the $4^4$).