Is there a generic algorithm to solve m,n,k games?

560 Views Asked by At

In an $m,n,k$ board game, 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.

The $m=3, \quad n=3, \quad k=3$ game is the classic tic-tac-toe.

Is there a generic solution for all such $m,n,k$ games, or is it not possible?

It is known that, if both players perform perfect play (optimal strategy):

  • $k ≥ 9$ is a draw.

  • $ k > m$ or $k > n$ is a draw.