36
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 18
    $\begingroup$ It turns out that the tic-tac-toe board was incredibly buoyant and Xavier and Oliver were picked up right after Kate Winslett. The metal X's and O's, sadly, were lost and never recovered. $\endgroup$
    – Hugh Meyers
    Commented Feb 26, 2016 at 10:03
  • 3
    $\begingroup$ This is a nice game. At last a way of making tic-tac-toe playable again! $\endgroup$
    – Gordon K
    Commented Feb 26, 2016 at 10:33
  • $\begingroup$ Very interesting. My gut feel is that the game will go on forever. Need to think about it some more. $\endgroup$
    – Trenin
    Commented Feb 26, 2016 at 13:32
  • $\begingroup$ Is this a mathematical answer? Because I don't know how to prove it, but I say no because no one player can hold opposite (diagonal) corners long enough to win. $\endgroup$
    – Raystafarian
    Commented Feb 26, 2016 at 18:19

1 Answer 1

Reset to default
31
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • $\begingroup$ So I will be saying "nice game there!" thanks! $\endgroup$
    – Raystafarian
    Commented Feb 26, 2016 at 18:34
  • $\begingroup$ wow nice. Basic strategy seems to be to set up a normal tic tac toe win that doesn't allow your opponent to tilt $\endgroup$
    – Slepz
    Commented Feb 26, 2016 at 18:36
  • $\begingroup$ Is there a way to change the starting position? Like if I wanted to run him against himself. $\endgroup$
    – Raystafarian
    Commented Feb 26, 2016 at 18:37
  • $\begingroup$ The jsfiddle doesn't have a way to change the starting position, no. This is because the decision tree has been pruned down only to moves that are necessary to guarantee a win from an empty board. If I allowed any starting position, then the tree would be about 100 times larger. You could generate whatever starting position you like using the Python script, however. (this may take some time, though - it executes in ~5 minutes on my machine) $\endgroup$
    – Kevin
    Commented Feb 26, 2016 at 18:42
  • $\begingroup$ I've found an issue with the interactive game. Play and pick "No, (1,1)". On next turn I wanted to do "Yes, (1,1)", but that isn't an option. No piece at (0,1), so it should be. $\endgroup$
    – Joel Rondeau
    Commented Feb 26, 2016 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.