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.
No comments:
Post a Comment