×

The pairing strategies of the 9-in-a-row game. (English) Zbl 1422.91107

Summary: One of the most useful strategies for proving Breaker’s win in Maker-Breaker positional games is to find a pairing strategy. In some cases there are no pairing strategies at all, in some cases there are unique or almost unique strategies. For the \(k\)-in-a-row game, the case \(k = 9\) is the smallest (sharp) for which there exists a Breaker winning pairing (paving) strategy. One pairing strategy for this game was given by A. W. Hales and R. I. Jewett [Trans. Am. Math. Soc. 106, 222–229 (1963; Zbl 0113.14802)].
In this paper we show that there are other winning pairings for the 9-in-a-row game, all have a very symmetric torus structure. While describing these symmetries we prove that there are only a finite number of non-isomorphic pairings for the game (around 200 thousand), which can be also listed up by a computer program. In addition, we prove that there are no “irregular”, non-symmetric pairings. At the end of the paper we also show a pairing strategy for a variant of the 3-dimensional \(k\)-in-a-row game.

MSC:

91A24 Positional games (pursuit and evasion, etc.)
91A46 Combinatorial games

Citations:

Zbl 0113.14802
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] L. V. Allis, H. J. van den Herik and M. P. H. Huntjens, Go-Moku solved by new search techniques, Comput. Intell. 12 (1996), 7-23, doi:10.1111/j.1467-8640.1996.tb00250.x.
[2] J. Beck, Van der Waerden and Ramsey type games, Combinatorica 1 (1981), 103-116, doi: 10.1007/bf02579267. · Zbl 0519.05005
[3] J. Beck, Combinatorial Games: Tic-Tac-Toe Theory, volume 114 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2008,http://www. cambridge.org/9780521461009.
[4] E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 3, A K Peters/CRC Press, Natick, Massachusetts, 2nd edition, 2003. · Zbl 1011.00009
[5] A. Csernenszky, R. R. Martin and A. Pluh´ar, On the complexity of chooser-picker positional games, Integers 12 (2012), 427-444, doi:10.1515/integ.2011.113. · Zbl 1242.91023
[6] R. K. Guy and J. L. Selfridge, Problems and solutions: Problems dedicated to Emory P. Starke: S10, Amer. Math. Monthly 86 (1979), 306-306, doi:10.2307/2320758.
[7] A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222-229, doi:10.2307/1993764. · Zbl 0113.14802
[8] K. Kruczek and E. Sundberg, A pairing strategy for tic-tac-toe on the integer lattice with numerous directions, Electron. J. Combin. 15 (2008), #N42,http://www.combinatorics. org/ojs/index.php/eljc/article/view/v15i1n42. L. Gy˝orffy et al.: The pairing strategies of the 9-in-a-row game109 · Zbl 1160.91008
[9] G. Makay, 9-in-a-row game,http://www.math.u-szeged.hu/˜makay/amoba/, accessed on 6 December 2016.
[10] P. Mukkamala and D. P´alv¨olgyi, Asymptotically optimal pairing strategy for tic-tactoe with numerous directions, Electron. J. Combin. 17 (2010), #N33,http://www. combinatorics.org/ojs/index.php/eljc/article/view/v17i1n33. · Zbl 1202.91044
[11] T. G. L. Zetters, Problems and solutions: Solutions of problems dedicated to Emory P. Starke: S10, Amer. Math. Monthly 87 (1980), 575-576, doi:10.2307/2321433.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.