## 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
'default')
alt.renderers.enable(
def win(p, piece):
= [], [], []
rows_cols_diags, diag1, diag2 for i in range(3):
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)])
rows_cols_diags.append([e[next(filter(lambda x: x[0][0]==i and x[0][1]==i, p))[1])
diag1.append(next(filter(lambda x: x[0][0]==i and x[0][1]==2-i, p))[1])
diag2.append(
rows_cols_diags.extend([diag1, diag2])return any(map(lambda x: x == [piece]*3, rows_cols_diags))
= 5
num_x = "X", "O"
piece_x, piece_o = set([(i,j) for i in range(3) for j in range(3)])
squares = []
positions for i, comb in enumerate(combinations(squares, num_x)):
= [(c, piece_x) for c in comb] + [(c, piece_o) for c in squares - set(comb)]
p if win(p, piece_x) and not win(p, piece_o):
"win"))
positions.append((p, else:
"loss"))
positions.append((p, print("Number of winning positions:", len(list(filter(lambda x: x[1]=="win", positions))))
def pos_viz(pos):
= pos
position, win_loss if win_loss == "win":
= alt.Data(values=[{'x':x, 'y':y, 'p':p, 'col':"green" if p==piece_x else "red"}
pos for (x,y),p in position])
else:
= alt.Data(values=[{'x':x, 'y':y, 'p':p, 'col':"grey"} for (x,y),p in position])
pos = alt.Chart(pos).mark_rect(stroke="white", strokeWidth=1, opacity=0.6).encode(
grid = alt.X('x:O',axis=None),
x = alt.Y('y:O',axis=None),
y = alt.Color('col:N', scale=None),
color
)= grid.mark_text().encode(
pieces = 'p:N',
text = alt.value('black')
color
)return grid + pieces
= lambda flat, size: [flat[i:i+size] for i in range(0, len(flat), size)]
group
= alt.vconcat()
chart for row in group(sorted(positions, key = lambda k:k[1], reverse=True), 9):
= alt.hconcat()
chart_row for pos in row:
|= pos_viz(pos)
chart_row &= chart_row
chart
chart
```

The probability that ‘X’ wins is *0.4924*.

Here are all the winning positions highlighted in green: