Mnk-games

The term mnk-games refers to the family of abstract perfect information board games in which two players take turns in placing stones on a rectangular checkerboard and the objective is to get a certain number of stones of one's own color in a line, either orthogonally or diagonally. The mnk-game involves a mxn board and the aim is to get k stones in a row. 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 is solving the game.

A standard strategy stealing argument from combinatorial game theory shows that no mnk-game can be a 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 mnk-game is a (first player) win, then so is the m'n'k-game for m' >= m and n' >= n. (Todo: give proof of this).

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 m44-games are won for m >= 30 and drawn for m <= 8.

• The 5,5,4-game is a draw and 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)