[bonanova]

Every school boy or girl knows that with best play tic tac toe is a drawn game.

That is, getting three markers X or O in a row playing alternately on a 3x3 grid is impossible if your opponent plays correctly.

But suppose we extend the board to the plane - there is an unlimited number of squares on which to play.

Certainly then the first player can always achieve a row of 3 markers no matter how her opponent plays.

What is the largest number of markers in a row that first player can achieve in this case?

[Guest]

I'm assuming the rules are as follows:

Player 1 first chooses a space anywhere on the plane.

Player 2 will choose any space adjacent to Player 1's mark.

While Player 1 has the longest string (or Player 1 can build the longest string on their current turn):

- Player 1 always attempts to build the longest string possible on any given diagonal, row or column.

- Player 2 always attempts to block Player 1's progression by placing a mark at one end or the other of Player 1's open string.

While Player 2 has the longest string (or Player 2 can build the longest string on their current turn):

- Player roles reverse from above.

Given these rules, there does not appear to be an upper limit on the length of Player 1's, or 2's for that matter, string. This seems to be due to the ever increasing number of cells available and the inability for the opposing player to create a series of 'walls' around a string to prevent further growth. The players' strings will grow off the juxtaposed strings that have already been 'capped.'

That being said, there could be a strategy by Player 2 such that their marks are positioned in such a way as to build 'walls' a small enough distance away that it doesn't take too many turns, but far enough that Player 2 has enough time before Player 1 can reach those 'walls.'

There's just too much complex math involved for me to work it out and perform my duties, but there's my thoughts on the problem/solution.

[Guest]

let's say the first player places an X marker on a given square, then the second player should block the possible strings in all 8 directions.

that means s/he has to place 8 O markers, which will take him 8 turns. Therefore, s/he should skip 8 squares from the first X marker and place the first O.

Following that, the longest string of X markers can be 8 + 1 + 8 = 17 marks.

Edited September 1, 2011 by Fays

[Molly Mae]

let's say the first player places an X marker on a given square, then the second player should block the possible strings in all 8 directions.

that means s/he has to place 8 O markers, which will take him 8 turns. Therefore, s/he should skip 8 squares from the first X marker and place the first O.

Following that, the longest string of X markers can be 8 + 1 + 8 = 17 marks.

To be a finite number much smaller than anticipated. Assuming semi-optimal play (I'm playing against myself and can predict my own moves flawlessly....most of the time)--I very quickly encounter a position I've seen previously (including mirrors). By trying for his own longest string and not being concerned with how long O's string is, X seems to be able to reach 5 in-a-row, but allows O 6+ (but again, I assume that O is not trying for a long string and X is not trying to prevent him).

[superprismatic]

Having seen expert Go Moku games, which is essentially tic-tac-toe on a 19 by 19 grid where the object is to get 5 in a row, I suppose 6 is not possible to force for the first player and probably not 5 (or else Go Moku would not have survived as a game as long as it has). If it can be done in the entire plane and not on a 19 by 19 grid, the strategy would be complex indeed! So, I suspect the largest that the first player can be sure to be able to get in a row is 4.

[bushindo]

Every school boy or girl knows that with best play tic tac toe is a drawn game.

That is, getting three markers X or O in a row playing alternately on a 3x3 grid is impossible if your opponent plays correctly.

But suppose we extend the board to the plane - there is an unlimited number of squares on which to play.

Certainly then the first player can always achieve a row of 3 markers no matter how her opponent plays.

What is the largest number of markers in a row that first player can achieve in this case?

Here's an upper bound on the largest row length for which the first player can win

Here's a strategy which allows the second player to always draw if 9-consecutive markers are required to win,

Divide the infinite plane into identical 8x8 sections. Within each section, pair certain squares up with certain other squares. When player 1 plays a marker within a matched square, play the corresponding square. The map of the pairs (shown by the badly drawn ovals) are as follows

For instance, if player 1 plays a marker at row 1, column 1, which we denote as (1,1), then player 2 should play a marker at square (2,1). Likewise, if player 1 plays a square at (3,3), player 2 should play at (4,4).

There are four 2x2 squares that are left empty with no pairings within them. Those 2x2 squares are not important to the strategy. If player 1 plays any square within any of the 2x2 squares, simply choose another box within the same 2x2 square and play that. For instance, if player 1 plays in square (1,3), we can choose to play (1,4), (2,3), or (2,4).

The true limit on the largest row length is probably smaller than 9, however.

[Guest]

<p>

The way I see it, X would have to find a way to make two 3-in-a-rows in a single move in order to exceed 4 in a row. If he manages one triple, the O will cap it on one end, X will extend the triple to a quadruple, and O will cap it on the other end, ending the run. If he manages to get two triples going at once, the defender will have to pick one to cap, allowing X to complete a quad with nothing blocking either end. At that point, O caps one end, X makes it a 5-er, O caps the other end. I don't think that with perfect O play anything better is possible; not even sure that X could make it that far.

</p>

[Guest]

Here's a quick draft of what I was thinking.

x plays. o can only block one side. x plays on any of its 6 sides not obstructed on either side by O. O blocks one side of that line. X plays a third piece to make a V or L-shaped pattern with an O now blocking just one point on the line. So far: two lines, 2 blocks each. Then, O would block the end of one. If it's the one that's blocked on the other side, then X can manage a maximum line of 4. If O chooses to block another end so that the L shape is constricted on two sides (more optimal), then X would only achieve a maximum of 3 in a row.

Or, back to the 2 lines, 3 blocks from O, X can place its piece to make a 2x2 square. Here now, 4 lines 2 x long are started, with O sitting around in three spots. As X extends a line, it will be capped on each side in O's next turns. This allows a max of 2 (already there) + 2 (before O can block) X's in the row.

In this way, X may achieve a maximum of 4-in-a-row.