# Random Tic Tac Toe

#### A FiveThirtyEight Riddler puzzle.

By Vamshi Jandhyala in mathematics Riddler

March 6, 2020

## 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: