N-dimensional Tic-Tac-Toe variant

Question

Consider the game surface to be an infinite N dimensional Cartesian lattice.

The rules are X moves first, but O gets to move twice each turn, so the move order goes XOOXOOXOO.... The goal is for X to get as long a sequence of neighboring X pieces in a straight line as possible. The goal of O is only to keep the line X may get as short as possible.

Given perfect play and some dimension N, what is the maximum number of pieces in-a-line that X can get in this game?

To make it clear what is meant by in-a-line in this context, consider a vector displacement between points on the lattice. If all the components of this vector are -1, 0, or +1 and the norm of this vector is greater than zero, then this displacement will take you from one point to a neighboring point (let's use this as the definition of neighbor). If there is a sequence of K neighbors, separated by a constant displacement vector, then these K points are "in-a-line".

So for N=1 we just have a line, with each point having two neighbors. For N=2 the game surface is a plane (like normal Tic-Tac-Toe, but infinite), with each point having 8 neighbors (4 on "diagonals"). For N=3, each point has 26 neighbors (20 on "diagonals"). Etc.

---

N=1 is trivial, yet already N=2 seems hard. It is not difficult for X to get a line of 3 in N=2, but I can't even convince myself if a line of 4 is impossible or not. Things become even more interesting in higher dimensions as the number of neighbors explodes exponentially.

So even a limited solution (such as a concrete answer for N=2) would be a quite interesting and an acceptable answer to this puzzle.

Answer 1

The best move that player o can make each turn is to "cap" the currently longest line, i.e. placing an "o" at each endpoint of the current longest line. From there, the longest chain that player x can make is just the degrees of freedom in the lattice space, with degrees of freedom referring to the number of positive directions that a chain can be built in.

The number of degrees of freedom for a n-dimensional lattice space when not counting diagonal chains is equal to n. In this case, the only "positive directions" are those aligned with the Cartesian axes.

When you add diagonals into the equation, then it becomes a problem of determining the number of unique, nonzero vectors that can exist in n-dimensional space and only have 0 or 1 for each component. This is related to binary number theory, and is just the number of nonzero integers that can be represented with n bits. As it turns out, this is equal to 2ⁿ - 1.

EDIT: This proof only applies when x only makes new moves connected to old moves. If x plays in multiple islands and then connects them, he could theoretically get a chain of four or longer. I'm of the belief that in this way, the maximum chain length for n dimensions would be 2 (2ⁿ - 1) - 1, which accounts for connecting two independent chains at the middle, but I have no way of backing this up, really.

Answer 2

I don't know solution for any N, but may be investigation of more general problem can be helpful.

Let's say we have N dimensional space and for each X turn O has M turns. Call the result (max length for X) - L(N,M). Here I call players - X and O, and their marks - x and o. Then:

1. L(1,2+) = 1. Obvious.
2. L(1,1) = 2. This one is more interesting. Let's prove the value.
   1 is unreachable for O. And 2 is reachable by following the simple rule: When X makes turn put your 'o' always on the right of 'x', unless you can't.. when you can't - put it on the left. This guaranties that all new 1-x-size "islands", which X creates are limited on the right and(!) no island can grow.
   Note, that if X always put x in distant parts of our space, we never actually see line of 2 x's. And O's goal not to create such a lines limited on the ends, but to prevent them. This must be common for all (N,M) cases.
3. L(2, 8+) = 1. This is equivalent for L(1,2).
4. L(2, 6) = 2. This is equivalent for L(1,1) in sense of safety (we surround the island from all sides and can forget about it), but note, that 6 <> 8/2, things become more interesting here. To surround horizontal/vertical xx we need 10 o's, but to surround diagonal xx we need 12 o's at least. So the rule would be - surround any new x with 6 o's: 3 on the top, 2 more on the right and 1 more at the bottom. If X attaches one more x - surround both. Simple and safe. This of course can be optimised, because we don't need all-sides-surrounding, only 2-sides.
5. L(2,4) = 2. This can be done. There are basically 4 possible lines directions (hor, vert, 2 x diag) and we need to limit each of them on one side exactly. For example we can limit each new x putting 3 o on top and 1 more on the right. When X attaches second x we still need to limit it in some places on top and right. First x will limit only one way, so up to 3 ways must be blocked with o's. Note the difference with L(1,1), where first x on the island limits second x "halffully" making all job, which O had to do with first x. So we spend 3 o's to do with second x the same thing, which we did with first x before, then we got 1 o left to limit our line - this is exactly what we need. Thereby we have all x's, independently of when they are added on the board or on the island limited on 4 sides, this guaranties that we can end any xx line from growing.
6. L(2,3) = ?. This where things get messy already. O can't lock all 4 directions for first x, X put second x correspondingly and get xx line unlimited on both ends, but will it help to create X to create xxx line? O still have 2 o's to limit any line and 1 o to make precautions. But O now can't stop X's islands from growing, on early stages at least, thereby, X can create folks now and make groups of xx lines, which are not limited at 3 or may be even 4 directions, the last will mean that xxx line will be created.
   I played this game a bit, and it feels like L(2,3) = 2, but a short strategy is hard to find. I think, O must limit all 3 ways on the top (diagonals are the most important), deal with all folks on the bottom and slowly surround the island on all sides. I hope to finish this case later (or someone else can do it, then may be we can go to L(2,4) or L(3,M)).

Answer 3

I don't know the answer exactly, but roughly speaking it should scale with $N$.

Suppose the answer is a line of length $n$, and suppose that the O player is able to contain the X player in a hypercube with side of length $n$.

Then the X player will have placed $n^N$ X's.

The O player will have surrounded the hypercube on all sides, which requires $2Nn^{N-1}$ O's (actually a bit more than that because we need the edges. But bare with me for now). Of course the O player gets to put down twice as many O's.

So this establishes an equation of

\begin{equation} 2Nn^{N-1}=2n^N\end{equation}

Which reduces to $N=n$.

However, things aren't quite that simple, because I've excluded the edges of the surrounding hypercube. I could include those twice, and the corners thrice, by looking at $2N(n+2)^{N-1}$. The number of corners is $2^N$. The number of edges is $nN2^{N-1}$.

So an overall equation can be set up and solved for $N$.

\begin{equation} 2N(n+2)^{N-1}-2.2^N-nN.2^N=2n^N\end{equation}