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

<p>Some known bounds: (source <a href="https://en.wikipedia.org/wiki/M,n,k-game" rel="nofollow noreferrer">wikipedia</a>)</p>

<ul>
<li>(5,5,4) is a draw. </li>
<li>(6,6,5) is a draw. </li>
<li>(7,7,5) and (8,8,5) are draws.   </li>
<li>(15,15,5) is a win. </li>
<li>(9,6,6) and (7,7,6) are both draws via pairings.</li>
</ul>

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

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 4.0
2020-02-02T11:27:44.820Z
2020-02-02T16:08:22.467Z
2020-02-02T16:08:22.467Z
Cohensius
<p>I've been working on a Tic-Tac-Toe AI (Minimax with AB pruning). </p>

<p>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?</p>

CC BY-SA 4.0
2020-02-02T06:17:49.957Z
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 - 
https://en.wikipedia.org/wiki/M,n,k-game
Cohensius
<computer-ai><combinatorial-game-theory><tic-tac-toe>
in Tic-tac-toe on an NxN board, what is the minimum goal (number in a row) that guarantees a tie?
Rafael
# in Tic-tac-toe on an NxN board, what is the minimum goal (number in a row) that guarantees a tie?

(Asked by: username_0 on 2020-02-02)

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?

**Tags:** computer-ai, combinatorial-game-theory, tic-tac-toe

> **Comments:**
> **username_1**: 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 -  https://en.wikipedia.org/wiki/M,n,k-game  

---

## 1 answers

### Answer by username_1 on 2020-02-02. Score: 1 | Accepted answer

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](https://en.wikipedia.org/wiki/M,n,k-game))

* (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.


---

