2

I've been working on a Tic-Tac-Toe AI (Minimax with AB pruning).

As far as I can tell, for an NxN board, player 1 can always win if the goal is to get less than N-1 in a row (for N > 4). Is there a known bound for the number in a row or the size of the board?

1
1

This generalization of Tic-Tac-Toe is called m,n,k-game. (the goal is to get k in a row on a (m,n) board).

Some known bounds: (source wikipedia)

  • (5,5,4) is a draw.
  • (6,6,5) is a draw.
  • (7,7,5) and (8,8,5) are draws.
  • (15,15,5) is a win.
  • (9,6,6) and (7,7,6) are both draws via pairings.

When the goal is 9 or larger (k>=9) the second player can force a draw:

When k = 9 and the board is infinite, the second player can draw via a "pairing strategy". A draw on an infinite board means that the game will go on forever with perfect play. A pairing strategy involves dividing all the squares of the board into pairs in such a way that by always playing on the pair of the first player's square, the second player is ensured that the first player cannot get k in a line. A pairing strategy on an infinite board can be applied to any finite board as well - if the strategy calls for making a move outside the board, then the second player makes an arbitrary move inside the board.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.