Potential-based strategies for tic-tac-toe on the integer lattice with numerous directions

Klay Kruczek ; Eric Sundberg

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

We consider a tic-tac-toe game played on the $d$-dimensional integer lattice. The game that we investigate is a Maker–Breaker version of tic-tac-toe. In a Maker–Breaker game, the first player, Maker, only tries to occupy a winning line and the second player, Breaker, only tries to stop Maker from occupying a winning line. We consider the bounded number of directions game, in which we designate a finite set of direction-vectors ${\cal S} \subset {\Bbb Z}^d$ which determines the set of winning lines. We show, by using the Erdős–Selfridge theorem and a modification of a theorem by Beck about games played on almost-disjoint hypergraphs, that for the special case when the coordinates of each direction-vector are bounded, i.e., when ${\cal S} \subset \{ \vec{v} : \|\vec{v}\|_\infty \leq k \}$, Breaker can win this game if the length of each winning line is on the order of $d^2\lg(dk)$ and $d^2\lg(k)$, respectively. In addition, we show that Maker can build winning lines of length up to $(1+o(1))d\lg k $ if ${\cal S}$ is the set of all direction-vectors with coordinates bounded by $k$. We also apply these methods to the $n$-consecutive lattice points game on the $N^d$ board with (essentially) ${\cal S} = {\Bbb Z}^d$, and we show that the phase transition from a win for Maker to a win for Breaker occurs at $n= (d+o(1))\lg N$.

Détail

DOI : 10.37236/277

Classification : 91A46
Mots-clés : tic-tac-toe, Maker-Breaker version, directions game