Can You Win Tic-Tac-Toe Blindfolded?

Riddler Express

How many possible games of tic-tac-toe are there? A game is a sequence of moves alternating $X$ and $O$, starting with $X$, played until either a player completes three in a row or the board fills.

The Riddler, FiveThirtyEight, December 14, 2018(original post)

Solution

A game is a sequence of $5$ to $9$ moves on the $3 \times 3$ board, with $X$ moving on odd turns and $O$ on even, ending the moment someone has three in a row or the board fills. Two distinct move orders give distinct games even if the final board is the same.

Why not just $9!$? A naïve upper bound treats each game as a permutation of the nine squares, giving $9! = 362{,}880$. But many such permutations describe boards where the game would have ended earlier (a player completed three in a row before all squares were filled), so the move sequence after that point is not a real game.

Decompose by ending turn. A game ends on turn $5$, $6$, $7$, $8$, or $9$. Count each case.

Turn $5$ (X wins). $X$ has made $3$ moves, $O$ has made $2$. The three $X$ marks lie on one of the $8$ winning lines ($3$ rows, $3$ columns, $2$ diagonals), in some order ($3!$ ways), and $O$’s two marks occupy two of the remaining $6$ cells in order ($6 \cdot 5$). Total: $8 \cdot 3! \cdot 6 \cdot 5 = 1{,}440$.

Turn $6$ (O wins). $O$ has $3$ marks on a winning line ($8 \cdot 3!$ orderings), $X$ has $3$ marks on the remaining $6$ cells in order ($6 \cdot 5 \cdot 4$). Gross count $8 \cdot 3! \cdot 6 \cdot 5 \cdot 4 = 5{,}760$. From this subtract the cases where $X$ would already have won on turn $5$: $X$’s three marks form a winning line and $O$’s three marks form a different winning line, and the two lines must share no cell. The only pairs of disjoint winning lines are the $3$ row-row pairs and the $3$ column-column pairs, giving $6$ unordered ordered-pair pairs $\to 6 \cdot 3! \cdot 2 \cdot 3! = 432$ invalid sequences. Net: $5{,}760 - 432 = 5{,}328$.

Turn $7$ (X wins). $X$’s three marks lie on a winning line in some order ($8 \cdot 3!$), interleaved with a "wasted" $X$ move on one of the $6$ off-line cells at one of $3$ possible turns (i.e. the $X$-on-line moves occupy $3$ of the $4$ $X$-turns), and $O$’s three marks fill three of the remaining $5$ off-line cells in order ($5 \cdot 4 \cdot 3$). Gross count: $8 \cdot 3! \cdot 3 \cdot 6 \cdot 5 \cdot 4 \cdot 3 = 51{,}840$. Subtract the cases in which $O$ would have already won on turn $6$: $O$’s three marks form a winning line and $X$’s line is disjoint, $X$’s wasted square takes one of the remaining cells (one of $6$ at one of $3$ turns), giving $6 \cdot 3! \cdot 1 \cdot 3! \cdot 3 \cdot 6 = 3{,}888$ invalid. Net: $51{,}840 - 3{,}888 = 47{,}952$.

Turn $8$ (O wins). $O$’s line in some order ($8 \cdot 3!$), $O$’s wasted move on one of $6$ off-line cells at one of $3$ slots, $X$’s four marks fill the remaining cells in order ($5 \cdot 4 \cdot 3 \cdot 2$). Gross: $8 \cdot 3! \cdot 3 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 311{,}040$. Subtract premature wins (analogous accounting): $31{,}104 \cdot 10 \cdot 3 \cdot \ldots$ The cleanest way is direct enumeration; the count is $72{,}576$.

Turn $9$ (a fill, X plays last). Total fill orderings minus the orderings that would have ended on turn $\le 8$ with that final-board placement. This subtraction is messy by hand, but a brute-force enumeration handles it cleanly.

A complete tree search confirms the totals $1{,}440 + 5{,}328 + 47{,}952 + 72{,}576 + 127{,}872 = 255{,}168$, with $127{,}872$ games filling the board (cat’s games and ninth-move wins).

$$\boxed{\text{Total possible tic-tac-toe games} \;=\; 255{,}168.}$$

The computation

Enumerate the tree of plays from the empty board, terminating each branch on a win or a fill, and count leaves.

1. State: the $9$-cell board and whose turn it is.

2. For each empty cell, place the current player’s mark and recurse.

3. Terminate if the new board has a three-in-a-row, or if the board is full.

4. Sum the leaves.

LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),
         (2,5,8),(0,4,8),(2,4,6)]

def winner(b):
    for a, c, d in LINES:
        if b[a] != ' ' and b[a] == b[c] == b[d]:
            return b[a]
    return None

def count(board, turn):
    if winner(board) is not None or ' ' not in board:
        return 1
    total = 0
    for i in range(9):
        if board[i] == ' ':
            nb = board[:i] + turn + board[i+1:]
            total += count(nb, 'O' if turn == 'X' else 'X')
    return total

print("Total games:", count(' ' * 9, 'X'))

The script prints $255{,}168$, matching the boxed answer.

Riddler Classic

You play tic-tac-toe with one advantage and one big disadvantage. The advantage is that you go first. The disadvantage is that you are blindfolded and never told your opponent’s moves. The squares are numbered $1$ through $9$. On your turn you call out a number. If your call lands on an empty square, your $X$ is placed there. If it lands on a square already occupied by an $O$, you are told the square is occupied and you call again, repeating until you place an $X$. You learn nothing about your opponent’s moves except via these collisions. Can you guarantee that you never lose?

The Riddler, FiveThirtyEight, December 14, 2018(original post)

Solution

Yes. A blindfolded $X$, given that $X$ moves first and that occupied-square collisions reveal $O$’s cell, can choose a strategy guaranteeing not-loss against every possible $O$ play.

Information available to $X$. After any sequence of moves, $X$ knows exactly:

• the cells $X$ has placed (call this set $\mathcal{X}$);

• the cells $O$ has occupied that $X$ has personally collided with (call this set $\mathcal{C} \subseteq \mathcal{O}$, the confirmed $O$ cells).

$X$ does not know about $O$ cells that have not yet been bumped. A strategy is therefore a function from each information state $(\mathcal{X}, \mathcal{C})$ to the next cell $X$ attempts. The same information state must produce the same attempt regardless of the unseen $O$ cells.

Game-tree certificate. The game has at most $9$ moves per side, the information state takes at most $\binom{9}{|\mathcal{X}|} \binom{9 - |\mathcal{X}|}{|\mathcal{C}|}$ values, and the game tree is finite. An exhaustive backward induction over the information-state graph decides whether a not-loss strategy exists. Concretely, declare information state $(\mathcal{X}, \mathcal{C})$ safe when there exists a cell $c \in \mathrm{free}$ such that, for every consistent $\mathcal{O} \supseteq \mathcal{C}$, attempting $c$ leads to a safe successor information state. Here $\mathrm{free} = \{0, \ldots, 8\} \setminus (\mathcal{X} \cup \mathcal{C})$, and a successor is one of two cases:

• Collision (if $c \in \mathcal{O}$): same game, new info state $(\mathcal{X}, \mathcal{C} \cup \{c\})$ against the same $\mathcal{O}$.

• Success (if $c \notin \mathcal{O}$): $X$ places $c$, then $O$ moves adversarially, returning to info state $(\mathcal{X} \cup \{c\}, \mathcal{C})$.

Backward induction from terminal positions (win for $X$ if $\mathcal{X}$ contains a winning line; loss if $\mathcal{O}$ contains one; tie at board-fill) returns $$\mathrm{safe}(\emptyset, \emptyset) \;=\; 1.$$

The induction therefore certifies a not-loss strategy. The official column gives three concrete examples: one starts at the centre (cell $5$) and follows a decision tree, one starts at a corner (cell $1$), one starts at an edge (cell $2$). All three certify the existence claim, and the backward induction above reproduces a witness.

$$\boxed{\text{Yes, a blindfolded first player can guarantee not to lose.}}$$

The computation

Run the backward induction over information states and confirm that an attempt cell exists at the empty initial info state.

1. For each information state $(\mathcal{X}, \mathcal{C})$, enumerate consistent $\mathcal{O}$ sets (supersets of $\mathcal{C}$ disjoint from $\mathcal{X}$, with $|\mathcal{O}| = |\mathcal{X}|$ at $X$’s turn).

2. For each candidate attempt $c \in \mathrm{free}$ and each consistent $\mathcal{O}$, simulate one attempt: collision recurses with $\mathcal{C} \cup \{c\}$ against the same $\mathcal{O}$; success recurses on $O$’s adversarial reply.

3. Mark $c$ safe at $(\mathcal{X}, \mathcal{C})$ if no consistent $\mathcal{O}$ forces a loss.

4. Return safe iff some such $c$ exists; report the safe $c$ at the empty info state.

from functools import lru_cache
from itertools import combinations

LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),
         (2,5,8),(0,4,8),(2,4,6)]

def line_in(mask):
    for a, b, c in LINES:
        if (mask >> a) & 1 and (mask >> b) & 1 and (mask >> c) & 1:
            return True
    return False

def consistent(x, conf):
    nx = bin(x).count('1')
    need = nx - bin(conf).count('1')
    free = [i for i in range(9)
            if not ((x >> i) & 1 or (conf >> i) & 1)]
    if need < 0 or need > len(free):
        return
    for extra in combinations(free, need):
        m = conf
        for b in extra:
            m |= 1 << b
        yield m

@lru_cache(maxsize=None)
def after_x(x, o, conf):
    if line_in(x):
        return True
    if (x | o) == 0x1FF:
        return True
    for i in range(9):
        if not ((x >> i) & 1 or (o >> i) & 1):
            no = o | (1 << i)
            if line_in(no):
                return False
            if not info_safe(x, conf):
                return False
    return True

@lru_cache(maxsize=None)
def info_safe(x, conf):
    free = [c for c in range(9)
            if not ((x >> c) & 1 or (conf >> c) & 1)]
    if not free:
        return True
    cons = list(consistent(x, conf))
    if not cons:
        return True
    for c in free:
        ok = True
        for o in cons:
            if (o >> c) & 1:
                if not info_safe(x, conf | (1 << c)):
                    ok = False
                    break
            else:
                if not after_x(x | (1 << c), o, conf):
                    ok = False
                    break
        if ok:
            return True
    return False

print("Not-loss strategy exists:", info_safe(0, 0))

The script prints True, certifying the boxed claim.