12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So in other words, Gomoku with an infinite board? I'd assume neither, O will always be able to block 1000 before X can reach it (I think) but the game will never end for O to win... But I don't know how to prove this theory... $\endgroup$ – warspyking Nov 6 '14 at 1:32
  • $\begingroup$ @warspyking If O can block X indefinitely, it's a win for O even if the game doesn't end. Maybe it's easier to think of it as a draw instead and ask whether X has a forced win. $\endgroup$ – xnor Nov 6 '14 at 1:35
  • $\begingroup$ That would probably be best, do you actually know the answer? $\endgroup$ – warspyking Nov 6 '14 at 1:37
  • $\begingroup$ @warspyking Yes, and I think it's a fairly well-known puzzle, I don't remember where I hear it. $\endgroup$ – xnor Nov 6 '14 at 1:39
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your solution is incorrect. Had to put my explanation in an answer. $\endgroup$ – SeeMoreGain Nov 6 '14 at 4:16
  • 2
    $\begingroup$ The funny thing is: it also works on a 1-D board. $\endgroup$ – Florian F Nov 6 '14 at 13:12
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ MWilliams is correct. He wants to have at least $2^{1000}$ bins with one X and no Os. He can guarantee that with $2^{1001}$ turns by placing each piece in its own bin. Following your strategy, he will have that after $2^{1000}$ turns. Either way, after $2^{999}$ more turns he will have $2^{999}$ bins with two Xs and no Os and can keep going. $\endgroup$ – Ross Millikan Nov 6 '14 at 4:40
  • $\begingroup$ The math misses something. In the first step (when going to the left), you can divide the bin as you can have sufficient free space on the right. However then your piece is on the edge of that bin (and all subsequent bins that are divided). A piece on the edge of a bin needs different treatment to one in the middle of a bin. This is not taken into account in the analysis. $\endgroup$ – SeeMoreGain Nov 6 '14 at 4:46
  • $\begingroup$ Look at it from state analysis. Playing my blocking strategy, by definition, there is only 2 states for a pattern of pieces, an X with an O to the left of it (X played apart), and a pair of XX with an O either side (when X is played together). There is no other way to place an X in a 1 dimensional game. @MWilliams is incorrect. $\endgroup$ – SeeMoreGain Nov 6 '14 at 4:50
  • $\begingroup$ Or to explain it more visually, when you divide the boxes in the first round, you can do so O|X ... | (where | is box limits), but then on second round you place an X in any box and the result is either another placement left O|X...OX ...|, or a placement right O|XXO...|. There is no other way to define the box. Your math assumes any time an X is in a box, you are in a situation of |...X...| because the grid is sufficiently large (hence the assumption about only being able to block M/2 in second round) but this is a false assumption. $\endgroup$ – SeeMoreGain Nov 6 '14 at 5:07
  • 1
    $\begingroup$ @RossMillikan I'm willing to play 8 turns in the comments, but not 2^1000 turns. And no, I can't specify my turns ahead of time, because then the opponent could move in a bin before I place my piece there. (Although you are correct, I'd still get at least M/2 bins with an X and no O specifying my moves ahead of time, so it would still work.) $\endgroup$ – MWilliams Nov 6 '14 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.