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

Question

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.

Answer 1

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.)

Answer 2

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.

Answer 3

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.