Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions.(English)Zbl 1202.91044

Summary: We show that there is an $$m = 2n + o(n)$$, such that, in the Maker-Breaker game played on $$\mathbb Z^d$$ where Maker needs to put at least $$m$$ of his marks consecutively in one of $$n$$ given winning directions, Breaker can force a draw using a pairing strategy. This improves the result of K. Kruczek and E. Sundberg [Electron. J. Comb. 15, No. 1, Research Paper N42, 6 p. (2008; Zbl 1160.91008)] who showed that such a pairing strategy exists if $$m \geqslant 3n$$. A simple argument shows that m has to be at least $$2n + 1$$ if Breaker is only allowed to use a pairing strategy, thus the main term of our bound is optimal.

MSC:

 91A46 Combinatorial games

Zbl 1160.91008
Full Text: