4
$\begingroup$

Tic-tac-toe is a children's board game that's notorious for draws. It's easy to write a program for either player (X or O) that always draws the game. I would like to know how the outlook changes if both players play completely randomly. Ie, X places their first move uniformly among the 9 squares, then O does the same, and so on until someone wins. Intuitively, X should be better because they'll usually get more squares and first player advantage, but I'm not sure.

I really have no Idea, but I would really like to know. I am good at math, but not that good.

$\endgroup$
9
  • 1
    $\begingroup$ Who / what is $X$ in the problem? $\endgroup$ Mar 2, 2021 at 14:51
  • $\begingroup$ This looks tedious to work out analytically (though, of course, there are a lot of symmetries), but it shouldn't be hard to simulate. $\endgroup$
    – lulu
    Mar 2, 2021 at 14:53
  • 3
    $\begingroup$ X is the computer playing X. you know, one player is X and one is O. I shoud have mentioned that in the description. this my first question I have ever asked so I didn't expect it to be top quality anyway. $\endgroup$
    – a person
    Mar 2, 2021 at 15:08
  • $\begingroup$ You could go for finding $P(W_i)$ where $W_i$ denotes the event that at the $i$-th move a player arrives in a winning position. Then the probability that the starting player wins is $P(W_5)+P(W_7)+P(W_9)$. If I made no mistakes then $P(W_5)=\frac1{63}$, but quite a job to find the other probabilities. $\endgroup$
    – drhab
    Mar 2, 2021 at 15:25
  • 2
    $\begingroup$ If they toss for which computer makes the first random move, does any one have an edge ? $\endgroup$ Mar 2, 2021 at 15:30

3 Answers 3

19
$\begingroup$

We can find the exact answer by recursion. In all final states of the board, the probability is either $0$ or $1$. In every other state $S$, the probability is the average of the probabilities you get in states obtained by a single move from $S$. There are fewer than $3^9 = 19683$ board states, so a computer has no trouble with this.

Here is some Mathematica code implementing this (the board is a list of length $9$; I represent empty squares by 0, X's by 1, and O's by -1). I represent the final answer by a triple $(\Pr[\text{X wins}], \Pr[\text{O wins}], \Pr[\text{tie}])$.

(* lines[board] adds up the values along each winning line *)
lines[board_] := 
  Total /@ {board[[{1, 2, 3}]], board[[{4, 5, 6}]], board[[{7, 8, 9}]], 
    board[[{1, 4, 7}]], board[[{2, 5, 8}]], board[[{3, 6, 9}]], 
    board[[{1, 5, 9}]], board[[{3, 5, 7}]]};

pwin[board_] := pwin[board] =
  Which[Max[lines[board]] == 3, {1,0,0}, (* player 1 has won *)
   Min[lines[board]] == -3, {0,1,0}, (* player -1 has won *)
   FreeQ[board, 0], {0,0,1}, (* no more moves left: draw *)
   Total[board] == 0, (* player 1's turn *)
   Mean[pwin /@ ReplaceList[board, {x___, 0, y___} :> {x, 1, y}]],
   True, (* player -1's turn *)
   Mean[pwin /@ ReplaceList[board, {x___, 0, y___} :> {x, -1, y}]]]

pwin[{0,0,0,0,0,0,0,0,0}] (* outputs {737/1260, 121/420, 8/63} *)

It says that from an empty board, the probability of the first player winning is $\frac{737}{1260} \approx 0.5849$. Similar code says that the probability of a tie is $\frac{8}{63} \approx 0.127$ and the probability of the second player winning is $\frac{121}{420} \approx 0.2881$.

Another interesting result we can get in the same way: what if one player plays randomly, but the other player plays to maximize their chances of winning? (And when choosing between a draw and a loss, to avoid losing.) To find this, just replace one of the Means in the code above by a more intelligent choice of move.

  • If the first player plays to win, they win with probability $\frac{191}{192}$ and tie with probability $\frac1{192}$.
  • If the second player plays to win, they win with probability $\frac{887}{945}$, tie with probability $\frac{43}{945}$, and lose with probability $\frac1{63}$. (Why do they lose with any probability, when there's a strategy that guarantees a tie? Because if you're playing against a random opponent, sometimes taking a risk of losing gives you a higher chance of winning.)
$\endgroup$
1
  • $\begingroup$ also impressive, but again, I'm no code expert. I was expecting answers to come in after at least a day... $\endgroup$
    – a person
    Mar 2, 2021 at 15:49
13
$\begingroup$

There's a relatively nice way to do this by hand: pretend they play until the board is full, then grade it. There are $\binom 9 5$ such ending boards, most of which have a unique winner or no winner, and each multiple winner (ambiguous) case will have the same analysis.

So, first off are the multiple winner (I'll call these ambiguous) cases: These must be $2$ parallel horizontal lines of X's and O's, where the remaining row/column will have $3$ empty spots filled by $2$ X's and one $O$. So we get: $2$ orientations (row vs column), $3$ choices for the X row/column, $2$ remaining choices for the O row/column, and then $3$ ways to fill the remaining row/column. A total of $36$ such boards. In these cases, order of play matters. We'll return to them later.

Now, for the cases with X as the unique winner: Either we win on a diagonal, or a row/column. If a diagonal, then the other entries wont matter: $\binom 6 2$ possible ways to fill in a board with a winning diagonal, and $2$ possible winning diagonals. If a row/column, we have again $2$ choices for row/column, $3$ choices for which, and then $\binom 6 2$ choices for filling in the remaining squares.

We have double counted somewhat: we could win with both a diagonal and a row/column, both diagonals, we could win with both a row and a column, or we could have an ambiguous board. Fixing a particular row/column, there are $2$ ways to also get a diagonal. Likewise, fixing a particular row, there are $3$ ways to also get a column.

In total, we have:

$$2 \binom 6 2 -1 + 3 ( \binom 6 2 - 2) + 3 ( \binom 6 2 - 2 - 3) - 36 = 62$$

Where these are the diagonal wins, the column wins (remove the diagonal wins), the row wins (remove the diagonal or column wins), subtract the ambiguous boards.

The unambiguous O wins are much simpler - if O wins a row/column, then there must be a row/column that X wins (there aren't enough O's on the board to prevent it!). So we only have the diagonals:

$$2 (\binom 6 1) = 12$$

Finally, there are the remaining $16$ cases, all of which are draws. You can also verify these by hand, there are $8$ with X in the middle and $8$ without.

To finish, let's return to the 36 ambiguous cases. In each of these, there is a unique win for X and a unique win for O. So the question is just "does X make the 3 winning moves before O." Abstracting the moves to winning or not, based on if they've played one of the moves along their 3 in a row, there are only $\binom 4 3 \binom 5 3 = 40$ strategies to consider. Note that each ordering is equally likely, as our bots do not know if a move is good or not. So X wins in:

$$ \binom 4 3 + 3 (\binom 4 3 - 1) + 0 = 13$$

(based on if X wins on their third or fourth move, they cannot win on their fifth as O will have finished their line first.)

So the total probability that X wins is $$\big ( 62 + 36 \cdot (\frac {13}{40}) \big ) / \binom 9 5 = \frac{737}{1260}$$

Exactly as predicted in other answers.

$\endgroup$
2
  • 2
    $\begingroup$ Very nice! I thought of looking at final states, but then spotted the ambiguous cases, and was not brave enough to continue. $\endgroup$ Mar 2, 2021 at 18:43
  • $\begingroup$ Excellent answer +1. Too bad that there are close votes for this question. The way you have laid it out is so nice. $\endgroup$
    – Shailesh
    Mar 3, 2021 at 17:07
6
$\begingroup$

Well that was an enjoyable time-waster! I wrote a little program to play and, assuming 'X' is the player who goes first, the answer seems to be about 59%:

Draw / Win / Lose = 63384 / 292379 / 144237 out of 500000 equals 13% / 58% / 29%
Draw / Win / Lose = 63221 / 292618 / 144161 out of 500000 equals 13% / 59% / 29%
Draw / Win / Lose = 63383 / 292474 / 144143 out of 500000 equals 13% / 58% / 29% Draw / Win / Lose = 63224 / 292577 / 144199 out of 500000 equals 13% / 59% / 29%

Like others, I can't see an easy way to do this analytically.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for taking the time to write the code. (+1) I find the answers plausible though I must say it's hard even to come up with a good mental heuristic for them. $\endgroup$
    – lulu
    Mar 2, 2021 at 15:42
  • $\begingroup$ wow, this was posted less than an hour ago, and here is an answer. I have done some coding in the past, but I'm not able to do anything useful. nice job! $\endgroup$
    – a person
    Mar 2, 2021 at 15:46

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.