36

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?

manshu
  • 6,304
  • 20
  • 56
Hugh Meyers
  • 23,712
  • 1
  • 52
  • 171
  • 18
    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. – Hugh Meyers Feb 26 '16 at 10:03
  • 3
    This is a nice game. At last a way of making tic-tac-toe playable again! – Gordon K Feb 26 '16 at 10:33
  • Very interesting. My gut feel is that the game will go on forever. Need to think about it some more. – Trenin Feb 26 '16 at 13:32
  • 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. – Raystafarian Feb 26 '16 at 18:19

1 Answers1

31

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.

Kevin
  • 6,449
  • 1
  • 31
  • 30
  • So I will be saying "nice game there!" thanks! – Raystafarian Feb 26 '16 at 18:34
  • wow nice. Basic strategy seems to be to set up a normal tic tac toe win that doesn't allow your opponent to tilt – Slepz Feb 26 '16 at 18:36
  • Is there a way to change the starting position? Like if I wanted to run him against himself. – Raystafarian Feb 26 '16 at 18:37
  • 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) – Kevin Feb 26 '16 at 18:42
  • 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. – Joel Rondeau Feb 26 '16 at 18:47
  • @JoelRondeau, interesting. On my machine, the progression of moves goes: X picks (no, 0,1). O picks (no, 1,1). X picks (yes, 0,0). This means that (1,1) is occupied by the X that was placed on the first turn and subsequently tilted right once into (1,1). so it makes sense that O can't choose (1,1) as its second move. Is that inconsistent with what you're seeing? Maybe it's a browser-dependent bug... – Kevin Feb 26 '16 at 18:55
  • @Kevin Actually, my mistake. (1,1) is occupied by the X, but if O did a Yes (1,1), it would no longer be occupied. However, O did No, (1,1) on the first turn and the rules state he can't place something at (1,1) 2 turns in a row whether it is open or not. – Joel Rondeau Feb 26 '16 at 18:58
  • Well done! I have never programmed in Python but I have convinced myself that this does indeed constitute a solution. And thanks for the online version. I thought of this on the train this morning and couldn't work it all out in my head. Nice to be able to actually play it. – Hugh Meyers Feb 26 '16 at 20:41
  • I was working on exactly the same approach but went to a friend's birthday party. one up :) – Jonathan Allan Feb 27 '16 at 04:25
  • The newer version shifts after the move rather than before. – Jonathan Allan Apr 09 '16 at 02:15
  • I've been wasting like 30 minutes trying to beat your game... Congrats. – Nico May 31 '16 at 13:23