3
$\begingroup$

Imagine playing tic tac toe, but rather than the standard 3 by 3 grid, the board extends indefinitely in every direction. When playing the usual game, one player must get three squares in a row to wind the game. However, with an infinite grid, three in a row become pointless, as the first player is guaranteed to be able to get two in a row with nothing on either end. This would allow for a win on the next turn regardless of what the second player does. This could be fixed if the required consecutive squares was increased, such as to four in a row. What would be a winning strategy for this rule set? What about for five in a row? Is there a point where it becomes impossible to win given perfect playing?

$\endgroup$
11
  • 1
    $\begingroup$ This seems to also be Connect-4 on an infinite grid (this might help with searching). What have you tried? 4-in-a-row seems to be easily possible. $\endgroup$ Commented Nov 11, 2021 at 18:11
  • 2
    $\begingroup$ $4$ in a row still looks like an easy win for the first player. Not sure what length stops that, or even if there is such a length. $\endgroup$
    – lulu
    Commented Nov 11, 2021 at 18:11
  • 1
    $\begingroup$ And here is an app that lets you play the $5$ in a row version. For $4$ in a row, I expect you could just break down all possible early move strategies. Should be "easy" but tedious. In practice (a few minutes with pencil and paper) it is always effortless. $\endgroup$
    – lulu
    Commented Nov 11, 2021 at 18:16
  • 1
    $\begingroup$ In fact, even in "five wins" on an infinite grid , the first player has a winning strategy. For "four wins" , I think, it is easy to find all cases without computer help. $\endgroup$
    – Peter
    Commented Nov 11, 2021 at 18:37
  • 1
    $\begingroup$ The stealing argument at least shows that the second player cannot have a winning strategy. Intuitively, there should be a number for which the game ends in a draw with perfect play, but a proof of this won't be easy. $\endgroup$
    – Peter
    Commented Nov 11, 2021 at 18:42

1 Answer 1

5
$\begingroup$

(m,n,k)-game: get $k$ in a row on a $m\times n$ board. There is a wiki page that talks about this exact problem: https://en.wikipedia.org/wiki/M,n,k-game

"Computer search by L. Victor Allis has shown that (15,15,5) is a win"

"$k \geq 8$ is a draw on an infinite board... It is not known if the second player can force a draw when k is 6 or 7 on an infinite board."

So we know that for $k\leq 5$ is a win for the first player, for $k\geq 8$ is a draw, and for $k = 6,7$ we don't know.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .