somewhat like tic-tac-toe

[radosr]

Alice and Bob play a game on an infinite grid of unit squares. Alice starts and chooses a square and marks it with an X. Bob then chooses a square and marks it with an O. They continue playing until one of them has marked a row or a column of five consecutive squares with their symbol; this player is the winner. (Until Alice or Bob gets five in a row, the game is not won.) Can Alice, who goes first, always win?

 

[Tsotne]

What a question...The answer is no. I have played this game a lot when studding at a high school. One correction in rules: Diagonal fulfillment is also possible. If it does not matter, anyway, you can not always win regardless you start first or not.

 

[pruse]

you're right, the answer is no... in fact, Bob can always block her from winning.

this is one of those problems where you have to find the appropriate tiling. the one that works here is, divide the grid into 2x2 squares, then tile each 2x2 square with two dominoes, alternating horizontal and vertical tilings in a checkerboard pattern. then any group of 5 consecutive unit squares contains a complete domino, so all Bob has to do to block Alice is play an O in the same domino that Alice just played in: any 5 in a row that contain an X will also contain an O.

 

[Tsotne]

It can be possible in case of limited scenarios like 3x3 cells. Then it can be depended who starts. But in unlimited scenarios where you have to go on until you fill the column/row/diagonal with 5 X/O it is impossible to state one standard way which guarantees you winning if you start first.

 

[APalley]

It can be possible in case of limited scenarios like 3x3 cells. Then it can be depended who starts. But in unlimited scenarios where you have to go on until you fill the column/row/diagonal with 5 X/O it is impossible to state one standard way which guarantees you winning if you start first.

Even in a 3x3 case (i.e. TicTacToe) the player who goes first is not guaranteed a win. Just guaranteed not to lose.

 

[Tsotne]

Even in a 3x3 case (i.e. TicTacToe) the player who goes first is not guaranteed a win. Just guaranteed not to lose.

Yes that's what I meant. In 3x3 rational game you either win or match ends even.

 

[yongge]

Is it possible for us to come up with a strategy for Bob to block Alice if five X along the the diagonal line is considered a win?

you're right, the answer is no... in fact, Bob can always block her from winning.

this is one of those problems where you have to find the appropriate tiling. the one that works here is, divide the grid into 2x2 squares, then tile each 2x2 square with two dominoes, alternating horizontal and vertical tilings in a checkerboard pattern. then any group of 5 consecutive unit squares contains a complete domino, so all Bob has to do to block Alice is play an O in the same domino that Alice just played in: any 5 in a row that contain an X will also contain an O.

 

[MiloRambaldi]

Even in a 3x3 case (i.e. TicTacToe) the player who goes first is not guaranteed a win. Just guaranteed not to lose.

If you are still on the original topic of a game played on an infinite grid, then you are wrong if you mean getting 3 in a row/column. Then as Tsotne mentioned one player has a winning strategy:

Alice (1st player, or X) has an easy winning strategy: On her second move she places an X adjacent to the first so that either the row or column formed contains no O. For example,

... XX ....
... O

How about the game where 4 consective marks are needed to win?