6
$\begingroup$

In an SMBC comic published on 20 June 2022, Zach Weinersmith proposes the following variant of tic-tac-toe:

  • Play consists of a number of rounds
  • At the start of each round, each player rolls a d6 in secret
    • A player rolling 1 or 2 is set the goal of winning the round (which in this game means 'making a line of three')
    • A player rolling 3 or 4 is set the goal of drawing the round (neither player makes a line of three)
    • A player rolling 5 or 6 is set the goal of losing the round (they do not make a line of three but their opponent does)
  • Board and play are as regular tic-tac-toe, with starting player alternating between rounds; except that play continues until all nine squares are filled, no matter if a line of three is made
  • After the end of the play, a player who achieved their goal scores 1 point; a player who did not achieve their goal scores 0 points
  • First player to 5 points wins; if both players reach 5 points simultaneously, play continues, and the overall winner is whoever is first to take a lead

So, a player is trying to both achieve their goal (known) and to prevent opponent's goal (can only be inferred). Formally, they maximize: their score - opponent's score.

What does best play look like?

$\endgroup$
12
  • 1
    $\begingroup$ Two corrections: 1."once the board is filled" - players play all 9 turns in a round. Only then they reveal their secret mission and calculate scores. 2. if both get to 5 points then then they play "golden goal" the next player to have higher score wins the game. $\endgroup$
    – Cohensius
    Jun 22, 2022 at 12:08
  • $\begingroup$ Ah, I misinterpreted the tie-breaker, thanks. When we continue to fill the board, does the presence of both O lines and X lines count as a 'win' for both players, or only the first to be made? $\endgroup$
    – AakashM
    Jun 22, 2022 at 12:13
  • 1
    $\begingroup$ We only exam wins/loses/draws when the round ends, after 9 turns. both players can win/lose/draw or more importantly: each player can get her goal or not. So the score at each round is one of the four options: (0,0), (0,1), (1,0), (1,1) $\endgroup$
    – Cohensius
    Jun 22, 2022 at 12:32
  • $\begingroup$ @Cohensius I think I've got all that in now $\endgroup$
    – AakashM
    Jun 22, 2022 at 12:39
  • 2
    $\begingroup$ see the twitter debate at: twitter.com/ZachWeiner/status/1538935850339377154 $\endgroup$
    – Cohensius
    Jun 22, 2022 at 12:57

2 Answers 2

3
$\begingroup$

I spent entirely too much time thinking about this when it was posted, but I still only have a partial answer.

Also, this whole answer (and all of its underlying thoughts) were assuming that the game ended when one player made a 3-in-a-row, so it is merely "related to" the puzzle posed and wouldn't be an answer even if completed. (I built this answer from a different understanding of the game the comic posed than the author of this puzzle)

I believe that one player (likely O) has a slight advantage in each round (average of +1/6). However, I had to make some simplifications in order to arrive at this conclusion, which could have been wrong.

The simplified game

Consider the following simplified game: In each round, there are three possible outcomes: Either X wins, or O wins, or a draw. Each player knows their own objective and do not know their opponent's. Rather than X's and O's, I'll call the players "First player" and "Second player," because an "X win" is not necessarily the same as first player achieving their objective.

In the first move, first player chooses one outcome to eliminate. In the second move, second player chooses one of the remaining two outcomes to achieve. Players who had their goal equal to second player's final choice win 1 point.

Simplified Game Strategy

First player chooses any outcome that is not their own objective. If second player's objective remains, they choose that. Otherwise, they choose randomly.

Simplified Game Scores

  • If both players had the same objective (1/3), both players win.
  • Otherwise, the there are 3 objectives, 1 held by each player and 1 "dud" (2/3)
    • If first player eliminates the dud (1/2) then second player wins.
    • If first player eliminates second player's objective (1/2)
      • And second player chooses the dud (1/2) then it's a draw
      • And second player chooses first player's objective (1/2) then first player wins.

P(Both players win) = 1/3
P(second player wins alone) = (2/3) * (1/2) = 1/3
P(first player wins alone) = (2/3) * (1/2) * (1/2) = 1/6
P(Neither player wins) = (2/3) * (1/2) * (1/2) = 1/6

First player scores an expected value of (1/3) + (1/6) = (1/2) per game.
Second player scores an expected value of (1/3) + (1/3) = (2/3) per game.

Is the simplified game equivalent?

That is the big question. I believe it is, but I haven't proven so. For The Simplified Game to be equivalent to Hidden Information Tic-Tac-Toe, then it must also be true that

  1. No player must can force any single outcome unilaterally.
  2. After some number of passing moves, one player must be forced to eliminate one of the three outcomes. (That player is "First player")
  3. After that move, the other player ("Second player") must be able to choose from the two remaining outcomes.

A "passing move" is a move which

  • Does not eliminate any outcomes
  • Does not put the board into a state where your opponent can force a single outcome.
  • Does not reveal any information to the opponent.

I believe that there are 4 passing moves, after which Incomplete Information Tic Tac Toe reduces to the Simplified Game with X in the role of first player.

Proof: X Must not be able to force any single outcome from an empty board

In order for X playing the Simplified Game to be an optimal strategy, it must not be possible for X to simply force their objective. I'll break this down by cases.

Case 1: X cannot force X to win

Already solved. Tic-tac-toe is known to be a draw assuming perfect play.

Case 2: X cannot force O to win

Case 2a: If X plays off center, O can respond by playing opposite X. If the response completes a 3-in-a-row for O, then by symmetry the previous move must have completed a 3-in-a-row for X, thereby ending the game.

Case 2b: If X plays in the center, O will always have options to avoid creating a 3-in-a-row. The strategy is to fill the side spaces first. If X allows O to take 3 side spaces, a 3-in-a-row is impossible, therefore X's first two non-center moves must also be side spaces. O then chooses a corner that is not adjacent to both of their side spaces (it can be adjacent to one, but not both). Regardless of which corner X takes, O will always have a choice of 2 corners left, one of which will not form a 3-in-a-row.

Case 3: X cannot force a draw

If X ever creates two symbols in a row, O can place two symbols such that whomever takes the remaining space wins, preventing a draw. A demonstration of this strategy is left as an exercise to the reader. (I have pages and pages of proof-by-exhaustion of this in handwritten notes and I'm convinced that it works, but I'd appreciate someone checking my work. I don't have any elegant strategy here).

The strategy

Because second-player has the advantage in The Simplified Game, each player will try to play as many "passing moves" as they can to force the other player to take first-player's role. After that, players choose strategies based on their objective and random chance.

Passing Moves

The longest sequence of passing moves I have found is 4, with the following line.

x1: Center
o1: Any Corner
x2: Corner opposite o1
o2: Either remaining corner

Outcome elimination moves

After these passing moves, X must choose an outcome to eliminate.

Eliminate O Win

x3: Side between o1 and o2. Then play tic-tac-toe normally.

If O wants to draw here, they can respond by playing tic-tac-toe themselves.
If O wants X to win, they can leave the side opposite x3 empty. X will be forced to fill it on their final move, completing a row with x5,x1,x3.

Eliminate Draw

x3: Side opposite the empty space between o1 and o2.

If O wants to win, they can fill that space for a win (o1, o3, o2). If O leaves it vacant, X will be forced to take it on x5 (x5, x1, x3).

Eliminate X Win... partially

If X plays in any of the three remaining spaces and then continues to choose not to complete their own rows, they can force O to either tie or win. However, if O chooses not to take the win, X can go back on their move and claim the win themselves rather than playing for a draw.

This technically allows X to find out that O's objective is not the O win, however, the cost of making this discovery was putting O in a position where they could have forced an O win to begin with. There is no set of objectives where doubling back like this is a good strategy for X, so I believe it still fits the Simplified Game model.

Limitations of this answer

This remains a partial answer.

In particular, I have not proven that there is no strategy for X better than the series of passing moves I posted. If X has a single passing move, or a series of 2 passing moves that does not leave a passing move to O, playing so would reverse their roles in The Simplified Game, which is a better outcome for X.

I also have not proven that there is no strategy for O better than to respond to X's passing moves with passing moves of their own. It may be possible for O to force a single outcome at some point in that sequence.

In both of these limitations, I've played a few lines out in pencil-and-paper and haven't come up with any better moves, but there's no guarantee I haven't missed something.

$\endgroup$
0
$\begingroup$

Some thoughts at first glance:

Tic tac toe is a solved game and you cannot force a win. The only way you can actually win is if your opponent is trying to lose. So if your goal is to win...
... and your opponent's goal is to win, you draw and both get 0.
... and your opponent's goal is to draw, you draw. You get 0 and they get 1.
... and your opponent's goal is to lose, you win and you both get 1.

So really there's no upside if your goal is to win - at best you and your opponent score the same number of points.

Similarly I suspect the only way you can lose on purpose is if your opponent is trying to win, which leads to the same dilemma. The best you can do, if your goal is to lose, is to keep pace with your opponent.

The best situation is for your goal to be a draw, and hope your opponent is trying to win or lose. Player 1 can easily force a draw (by going in the center and then mirroring all of Player 2's moves). Pretty sure player 2 can also force a draw.

So basically the game boils down to the luck of the dice - you hope you roll more 3s and 4s than your opponent.

$\endgroup$
5
  • $\begingroup$ I'm not sure it's that simple. If the first player takes the center space I think its possible for the second player to force the first player to win. Likewise, if the first player doesn't take the center space it's possible for the second player to take the center, and then force the first player to win provided the first player thinks the second player is playing to win themselves (or conversely, the second player can win outright if the first player thinks they are playing to lose). $\endgroup$ Jun 29, 2022 at 21:30
  • $\begingroup$ I haven't done an exhaustive search of the game states though, this is just me thinking through a couple possible ways the games could go so I could easily be wrong on this. $\endgroup$ Jun 29, 2022 at 21:31
  • $\begingroup$ "If the first player takes the center space I think its possible for the second player to force the first player to win." He can't possibly, wherever the 2nd player goes the 1st player can go in the square opposite the center. I also haven't done an exhaustive search, it would be easy enough to do so I probably will tomorrow if no one beats me to it, but I feel reasonably sure that either player can always force a draw if they want to. $\endgroup$
    – SQLnoob
    Jun 29, 2022 at 21:33
  • 1
    $\begingroup$ "He can't possibly, wherever the 2nd player goes the 1st player can go in the square opposite the center." That's fair, I do need to think about this more. However, it seems to me that is also a situation that depends on what the 1st player thinks the 2nd player wants. Imagine after turn 4 the second player has the upper left, and center left while the 1st player has the center and the bottom right. Where does 1st player (X in this case) go to draw? If they think the 2nd player needs to win they need to block, but then they can be forced to take the entire bottom row if 2nd needs to lose. $\endgroup$ Jun 29, 2022 at 21:43
  • $\begingroup$ Ah... hm, that's an interesting position. I guess I will have to think about it some more, too. $\endgroup$
    – SQLnoob
    Jun 29, 2022 at 21:49

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.