Mnk-games Guide, Meaning , Facts, Information and Description
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.
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 move given to either player in any position can only improve that player's chances. Thus, suppose that the second player has a winning strategy. Then the first player makes an arbitrary move to begin with and then pretends that she is the second player and adopts the second player's winning strategy. She can do this as long as the strategy calls for moving on the square that she initially placed a stone on. But this extra stone can only help her, so she makes another arbitrary move and continues as before. This ensures that the first player wins, contradicting the assumption that the second player has 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.
Another general theorem is that if the m,n,k-game is a (first player) win, then so is the m',n',k-game for m' ≥ m and n' ≥ n. For suppose that this isn't the case, then the second player has a drawing strategy on the larger board. But this strategy can be converted into a drawing strategy on the smaller board, by playing at random whenever the strategy requires a move outside the confines of the smaller board, or in a square already played in by the second player. Since an extra move is never a disadvantage, this strategy achieves a draw on the smaller board. This contradicts the condition that the smaller board was a first-player win. So our assumption must be wrong, and the second player has no drawing strategy on the larger board.
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. For smaller k, the following results are known:
- k = 1 and k = 2 are trivial wins. k = 3 is a win except for m = n = 3.
- The m,4,4-games are won for m ≥ 30 and drawn for m ≤ 8.
- The 5,5,4-game is a draw.
- The 6,5,4-game is a win.
- The 6,6,5-game is a draw.
Reference
- J. W. H. M. Uiterwijk and H. J van der Herik, The advantage of the initiative, Information Sciences 122 (1) (2000) 43-58. Online (pdf)
This is an Article on Mnk-games. Page Contains Information, Facts Details or Explanation Guide About Mnk-games