What’s The Optimal Way To Play HORSE?

Riddler Express

In the Riddler Official Football League, every reader-coach submits one penalty-kick target and one area to defend. The goal is split into two rows and three columns ($6$ regions); a goalie who guesses the shooter’s region saves it, and otherwise an undefended shot scores with a region-dependent probability (corners riskier than the centre). All coaches’ shooters and goalies are simulated against each other, and the most net goals wins. What should you submit?

The Riddler, FiveThirtyEight, July 12, 2019(original post)

Status

This is a participatory contest, scored against the field of more than $1{,}520$ other submissions, not a problem with a derivable answer. Its winning play depends on what everyone else submits: the champion aimed at the upper-middle ($90\%$) region and defended the lower-middle (the one region where an undefended shot is certain to score), precisely because he guessed the crowd would over-defend the lower-middle and leave the upper-middle juicy. That is a read on the population of opponents, not an optimum.

Because the answer is contingent on the field rather than derivable, the Express is deferred from the worked-solution standard, in the same category as the Battle for Riddler Nation and the ROFL contest itself. (There is a genuine two-player game-theoretic version, the mixed Nash equilibrium of the $6 \times 6$ shooter-versus-goalie zero-sum game, but the puzzle as posed asks for a contest submission, not that equilibrium.)

Riddler Classic

Alice and Bob play HORSE. Alice shoots first from anywhere; if she makes it, Bob must attempt the same shot, getting a letter if he misses. If Alice misses, she gets no letter but Bob takes over choosing shots. Each missed obligated shot is a letter in H-O-R-S-E; first to spell HORSE loses. Both are equally skilled and can pick a shot of any make-probability they like. If both play optimally, what shot should Alice take first?

The Riddler, FiveThirtyEight, July 12, 2019(original post)

Solution

Alice’s only edge is that she shoots first, like the server in volleyball: only the shooter can hand the opponent a letter. The question is what make-probability $X$ best protects that edge.

Suppose Alice shoots with make-probability $X$. Three things can happen on her turn. She misses (probability $1-X$) and loses the “serve” to Bob, handing him the initiative. She makes it and Bob then misses the copy (probability $X(1-X)$), giving Bob a letter while Alice keeps the serve. Or she makes it and Bob matches (probability $X^2$), returning to the start with nothing changed. The only outcomes that matter are the first two: losing the serve versus scoring a letter on Bob. Their ratio is $$\frac{X(1-X)}{1-X} = X,$$ which is largest when $X$ is as close to $1$ as possible. So Alice should take the surest shot she can.

As that surest shot approaches certainty, the game becomes very long (a $99\%$ shot makes for roughly a two-hour, $700$-shot game), and Alice’s chance of eventually winning approaches a precise limit. In that limit each “decisive event” is equally likely to be Alice losing the serve or Bob taking a letter, and solving the resulting random walk to five letters gives Alice $$\frac{10802}{19683} \approx \boxed{54.9\%},$$ just under fifty-five percent, the cash value of going first.

The computation

Encode the game as a Markov chain on states (whose serve it is, Alice’s letters, Bob’s letters) for a fixed shot quality $X$, and solve for Alice’s win probability from the start. Sweeping $X$ toward $1$ shows the win probability rising monotonically (confirming “surest shot is best”) and converging to the limiting value.

import numpy as np
def alice_win(X):
    idx = {}; states = []
    for srv in "AB":
        for a in range(5):
            for b in range(5):
                idx[(srv, a, b)] = len(states); states.append((srv, a, b))
    n = len(states); M = np.zeros((n, n)); rhs = np.zeros(n)
    for (srv, a, b) in states:
        i = idx[(srv, a, b)]; M[i, i] += 1
        if srv == "A":
            M[i, idx[("A", a, b)]] -= X * X       # Bob matches; no change
            if b + 1 == 5: rhs[i] += X * (1 - X)   # Bob 5th letter: A wins
            else: M[i, idx[("A", a, b + 1)]] -= X * (1 - X)
            M[i, idx[("B", a, b)]] -= (1 - X)     # A misses; serve to Bob
        else:
            M[i, idx[("B", a, b)]] -= X * X
            if a + 1 == 5: pass                    # A 5th letter; A loses
            else: M[i, idx[("B", a + 1, b)]] -= X * (1 - X)
            M[i, idx[("A", a, b)]] -= (1 - X)
    return np.linalg.solve(M, rhs)[idx[("A", 0, 0)]]

for X in (0.5, 0.9, 0.99, 0.999, 0.9999):
    print(f"X={X}: Alice wins {alice_win(X):.5f}")
# X=0.5: 0.52799   X=0.9: 0.54499   X=0.99: 0.54842
# X=0.999: 0.54876   X=0.9999: 0.54879  ->  limit 10802/19683 = 0.548798...

Alice’s win probability climbs as her shot gets surer, confirming that the optimal play is the surest shot, and it converges to $10802/19683 \approx 54.9\%$, the value of the first-shooter advantage.