Mnk-games
|
|
- The title of this article is incorrect because of technical limitations. The correct title is m,n,k-games.
| Contents |
Overview
The mnk-game (or m,n,k-game) is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. Thus, tic-tac-toe is the 3,3,3-game and free-style gomoku is the 19,19,5-game.
Apart from gomoku, mnk-games are mainly of mathematical interest. One seeks to find the game-theoretic value, which is the result of the game with perfect play. This is known as solving the game.
The second player cannot have a winning strategy
A standard strategy stealing argument from combinatorial game theory shows that in no m,n,k-game can the second player win. This is because an extra stone given to either player in any position can only improve that player's chances. The strategy stealing argument assumes that the second player has a winning strategy and demonstrates a winning strategy for the first player. The first player makes an arbitrary move to begin with. After that, she pretends that she is the second player and adopts the second player's winning strategy. She can do this as long as the strategy doesn't call for placing a stone on the 'arbitrary' square that is already occupied. If this happens, though, she can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone can not hurt her, this is a winning strategy for the first player. The contradiction implies that the original assumption is false, and the second player can not have a winning strategy.
This argument tells us nothing about whether a particular game is a draw or a win for the first player. Also, it does not actually give a strategy for the first player.
General results
- If (m, n, k) is a draw, then (m', n', k') where m' ≤ m, n' ≤ n, k' ≥ k is also a draw. As a corollary, if (m, n, k) is a win, then (m', n', k') where m' ≥ m, n' ≥ n, k' ≤ k is also a win.
- If k ≥ 3 and either m < k or n < k, the game is a draw.
- k ≥ 8 is a draw: it has been shown that when k is at least 8, the second player can force a draw even on an infinite board, and hence on any finite board. This means that when the board is infinite the game will go on for ever with perfect play, whereas if it is finite the game will end in a tie. It is not known if the second player can force a draw when k is 6 or 7.
- k = 1 and k = 2 are trivial wins, except for (1,1,2) and (2,1,2)
- k = 3 is a draw for (3,3,3) (see Tic tac toe) and a win otherwise if m ≥ 3 and n ≥ 3.
Specific results
- (m,4,4) is a win for m = 30 (Lustenberger, 1967) and a draw for m = 8. In 2003, it was shown to be a win for m = 9 (Sobotovych).
- (5,5,4) is a draw.
- (6,5,4) is a win.
- (6,6,5) is a draw.
- Computer search by L. Victor Allis has shown that (15,15,5) is a win, even with one of the restrictive rules of Go-Moku.
External link
- W.J. Ma, Generalized tic-tac-toe, [1] (http://www.klab.caltech.edu/~ma/tictactoe.html).
References
- J. W. H. M. Uiterwijk and H. J van der Herik, The advantage of the initiative, Information Sciences 122 (1) (2000) 43-58. Online (http://www.fdaw.unimaas.nl/education/4.2ZT/Initiative.pdf) (pdf)