Random Tic Tac Toe

Problem

A local cafe has board games on a shelf, designed to keep kids (and some adults) entertained while they wait on their food. One of the games is a tic-tac-toe board, which comes with nine pieces that you and your opponent can place: five Xs and four Os.

When I took my two-year-old with me, he wasn’t particularly interested in the game itself, but rather in the placement of the pieces.

If he randomly places all nine pieces in the nine slots on the tic-tac-toe board (with one piece in each slot), what’s the probability that X wins? That is, what’s the probability that there will be at least one occurrence of three Xs in a row at the same time there are no occurrences of three Os in a row?

Solution

import altair as alt
from itertools import combinations
alt.renderers.enable('default')

def win(p, piece):
    rows_cols_diags, diag1, diag2 = [], [], []
    for i in range(3):
        rows_cols_diags.append([e[1] for e in filter(lambda x: x[0][0]==i, p)])
        rows_cols_diags.append([e[1] for e in filter(lambda x: x[0][1]==i, p)])
        diag1.append(next(filter(lambda x: x[0][0]==i and x[0][1]==i, p))[1])
        diag2.append(next(filter(lambda x: x[0][0]==i and x[0][1]==2-i, p))[1])
    rows_cols_diags.extend([diag1, diag2])
    return any(map(lambda x: x == [piece]*3, rows_cols_diags))

num_x = 5
piece_x, piece_o = "X", "O"
squares = set([(i,j) for i in range(3) for j in range(3)])
positions = []
for i, comb in enumerate(combinations(squares, num_x)):
    p = [(c, piece_x) for c in comb] + [(c, piece_o) for c in squares - set(comb)]
    if win(p, piece_x) and not win(p, piece_o):
        positions.append((p, "win"))
    else:
        positions.append((p, "loss"))
print("Number of winning positions:", len(list(filter(lambda x: x[1]=="win", positions))))

def pos_viz(pos):
    position, win_loss = pos
    if win_loss == "win":
        pos = alt.Data(values=[{'x':x, 'y':y, 'p':p, 'col':"green" if p==piece_x else "red"} 
                for (x,y),p in position])
    else:
        pos = alt.Data(values=[{'x':x, 'y':y, 'p':p, 'col':"grey"} for (x,y),p in position])
    grid = alt.Chart(pos).mark_rect(stroke="white", strokeWidth=1, opacity=0.6).encode(
        x = alt.X('x:O',axis=None),
        y = alt.Y('y:O',axis=None),
        color = alt.Color('col:N', scale=None),
    )
    pieces = grid.mark_text().encode(
        text =  'p:N',
        color = alt.value('black')
    )
    return grid + pieces

group = lambda flat, size: [flat[i:i+size] for i in range(0, len(flat), size)]

chart = alt.vconcat()
for row in group(sorted(positions, key = lambda k:k[1], reverse=True), 9):
    chart_row = alt.hconcat()
    for pos in row:
        chart_row |= pos_viz(pos)
    chart &= chart_row

chart

The probability that ‘X’ wins is 0.4924.

Here are all the winning positions highlighted in green: