game theory - Tic-tac-toe 1000 in a row

Consider a variant of Tic-Tac-Toe and Gomoku on a board that's infinite in every direction. X wins by getting a line of 1000 X's horizontally, vertically, or diagonally. O cannot win but plays for a draw by preventing X from winning indefinitely. X gets to move twice each time and starts, so the turn order goes XXOXXOXXO....

Can X win with perfect play?

Answer

Yes, X can win.

To simplify things I'm going to take advantage of your rules that O cannot win, so that X doesn't need to worry about O getting 1000 in a row.

Just consider a 1 dimensional game, chose an origin, and label the locations with integers in order.

Define the "bin $K$" as the set of spaces $x$ such that $1000\ K \le x < 1000 (K+1)$.

A simple winning strategy is:

• 
  

  For the first $M$ turns, have X play each piece in a previously empty bin.

  
  


• 
  

  Now while possible, have X play each piece in a bin with only one of its pieces and no O pieces.

  
  


• 
  
  

  Now while possible, have X play each piece in a bin with only two of its pieces an no O pieces.

  
  


• 
  

  And so on.

  
  

It should be intuitively clear that X will always win, with $M$ chosen sufficiently large.

To prove this without relying on intuition, I only need to show there is an answer to

What value of $M$ is sufficient if the win condition for X is to get $Z$ pieces in-a-row?

After $M$ turns, X will have a piece in $2M$ bins, and O can block at most $M$ of them.

After the next $M/2$ turns, X will have two pieces in $M$ bins, and O can block at most $M/2$ of them.

More generally, after $\sum_{t=0}^N M/2^t$ turns, X will have $(N+1)$ pieces in $M/2^N$ bins. Note that $M$ must be at least $2^N$ for the last number of turns in that sequence to be an integer. So $M \ge 2^N$.

So a sufficient value is: $$Z = N+1 \quad\quad \rightarrow \quad\quad M \ge 2^{Z-1} $$

If the rules are changed such that O can win with 1000 in a row, then the math is a bit more complicated. But you could imagine X infrequently using a turn here or there to stop O and then continue on with the plan. X should still be able to win.