strategy - Titanic Tic-Tac-Toe

Xavier and Oliver were playing tic-tac-toe on the Titanic using a wooden board and metal X's and O's. As the stern of the ship sank lower and lower they found, to their annoyance, that the pieces began to slide from left to right. After some thought they decided to turn the situation to their advantage. They took turns holding the board level and added the following rules.

At the start of any player's turn he may allow the board to tilt causing all of the pieces to slide one square to the right. Any pieces leaving the 3x3 grid are removed. The player may then play a normal tic-tac-toe move.

A player may not play two successive moves on the same square.

A player may not allow the board to tilt if doing so will cause one or more of his opponent's pieces to be removed unless one or more of his own pieces will also be removed.

To clarify, a player may tilt the board if a) one or more of his own pieces is in the right hand column or b) if there are no pieces in the right hand column. Tilting only happens in the one direction: left to right. Tilting always takes place during a player's turn before he has placed his piece.

Assuming best play, can either player force a win?

Answer

The first player can always force a win.

I wrote this Python script to analyze the tree of possible game states reachable from an empty starting board. No matter what the second player does, the first player can make a move that eventually leads to a win in ten moves or less.

I took the tree and trimmed it down to only the optimal moves for the first player, plus all possible counter-moves for the second player. Excerpt:

["001", {"120": ["000", {"122": ["011", {"012": ["001", {}], "002": ["001", {}], "001": ["012", {}], "000": ["001", {}], "111": ["022", {}],

Each string represents a possible move one of the players could make. The first character of the string is "1" if the player shifts the board, and "0" otherwise. The second character is the X coordinate of the piece placed, and the third character is the Y coordinate. Each list contains two items: first, the first player's optimal move; second, a dictionary of the second player's possible counter-moves. Each dictionary is keyed by the possible move the second player could take, and each value is the two-item list representing the first player's optimal counter-counter-move to that counter-move. If the dictionary is empty, that means the game is over and the first player won.

I took this data and wrote a simple interactive game that you can play against the unbeatable computer.

---

edit: here is an interactive version with a better interface.