5
$\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$ Commented 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
    Commented 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
    Commented 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
    Commented 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$ Commented Mar 2, 2021 at 15:30

3 Answers 3

20
$\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
    Commented Mar 2, 2021 at 15:49
14
$\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$ Commented 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
    Commented Mar 3, 2021 at 17:07
7
$\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
    Commented 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
    Commented Mar 2, 2021 at 15:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .