Tic-tac-toe 1000 in a row

Question

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 1

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.

Answer 2

Here's an easy "intuitive" explanation how X can win:

If X can get a 998 in a row and it's her turn, she has won.

So, if she can get TWO 998s in a row, and it's Os turn, she has won.

{O will only be able to cover one - so it's over}

So, if she can get FOUR 997s in a row, and it's O's turn, she has won.

(O will only be able to cover ..two times.., so there will be two 998s and it's O's turn - so it's over.}

So, if she can get EIGHT 996s in a row, and it's Os turn, she has won.

(O will only be able to cover ..four times.., so there will be four 997s and it's O's turn - so it's over.}

So, if she can get SIXTEEN 995s in a row, and it's Os turn, she has won.

{O will only be able to cover ..eight times.., so there will be eight 996s and it's O's turn - so it's over.}

... and eventually ...

So, if she can get < a very large number == NN > 1s in a row, and it's Os turn, she has won.

To repeat, if she can get NN 1s in a row, she has won.

---

So to win, simply: on the y cartesian axis (say), X simply keeps putting "one". ie, X simply creates an incredibly tall column, that is to say, just keeps "starting one row" after another.

She is able to add one unblocked row each time (the other one gets covered by O).

Simply, after NN goes... (that is to say, 2xNN points placed)...

she will have NN 1s in a row.

She has won!

---

footnote: regarding 2Dism. X's first step is to get "NN 1s" in play. Above I describe them as being simply all horizontal and stacked-up. In fact, NN could hugely separate each attempt, and allow each one to be either H or V. (For a given line, of course, X could not change between H/V, after, two points are down). In this way, it's twice as hard for O to block (this applies strictly on "stage 1" only .. enroute to "NN 1s"). So intertestingly, for "stage 1", X need only take NN / 2 goes (ie, NN points placed) to achieve "NN 1s". But wait! It occurs, X gets to place four potential lines with each (hugely-spaced) two dots. O can only block one alone of the four. So in fact if I'm not mistaken for "stage 1", X need only take NN / 3 goes.

Answer 3

EDIT: I withdraw my solution, I somehow missed the 2-X moves for 1 -O move.

You assume that O's priority is to immediately block bins.

If I was O,

X plays in 2M bins. O plays to the left in 2M bins, so far no bins blocked. X plays 2nd consecutive piece in any bin, O plays to the right of it, blocking it.

This strategy allows X to open unlimited bins at count 1 but 0 bins at count 2, but they will be thwarted before it gets to 1000. ie your third step of play in a bin with 2X and no O will never happen.

The only way to answer this question is to look at the directional advantages offered by clustering pieces together.

What is needed is a cluster of pieces that for x number of X pieces, it is neccessary to place x+(sum 1 to 999) pieces to block all paths. This will allow for O blocking first path at 1 piece, 2nd path after 2 pieces, ...

The best strategy will involve X building a giant grid (each piece 1000 away from next one) and then trying to put pieces in the middle of the grids to slowly make more boxes. This will gradually increase the edge count that O must cover. However from what I have worked through, this will not reach the required excess edge count. Therefore X will not win.