# if two computers are playing tic-tac-toe, but they are choosing their squares randomly, what is the chance for X to win?

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.

• Who / what is $X$ in the problem? Mar 2, 2021 at 14:51
• This looks tedious to work out analytically (though, of course, there are a lot of symmetries), but it shouldn't be hard to simulate.
– lulu
Mar 2, 2021 at 14:53
• 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. Mar 2, 2021 at 15:08
• 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. Mar 2, 2021 at 15:25
• If they toss for which computer makes the first random move, does any one have an edge ? Mar 2, 2021 at 15:30

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.)
• also impressive, but again, I'm no code expert. I was expecting answers to come in after at least a day... Mar 2, 2021 at 15:49

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.

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

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.

• 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.
– lulu
Mar 2, 2021 at 15:42
• 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! Mar 2, 2021 at 15:46