# in Tic-tac-toe on an NxN board, what is the minimum goal (number in a row) that guarantees a tie?

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?

• This generalization of Tic-Tac-Toe is called m,n,k-game. (getting k in a row on a (m,n) board). See wikipedia for some known results - en.wikipedia.org/wiki/M,n,k-game Feb 2 '20 at 6:17

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.