Monday 5 October 2015

geometry - N-dimensional Tic-Tac-Toe variant


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

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...