How Good Are You At Guess Who?

Riddler Express

A tic-tac-toe board is filled at random with five Xs and four Os, one piece per slot. What is the probability that X wins, meaning there is at least one line of three Xs and no line of three Os?

Solution

There are $\binom{9}{5} = 126$ equally likely ways to choose which five slots hold the Xs (the Os fill the rest). X wins on those layouts where the X slots contain one of the eight lines and the O slots contain none. The placements are few enough to examine all of them, and counting the winners gives $$\Pr(\text{X wins}) = \frac{31}{63} \approx \boxed{0.492}.$$ Just under half, because filling five of nine squares very often makes a line for X while the four Os only occasionally line up.

The computation

Run through all $\binom{9}{5}$ choices of the X slots, and count those for which X has a line and O does not.

from itertools import combinations
from fractions import Fraction as F
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)]
has = lambda cells: any(all(p in cells for p in ln) for ln in lines)
wins = total = 0
for xs in combinations(range(9), 5):
    X = set(xs); O = set(range(9)) - X
    total += 1; wins += has(X) and not has(O)
print(F(wins, total))                        # 31/63

Riddler Classic

In “Guess Who,” each player secretly picks one of $N$ characters at random. Players alternate turns; on a turn you either guess the opponent’s character (win if right, lose if wrong) or ask a yes/no question to eliminate candidates, but if that leaves only one possibility you must still wait until your next turn to guess it. Both play optimally. How likely is the first player to win for $N=4$? For $N=24$? For $N=14$?

Solution

Describe a position by $(c,d)$: the player to move has narrowed the opponent to $c$ possibilities, and the opponent has narrowed the mover to $d$. Let $W(c,d)$ be the mover’s winning probability. The mover chooses between two actions. Guessing wins with probability $\tfrac1c$ and otherwise loses at once, worth $\tfrac1c$. Asking a question splits the $c$ candidates into groups of sizes $k$ and $c-k$; the true character lands in the first with probability $\tfrac{k}{c}$ (leaving $k$ candidates) or the second (leaving $c-k$), and then the opponent moves. So $$W(c,d) = \max\!\Big(\tfrac1c,\ \max_{1 \le k < c} A_k\Big), \quad\text{where}$$ $$A_k = \tfrac{k}{c}\big(1 - W(d,k)\big) + \tfrac{c-k}{c}\big(1 - W(d,c-k)\big),$$ with $W(1,d) = 1$ (a sole candidate is a sure guess). The game starts at $(N,N)$, so the first player wins with probability $W(N,N)$: $$\begin{aligned} N=4:&\ \boxed{\tfrac{9}{16}}, \qquad N=14:\ \boxed{\tfrac{55}{98}},\\[2pt] N=24:&\ \boxed{\tfrac{5}{9}}. \end{aligned}$$ The first-mover edge is real but modest, hovering near $0.56$, and it does not shrink steadily with $N$: the number-theoretic details of how $N$ can be split keep the advantage bouncing around just above one half.

The computation

Solve the recursion by value iteration over all states $(c,d)$ with $1 \le c,d \le N$, seeding each with the guess value $\tfrac1c$ and updating until the values settle.

from fractions import Fraction as F
def guess_who(N):
    W = {(c, d): F(1, c) for c in range(1, N+1) for d in range(1, N+1)}
    for _ in range(4 * N):
        nxt = {}
        for c in range(1, N+1):
            for d in range(1, N+1):
                if c == 1:
                    nxt[(c, d)] = F(1); continue
                best = F(1, c)
                for k in range(1, c):
                    v = F(k,c)*(1-W[(d,k)]) + F(c-k,c)*(1-W[(d,c-k)])
                    best = max(best, v)
                nxt[(c, d)] = best
        if nxt == W:
            break
        W = nxt
    return W[(N, N)]
print(guess_who(4), guess_who(14), guess_who(24))   # 9/16, 55/98, 5/9