Haha, you fool! You fell victim to one of the classic blunders, the most famous of which is “Never get involved in a land war in Asia,” but only slightly less well known is this: “Never go in a blog post expecting a game related article, because it may be a math related article!”
I am reading Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Mitzenmacher and Upfal.
The exercises section of Chapter 1 presents the following tictactoe question:
Not wanting to underutilize the $\KaTeX$ capabilities of my website, I decided to write up a solution. I did promise a math post, so the Probability comes first, and Computing second.
Math
This being a math post, let’s define a few sets to make the solution more concise.
Let the set of possible boards be $S$, and the set of boards where $\text{x}$ wins be $X$.
First, let’s determine the total number of possible boards, $S$. Note that this isn’t a typical tictactoe board, where the game stops after a single threeinarow.
There are $2$ outcomes for a coin flip (or $\text{x}$ vs $\text{o}$), and since each flip is independent, $9$ flips to determine the labels for the board result in $S = 2^9 = 512$ possible boards.
Secondly, let’s determine the number of boards where $\text{x}$ has one or more winning combinations, $X$. This is a much tougher problem, and to work out the solution I split the problem into cases depending on the number of $\text{x}$s on the board that result in a win.

$n(\text{x}) = 3:$ We can easily enumerate the cases here, resulting in a total of $8$.
✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗ 
$n(\text{x}) = 4:$ Since we cannot have two winning lines with only 4 $\text{x}$, we can think of the problem as the $n(\text{x}) = 3$ problem, but also choosing one of the 6 remaining cells to add another $\text{x}$, resulting in $8 \cdot 6 = 48$ cases.

$n(\text{x}) = 5:$ This requires a bit more enumeration. We can think of the number of winning cases as the difference between the total number of cases and the number of nonwinning cases, so
$\begin{align*} T &= \{ b \in S\ \ n(\text{x}) = 5\}\\ W &= \{ b \in X\ \ n(\text{x}) = 5\}\\ NW &= \{ b \notin X\ \ n(\text{x}) = 5\}\\ W &= T  NW \end{align*}$
The total number of boards with 5 of $\text{x}$ is $\binom{\ 9\ }{\ 5\ }$, as we are choosing 5 out of the 9 available cells to place an $\text{x}$ in. Therefore, $T = \binom{\ 9\ }{\ 5\ } = 126$.
There are 5 unique boards that are nonwinning.
✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗Of these 5 boards, the first two are unique across all 8 transformations (4 rotations and 4 reflections), while the other three only have 4 unique transformations due to the symmetry shown by the line.
$\begin{align*} NW &= 2 \cdot 8 + 3 \cdot 4 = 28\\ W &= 126  28 = 98 \end{align*}$

$n(\text{x}) = 6:$ There are only two boards with 6 $\text{x}$ that are nonwinning.
✗✗✗✗✗✗✗✗✗✗✗✗This leaves $\binom{\ 9\ }{\ 6\ }  2 = 84  2 = 82$ winning boards.

$n(\text{x}) = 7:$ All boards are winning, therefore there are $\binom{\ 9\ }{\ 7\ } = 36$ boards.

$n(\text{x}) = 8:$ All boards are winning, therefore there are $\binom{\ 9\ }{\ 8\ } = 9$ boards.

$n(\text{x}) = 9:$ All boards are winning, therefore there is $\binom{\ 9\ }{\ 9\ } = 1$ board.
Adding them all up, we get $8 + 48 + 98 + 82 + 36 + 9 + 1 = 282$ winning boards out of $512$ boards total. Now it should be smooth sailing to find the probability that $\text{x}$ wins, which is $282 / 512 = 0.5508 \approx 55.1\%$!
ono
Fixing The Mistake
In hindsight, seeing $\text{x}$ winning with $P > 0.5$ should raise some alarm bells, given that $\text{o}$ should win with the same probability. In another variant of this game, we could say that everyone wins and go home happy campers. Today though, there is only one spot on the podium for the luckiest tictactoer (ticertacertoer?).
Luckily, we did not do a whole bunch of work for nothing. From our winning boards, we need to prune ones that result in $\text{o}$ also winning. We go again!

$n(\text{x}) = 3:$ The new total for this is now $2$, as the remaining 6 boards result in a win for $\text{o}$.

$n(\text{x}) = 4:$ Similar to the previous section, the total is now $2 \cdot 6 = 12$.

$n(\text{x}) = 5:$ Here we have another kerfuffle. Because we previously calculated the number of winning boards by subtracting nonwinning boards from the total number of boards, we cannot simply subtract the winning boards that also result in an $\text{o}$ win.
The situation to notice here is that where $n(\text{x}) = 5$, $n(\text{o}) = 4$. We know that in all the $n(\text{x}) = 5$ boards, there are $48$ cases where $\text{o}$ wins, since $\text{win}(n(\text{o}) = 4) = \text{win}(n(\text{x}) = 4) = 48$.
Going back to the $n(\text{x}) = 5$ nonwinning boards:
✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗✗I’ve added the $\text{o}$s onto two boards, and highlighted their respective wins. Including possible transformations, this means that out of the nonwinning boards for $\text{x}$, there are $8 + 4 = 12$ winning boards for $\text{o}$.
Therefore, the number of winning boards for $\text{o}$ where $\text{x}$ is also winning is $48  12 = 36$. This gives the total number of actual wins, ie. wins for $\text{x}$ where $\text{o}$ does not win, as $98  36 = 62$ boards.

$n(\text{x}) = 6:$ We can utilize a similar, but simpler logic here. The two nonwinning boards for $\text{x}$:
✗✗✗✗✗✗✗✗✗✗✗✗is winning for $\text{o}$, which leaves the remaining $8  2 = 6$ winning boards for $\text{o}$ in the winning boards for $\text{x}$. So, using the total from the previous section, the new total is $82  6 = 76$ boards.

$n(\text{x}) \in \{7, 8, 9\}:$ Onto the home stretch! These cases make it impossible for $\text{o}$ to win, so the totals remain the same at $36, 9$, and $1$ respectively.
Our new and improved total is $2 + 12 + 62 + 76 + 36 + 9 + 1 = 198$ boards, giving a probability of $198 / 512 = 0.3867 \approx 38.7\%$. That’s much more reasonable!
I can fix that! Let’s write some code. Although I’m not confident my code’s any better than my math…
CS
I’ll be using Python today, for no reason other than I’ve been writing a lot of Rust lately and have been neglecting my first programming language. Let’s do it two slightly different ways, one by enumerating all possible tictactoe boards, and another by randomly generating boards and calculating a running win percentage.
Combinatorics
To generate all possible boards without duplication, we can use the handy itertools.product
.
My oxidized iron brain can’t help introducing more typesafety into the ducktyped snake language, so we’ll use enumerations.
import enum
import itertools
class Player(enum.Enum):
X = enum.auto()
O = enum.auto()
def __repr__(self):
return f"{self.name}"
PLAYERS = list(Player)
for board in itertools.product(PLAYERS, repeat=9):
# Prints:
# (X, X, X, X, X, X, X, X, X)
# (X, X, X, X, X, X, X, X, O)
# (X, X, X, X, X, X, X, O, X)
# (X, X, X, X, X, X, X, O, O)
# (X, X, X, X, X, X, O, X, X)
# ...
print(board)
We can then write a function to test for a win from a particular player:
def is_win_for(board: tuple[Player, ...], player: Player) > bool:
INDICES = (
((0, 0), (0, 1), (0, 2)),
((1, 0), (1, 1), (1, 2)),
((2, 0), (2, 1), (2, 2)),
((0, 0), (1, 0), (2, 0)),
((0, 1), (1, 1), (2, 1)),
((0, 2), (1, 2), (2, 2)),
((0, 0), (1, 1), (2, 2)),
((0, 2), (1, 1), (2, 0)),
)
for indices in INDICES:
if all(board[col * 3 + row] == player for (row, col) in indices):
return True
return False
Putting it all together:
total_boards = 0
wins = 0
PLAYERS = list(Player)
for board in itertools.product(PLAYERS, repeat=9):
print(board)
if is_win_for(board, Player.X) and not is_win_for(board, Player.O):
wins += 1
total_boards += 1
print(f"{wins}/{total_boards} = {wins / total_boards}")
And drumroll please…
$ python solver.py
98/512 = 0.38671875
Tough customer!
Simulation
Now, let’s do it more in the spirit of the question!
import random
total_boards = 0
wins = 0
PLAYERS = list(Player)
for i in range(10000001):
# Show incremental progress
if i % 1000000 == 0 and total_boards != 0:
print(f"{i} iterations: {wins}/{total_boards} = {wins / total_boards}")
# Our coin flip generated board
board = tuple(random.choice(PLAYERS) for _ in range(9))
if is_win_for(board, Player.X) and not is_win_for(board, Player.O):
wins += 1
total_boards += 1
Second drumroll please…
$ python solver.py
98/512 = 0.38671875
1000000 iterations: 387490/1000000 = 0.38749
2000000 iterations: 774802/2000000 = 0.387401
3000000 iterations: 1161301/3000000 = 0.3871003333333333
4000000 iterations: 1547835/4000000 = 0.38695875
5000000 iterations: 1934959/5000000 = 0.3869918
6000000 iterations: 2321540/6000000 = 0.38692333333333334
7000000 iterations: 2707923/7000000 = 0.38684614285714286
8000000 iterations: 3094900/8000000 = 0.3868625
9000000 iterations: 3482005/9000000 = 0.38688944444444445
10000000 iterations: 3868924/10000000 = 0.3868924
Close enough!
Conclusion
The math part of this post took a lot longer than the CS part of this post.
I will stuff my fingers into my ears and chalk that up to me not being a math major.
Please do let me know if there’s a more rigorous, less “proofbyenumeration” math solution.
I can be reached at feedback@<this website's domain name>
.
The Exercise For The Reader is part (b) of the same problem:
Eat your veggies, and I’ll see you in the next post.