Hypercube Tic-Tac-Toe
Solomon W. Golomb, Alfred W. Hales · 2002
. We study the analogue of tic-tac-toe played on a fc-dimensional hypercube of side n. The game is either a first-player win or a draw. We are primarily concerned with the relationships between n and k (regions in n-k space) that correspond to wins or draws of certain types. For example, for each given value of k , we believe there is a critical value n d of n below which the first player can force a win, while at or above this critical value, the second player can obtain a draw. The larger the value of n for a given fc, the easier it becomes for the second player to draw. We also consider other “critical values” of n for each given k separating distinct behaviors. Finally, we discuss and prove results about the misere form of the game. 1. Introduction Hypercube tic-tac-toe is a two-person game played on an n k “board” (i.e. a /c-dimensional hypercube of side n ). (The familiar 3 x 3 game has k = 2 and n = 3. Several editions of the 4 3 game, k = 3 and n = 4, are commercially available.) In all these games the two players take turns. Each player claims a single one of the n k cells with his/her symbol (traditionally O's and X's, or “noughts and crosses”, as the game is known in the UK), and the first player to complete a “path” of length n (in any straight line, including any type of diagonal) is the winner. If all n k cells are filled (with the two kinds of symbols) but no solid-symbol path has been completed, the game is declared a draw. Since the first move cannot be a disadvantage, with best play the first player should never lose. Hence, in the ideal world, the first player seeks a win, while the second player tries to draw. For each given value of k , we believe there is a critical value n d of n below which the first player can force a win, while at or above this critical value, the second player can obtain a draw. This exact value of n is exceedingly difficult to determine as a function of k. (The larger the value of n for a given k, the easier it becomes for the second player to draw.)