Winning strategies in n-circular TicTacToe

Question

The game of N-Circular TicTacToe is defined as follows:

Informally, there is a circular board with $N$ empty slots where Alice and Bob place $X$'s and $O$'s. Whoever gets to place three consecutive symbols first wins.

More formally:

1. There are two players: Alice and Bob playing against each other.
2. The game progresses in turn, with Alice playing first.
3. In the beginning, Alice and Bob has two sets $A_0$ and $B_0$ with both empty and a set $S_0 = \{ 0, 1, 2, \cdots N-1\}$.
4. For every $i \geq 1$, the $(2i - 1)$th turn consists of Alice picking some number $a \in S_{2i-2}$ and placing it in $A_{2i-1}$, i.e, $A_{2i-1} = A_{2i-2} \cup \{a\}$ and setting $S_{2i-1} = S_{2i-2} \setminus \{a\}$, thus making $a$ unavailable. Similarly, every $(2i)$th turn consists of Bob picking some number $b \in S_{2i-1}$ and placing it in $B_{2i}$, i.e, $B_{2i} = B_{2i-1} \cup \{b\}$ and setting $S_{2i} = S_{2i-1} \setminus \{b\}$.
5. The game stops after the end of turn $j$ if:
   • There exists some $n \pmod N$ such that $n \pmod N, n+1 \pmod N, n+2 \pmod N$ are all in $A_j$. In this case, Alice wins.
   • There exists some $n \pmod N$ such that $n \pmod N, n+1 \pmod N, n+2 \pmod N$ are all in $B_j$. In this case, Bob wins.
   • Neither of the above hold, but $S_j = \phi$, in which case neither player wins.

Who'd have the winning strategy of this game? Also, how would the game evolve if the circularity was removed, i.e, we considered the numbers from $\{0, 1, \cdots (n-1)\}$ as is, instead of modulo $N$

I have no idea how to approach this problem without a lot of brute-force or case analysis. Any help is appreciated.

Answer 1

I claim that the strategy of proximity always leads to a draw:

Idea: If Alice places an X in position $j$, Bob chooses either $j+1$ or $j-1$. This is always necessary since two adjacent X with no proximate O lead to the victory of Alice. And it looks to be sufficient to draw.

Detail:

• First move: If Alice places an X in position $j$, Bob chooses $j+1$.

• Since the second move, I want to give Bob a precise strategy to choose between $k-1$ and $k+1$. I say that Bob chooses the side which has the closest X with no O's in between.

Answer 2

Like traditional Tic-Tac-Toe, this game will always result in a tie with perfect players. Here is why:

Player 2 (playing O's) can always prevent player 1 (playing X's) from winning using the strategy as described by Ivan: player 2 will always play in a square next to the square player 1 just played in. If both squares are still empty, then choose the side whose closest filled in square is an X. If both squares are already filled in, or if there is no side whose closest filled in square is an X, then player 2 is free to put an O anywhere else.

Using this strategy, it will be clear that when player 2 is done:

1. There cannot be two X's next to each other and with empty squares on both sides of them.

2. There cannot be any two X's with all empty squares in between

And that means that with this defensive strategy from player 2, player 1 can never win.

OK, but maybe player 2 can win? Well, player 1 knows that player 2 can at least force a draw, so the best thing player 1 can do is to play defensively as well, and try and keep player 2 from winning.

And indeed, player 1 can always keep player 2 from winning as well: for the first move, player 1 places an X anywhere, and player 2 is forced to play it right next to it (otherwise, it is clear player 1 will win). After that, player 1 will keep playing in the square close to an X leaving one empty square in between, and that will force player two to put an O between the two X's (to maybe see this a bit more clear: we can say without loss of generalization that the square player 1 put the first X in was square 2, and that player two put the first O in square 1. Player 1 will now [play in square 4, forcing player 2 to play in square 3)... and player 1 can simply repeat this strategy (player 1 will play next in 6, forcing player 1 to play in 5, then player 1 plays in square 8, forcing player 2 in square 7, etc. etc.) until the board is full.

So, since both players with perfect play can prevent the other one from winning, with perfect players this will always end up as a tie.