Titanicker Tic-Tac-Toe

Question

This is something of a follow-on to Hugh Meyer's enjoyable "Titanic Tic-Tac-Toe." Fortunately, our intrepid heroes Xavier and Oliver have wrested away a bit of wreckage that some fellow named Jack was holding on to and, as they sit in the icy North Atlantic, they pass the time by playing their favourite game.

Since they are now subject to the random undulations of the waves, they've had to change up their play again. Their rules are now as follows:

• Each player may, before placing a marker, shift the board in any direction, not just to the right.
• As before, the player may only shift a row or column provided that it either (a) removes one of his tokens or (b) does not remove any of his opponent's.
• As before, a player may not play on the same square in consecutive turns.

After some discussion and gentlemanly concession, Xavier and Oliver have added the following stipulation:

• The player may not make a play so as to return the board to state that it has previously been after his turn. If that is the only such move they can make, they lose.

To provide some mathematical clarity, if $S_i$ is the state of the board after the $i$ turns, then for $i \ne j$, $S_i = S_j$ only if $i \not\equiv j \mod 2$.

Their hope is that this will keep them from getting caught in a vicious cycle.

So, will Oliver win a game before the Carpathia arrives to save them? (Will Xavier?)

Answer 1

There can't be a draw because if the board is full, either you can move the board and get new places to play, or you can't because all positions you can go where already used, and you lose.

So the game always ends with a win for first or second player. So, as it is a finite two players game with no draw, there is exactly one player that has a winning strategy.

Now, you can remark that having a marker on the board is always better than not having one : it allows you to make a line, it prevents the other to make a line through it and it allows you to shift the board. Hence, the first player has a winning strategy, because if it hasn't, then he could play the strategy of the second player before him (it's the same argument than classical tic tac toe in fact).

Hence the first player to play has a winning strategy.

Now, knowing it exists doesn't give it, and it can be a very complex one...

Answer 2

there are 3^9 possible boards, (and not all of those are reachable) after at-most a few thousand moves someone will have won, either conventionally, or by snookering their opponent