13
$\begingroup$

This puzzle is part of the Monthly Topic Challenge #1: Restricted Title: xkcd 1xxx and is based on https://xkcd.com/1801/.


Protip: If you ever need to defeat me, just give me two very similar options and unlimited internet access.

Two people are playing tic-tac-toe, and it is common knowledge that both players are susceptible to a peculiar form of decision paralysis.

At the start of a player's turn, if they can play exactly two "normally" winning moves, then that player becomes unable to make any move and immediately loses the game.

A "normally" winning move is one that would lead to a win if the remainder of the game were played perfectly between two "normal" players not susceptible to decision paralysis.


For example, if it is X's turn in the following position, there are exactly two normally winning moves, marked with asterisks.

X O X
O *
*

Overcome with decision paralysis, X immediately declares, "I lost the game," and O wins.


With both players knowing that they can win by either scoring three-in-a-row or paralyzing their opponent, which player has a winning strategy?

Disclaimer: The creator of this puzzle is not liable for any harm caused while playing decision paralysis tic-tac-toe. Please play responsibly.

$\endgroup$
1
  • $\begingroup$ 1801 eh? Too bad there's no 832 for that one... $\endgroup$ Jul 19 at 11:48

2 Answers 2

5
$\begingroup$

The one with the winning strategy is quite surprisingly

X

First, let us note that

if X starts anywhere else than the center, O wins on their first move like this

 |X   *|     |* X  |
 |     |     |O *  |
 |*   O|     |     |

First options

When X starts in the center, O has two options, corner, which gives X zero winning moves or middle, which gives X six winning moves

 |O    |     |* O *|
 |  X  |     |* X *|
 |     |     |*   *|

Case 1

If O goes for the corner, X wins like this

 |O    |    |O   X|    |O X X|
 |  X  | -> |  X  | -> |* X  |
 |     |    |O    |    |O *  |

Case 2

So O should go for the middle. Then, if X goes anywhere else than one of the more distant corners, O wins immediately like this

 |  O  |     |X O  |     |* O  |
 |O X  |     |* X  |     |X X O|
 |* X *|     |*   O|     |*    |

Case 2.1

So X will go for one of the bottom corners. Then the game will end like this

 |  O  |    |  O O|    |* O O|
 |  X  | -> |  X  | -> |  X  |
 |     |    |X    |    |X X *|

$\endgroup$
5
  • $\begingroup$ Can you explain how X starting in an edge space is a loss for X? If your argument that O can win by playing in an adjacent edge space is valid, then O has exactly two such spaces they can play in, which would make this position a loss for O by decision paralysis. $\endgroup$
    – fljx
    Jul 19 at 20:28
  • 2
    $\begingroup$ @fljx From the rules: A "normally" winning move is one that would lead to a win if the remainder of the game were played perfectly between two "normal" players not susceptible to decision paralysis. O playing in an adjacent edge space is not a "normal" winning move but it is a winning move in that the two cells marked with an asterisk are the (only) two "normal" winning moves for X after that. $\endgroup$
    – user39583
    Jul 19 at 21:32
  • 1
    $\begingroup$ I hate to be that guy, but how do you use your notation? @user39583 $\endgroup$
    – yogazefish
    Jul 22 at 1:42
  • $\begingroup$ X and O can both win, it depends who plays first. $\endgroup$
    – Florian F
    Jul 22 at 23:24
  • $\begingroup$ @FlorianF or who plays worst. Thanks for the edit, looks much prettier now! $\endgroup$
    – user39583
    Jul 23 at 7:43
-1
$\begingroup$

Resolution

O wins

Edge

If X goes on an edge, O can go on an edge diagonal from X's edge and O wins from decision paralysis. * X _ [new line]O * _ [new line]_ _ _ [new line]The underscores are blank spaces and the asterisks are where X can go to double trap O. Since there are two ways to double trap, X loses.

Corner

If X goes in a corner, O can go in the opposite corner. Now, if X goes in any of the other 2 corners, he can double trap O next turn. X loses due to decision paralysis. X _ * [new line] _ _ _ [new line]* _ O. The underscores are blank spaces and the asterisks are where X can go to double trap O. Since there are two ways to double trap, X loses.)

Center

If X goes in the center, O can go in any corner and win. Once O goes into the corner, X has 4 options. I am going to use the algebraic notation for this. X is in B2. O is in A1. If X goes in A2, O can go in C1. Now, if X goes in C2 or B1, X wins. Since there are two ways to win, X loses. If X goes in A3, O can go in C1. If X goes anywhere but B1, he loses. O can go in C3. If X goes in B3 or C2, he wins. Since there are two ways to win, X loses. If X goes in B3, C can go in A3. Now, if X goes in B1 or A2, he wins. Since there are two ways to win, X loses. If X goes in C3, O can go in B1. Now, if X goes anywhere but C1, he loses. Now, if O goes in A2, X can win by going in A3 or C2. Since there are two ways to win, X loses.

$\endgroup$
4
  • $\begingroup$ I wasn't totally sure how to use the commands for spoilers and graphs so if a mod could help me out, that would be gr8 $\endgroup$
    – yogazefish
    Jul 20 at 5:35
  • 3
    $\begingroup$ In the last case there are six winning moves for X (any of the corners work as well) and the rules state that there have to be exactly two for the decision paralysis to kick in. $\endgroup$
    – user39583
    Jul 20 at 6:06
  • $\begingroup$ @user39583 thx. I patched it up $\endgroup$
    – yogazefish
    Jul 22 at 1:40
  • 1
    $\begingroup$ B2, A1, A3, C1 does not mean X has to go to B1. It would in a normal game, but if instead X goes to A2, O will have exactly two winning moves, B1 and C2, and will lose from decision paralysis (see the case 1 from my answer above). I'm not sure what you meant by your question about the notation, but you can get a new line inside spoiler blocks by adding two empty spaces at the end of the row and then starting a new row. The game boards in my answer are inside pre-formatted text blocks (<pre>board</pre>). $\endgroup$
    – user39583
    Jul 22 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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