Random Tic-tac-toe

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 tic-tac-toer (ticer-tacer-toer?).

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 non-winning 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$ non-winning 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 non-winning 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 non-winning 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…

Combinatorics

To generate all possible boards without duplication, we can use the handy itertools.product. My oxidized iron brain can’t help introducing more type-safety into the duck-typed 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!