Solving 7,7,5-game and 8,8,5-game

Abstract

An $m n k$ -game is a kind of k-in-a-row game played on an $m \times n$ chess board, where two players alternatively mark empty squares with their own colors and the first one to get k-consecutive marks wins. This paper solves 7,7,5-game and 8,8,5-game as draws. In the proof, we propose some methods based on pairing strategies and potential weights, and then use a program implementing these methods to solve 7,7,5-game in about one minute and 8,8,5-game in about three days.

Keywords

positional games pairing strategy

Get full access to this article

View all access options for this article.

References

Allis, L.V. (1994). Searching for solutions in games and artificial intelligence. PhD thesis, Univ. Limburg, Maastricht, The Netherlands.

Beck, J. (1981). On positional games. J. Combin. Theory Ser. A, 30, 117–133. doi:10.1016/0097-3165(81)90001-7.

Beck, J. (2005). Positional games. Combinatorics, Probability and Computing, 14, 649–696. doi:10.1017/S0963548305007078.

Beck, J. (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press.

Chen, C. (2013). The research of new rules for Gomoku and the results of solving Gomoku with 5 × 5, 6 × 6, 7 × 7 board size. Master thesis (in Chinese). Also available at: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22GN060047016S%22.&searchmode=basic.

Chiang, S.-H., Wu, I.-C. & Lin, P.-H. (2009). On drawn K-in-a-row games. In The 12th Advances in Computer Games Conference (ACG12), Pamplon, Spain.

Chiang, S.-H., Wu, I.-C. & Lin, P.-H. (2011). Drawn K-in-a-row games. Theoretical Computer Science, 412(35), 4558–4569. doi:10.1016/j.tcs.2011.04.033.

Gyorffy, L., Makay, G. & Pluhar, A. (2016). Pairing strategies for the 9-in-a-row game. Submitted.

Hales, A.W. & Jewett, R.I. (1963). Regularity and positional games. Trans. Amer. Math. Soc., 106, 222–229. doi:10.1090/S0002-9947-1963-0143712-1.

10.

Pluhar, A. (2002). The accelerated k-in-a-row game. Theoretical Computer Science, 271(1–2), 865–875. doi:10.1016/S0304-3975(01)00115-3.

11.

Uiterwijk, J.W.H.M. (2017). Set matching: An enhancement of the Hales-Jewett pairing strategy. In

Winands ,

H.J.

van den Herik and

Kosters (Eds.), Advances in Computer Games. ACG 2017. Lecture Notes in Computer Science (Vol. 10664). Cham: Springer.

12.

Uiterwijk, J.W.H.M. & van den Herik, H.J. (2000). The advantage of the initiative. Information Sciences, 122(1), 43–58. doi:10.1016/S0020-0255(99)00095-X.

13.

Van den Herik, H.J., Uiterwijk, J.W.H.M. & van Rijswijck, J. (2002). Games solved: Now and in the future. Artificial Intelligence, 134, 277–311. doi:10.1016/S0004-3702(01)00152-7.

14.

Wu, I.-C. & Huang, D.-Y. (2005). A new family of k-in-a-row games. In The 11th Advances in Computer Games Conference (ACG’11), Taipei, Taiwan.

15.

Wu, I.-C., Huang, D.-Y. & Chang, H.-C. (2005). Connect6. ICGA Journal, 28(4), 235–242.