Solving Strong and Weak 4-in-a-Row

JWHM Uiterwijk*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

12 Downloads (Pure)

Abstract

In this paper we first summarize knowledge about the standard (strong) version of the game 4-in-a-Row. It was previously shown that 4-in-a-Row is a draw on 4 x n boards for n = 4-8, and on the 5 x 5 board as well. Further we know that the game is a (first-player) win on the 5 x 6 board. Finally it is stated that 4-in-a-Row is a win on a 4 x 30 board. It is not known if and where there is a transition from drawn games to won games on 4 x n boards for n ranging from 9-29. Using our k-in-a-Row solver we then show that the 4 x n boards for n = 9, 10, and 11 are wins. We provide the principal variations by our solver program for the 5 x 6 and 4 x 9 boards.Further we introduce a second version of the game, weak 4-in-a-Row (also called Maker-Breaker (MB) 4-in-a-Row), where the second player wins if he is able to prevent the first player from winning, but does not win by obtaining a 4-in-a-Row sequence himself. This game benefits the first player, since he can safely ignore any "threats" by the second player. Our results show that for weak 4-in-a-Row the first player already wins on the 5 x 5 and 4 x 7 boards. We also provide the principal variations by our solver program for these boards.We then focus on the monotonicity property of winning positional games. It is widely believed that if a k-in-a-Row game is a win on some board, it will be a win on any larger board as well. This is denoted as a monotone win. As a consequence, if a k-in-a-Row game is a draw on some board, it will be a draw on any smaller board. For weak positional games the monotonicity property holds by definition. However, for the strong version of k-in-a-Row, the monotonicity property has never been formally proven. It is surely not true on arbitrary graphs, where enlarging the winning set might change a winning game into a draw. This phenomenon is known as the Extra Set Paradox. Still it is commonly believed that the monotonicity of winning does hold for rectangular boards. However, we show that even this is not true, at least not for arbitrary positions on a rectangular board. We demonstrate this with a counterexample.To deal with the problem of non-monotonicity we propose an algorithmic solution. Suppose that k-in-a-Row is a win on some m x n board (assuming arbitrarily that m <= n). To prove that this is a monotone win, we enlarge the board with a rim around the m x n board of width at most k-1. On this board the first player is only allowed to play on the inner board, whereas the second player may use the whole board. We show that if with these constraints the first player still wins, the game is also a win on any larger board. Using this method we have shown that the 5 x 6 board indeed is a monotone win. For the 4 x 9 board we had to make a small adaptation, namely that the first player is allowed to use the rim, but only to respond to useless direct threats by the opponent. Moreover, any such stone of the first player in the rim may not contribute to winning variations in any way. Using this we prove that also the win on the 4 x 9 board is monotone. With these results strong and weak 4-in-a-Row are completely solved.
Original languageEnglish
Title of host publicationIEEE Conference on Games
Subtitle of host publicationCoG'19
PublisherIEEE
Number of pages8
ISBN (Print)9781728118840
DOIs
Publication statusPublished - Aug 2019
EventIEEE Conference on Games (IEEE COG) - London, United Kingdom
Duration: 20 Aug 201923 Aug 2019
https://ieee-cog.org/2019/

Publication series

SeriesIEEE Conference on Computational Intelligence and Games
ISSN2325-4270

Conference

ConferenceIEEE Conference on Games (IEEE COG)
Country/TerritoryUnited Kingdom
CityLondon
Period20/08/1923/08/19
Internet address

Cite this