M,n,k-game


An 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 15,15,5-game. An m,n,k-game is also called a k-in-a-row game on an m×n board.
m,n,k-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.

Strategy stealing argument

A standard strategy stealing argument from combinatorial game theory shows that in no m,n,k-game can there be a strategy that assures that the second player will 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, the player pretends that he is the second player and adopts the second player's winning strategy. He 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, he can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone cannot hurt him, this is a winning strategy for the first player. The contradiction implies that the original assumption is false, and the second player cannot have a winning strategy.
This argument tells 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.

Applying results to different board sizes

A useful notion is a "weak ' game", where k-in-a-row by the second player does not end the game with a second player win.
If weak
' is a draw, then decreasing m or n, or increasing k will also result in a drawn game.
Conversely, if weak or normal ' is a win, then any larger weak ' is a win.
Note that proofs of draws using pairing strategies also prove a draw for the weak version and thus for all smaller versions.

General results

The following statements refer to the first player, assuming that both players use an optimal strategy.
It is possible to consider variants played on a multidimensional instead of a bidimensional board.
For the case of k-in-a-row where the board is an n-dimensional hypercube with all edges with length k, Hales and Jewett proved that the game is a draw if k is odd and
or if k is even and
They conjecture that the game is a draw also when the number of cells is at least twice the number of lines, which happens if and only if