Cubic tic-tac-toe: A matching-based approach

Abstract

In the natural generalization of tic-tac-toe to an $n\times n\times n$ board where $n\in \mathbb{N}$, it is known that the first player has a winning strategy if $n\le 4$ and that either player can force a draw if $n\ge 8$. The question of whether the first player has a winning strategy if $n=5,6$ or $7$ has remained open. Here, we prove that the first player does not have a winning strategy if $n=7$. The proof, which is computer-assisted, exploits the fact that the second player's first four moves can always be chosen such that their remaining moves can be automated via a simple pairing strategy. The process of finding the pairing strategy involves reframing the problem in such a way that the goal is to seek a maximal matching in a bipartite graph that represents the tic-tac-toe board after each player has made four moves. We use the Hopcroft-Karp matching algorithm to find such maximal matchings.

21 pages, 4 figures