A Tic-Tac-Toe type game

Question

I found this interesting game with no name:

You have a 1x11 grid, like this.

The way you play is similar to Tic-Tac-Toe (aka Noughts and Crosses). Players take turns to place Xs and Os on the grid, but you can't put one letter directly adjacent to another letter. When one player doesn't have any squares that are valid for he or she to place a letter on, then their opponent wins.

So, my question is:

Is there a strategy that guarantees you to win? If so, what is it?

Answer 1

I think the answer is that the

First player can always guarantee a win.

Strategy

The first player can play the middle square first giving the configuration

_ _ _ _ _ X _ _ _ _ _

This effectively divides the board into two sets of four playable squares (on the left, and on the right of the initial X) as shown

_ _ _ _ | _ X _ | _ _ _ _

Then, whichever square O plays next will be in one of these sets and there will guaranteed to be at least one playable square for X in that set since a single move can eliminate at most three playable squares. Furthermore, any move of X in the same set of four is guaranteed to eliminate all remaining playable squares in that set.

X just needs to play as such twice.

Answer 2

Another strategy for

The first player to win

that works for any odd number of squares:

Play in the middle, as hexomino suggested:

_ _ _ _ _ X _ _ _ _ _

Now, whenever O plays in the left or right section of the board, play the square reflected on the opposite section, which is guaranteed to be available by symmetry. Since you won't run out of moves, your opponent is guaranteed to be the one to run out first.

Answer 3

I solved the entire game:

These are the winning pattern for the First move: O X X X O X O X X X O

where X means a First can force a win and O means Second can force a win.

Explanation:

So, I wanted to give a mathematical proof since I thought the game was equivalent to nim S(2,3), but then I realized the edge conditions make this statement untrue, it's still a nim variant but I don't know how to approach it. So instead here's an empirical proof:

user ffao already proved that any game with an odd number of positions(< 1) is a win for First (Proof A), so:
_ _ _ _ _ X _ _ _ _ _ = First wins

X _ _ _ _ _ _ _ _ _ = Second wins since the move leaves Second to play A

_ _ _ X _ _ _ _ _ _= Second wins with _ _ _ _ X _ O _ _ _ _ this leaves First with 2 A type games: they will win the first (where they start), and lose the second (where Second start, who will take the match)

What happens with even numbers of positions? 4 squares is an easy win for Second, and 6 is win for First = _ _ X _ _ _ ,

_ _ _ X _ _ _ _ _ _ _ = First wins since the move splits the game in a 2,6 games. If Second takes 2, First starts 6 and wins, if Second starts 6, they will take it, then First will win 2.

_ _ X _ _ _ _ _ _ _ _ = First wins as it leaves a 1,7 games, just like before if Second takes 1, First will start 7 and win; if Second start 7 they will take it and First will take 1 and win.

_ X _ _ _ _ _ _ _ _ _ = First wins This leaves Second to start an 8 game which can be shown to be a win for the second player (First). Second can reduce the match to a 5 game (which First will win due to A), a 6 game (which we have shown First will win), and a 2,3 game (which First will win with: _ _ _ O _ X _ _).

All the other games are mirrors.

Answer 4

If Player 1 can't force a win when the board is $n$ squares long, he can do it for $n+2$ or $n+3$ by filling any of the first or second squares from outside to inside respectively, turning it into an $n$-square-long game.

If 1 can force a win for $n$, then when it's $n+4$ squares long, he can fill the 3rd square to the right or left, leaving 2 "games" with $n$ and 1 square-long games. Then, Player 2 can't complete the latter for fear of leaving the former game to the other and allowing him to win. If he makes a "winning" first move in the larger game (one he can force a win with), 1 plays along to act the "loser". If 2 starts with a losing move in the larger game, 1 does the same.

If $n<4$, 1 wins.

If $n=4$, 2 wins.

If $n=5$, 1 wins.

If $n=6$, 1 can win by occupying the first or last square.

If $n=7$, 1 can win by occupying the second or second-to-last. Then 2 uses one of the four available squares, but loses.

11 mod 4 is 3, so it's a number allowing 1 to win (shortened due to symmetry - third to last square):

--------X--

-----O--X--

X----O--X--

(1 eventually wins)

or

--------X--

------O-X-- (O may want to play the loser)

-X----O-X--

(1 eventually wins)

or

--------X--

----O---X--

-X--O---X--

(1 eventually wins)

or

--------X--

---O----X--

---O-X--X--

(1 eventually wins)