This week’s Riddler Classic is about how to optimally play HORSE — the playground shot-making game. Here is the problem.

Two players have taken to the basketball court for a friendly game of HORSE. The game is played according to its typical playground rules, but here’s how it works, if you’ve never had the pleasure: Alice goes first, taking a shot from wherever she’d like. If the shot goes in, Bob is obligated to try to make the exact same shot. If he misses, he gets the letter H and it’s Alice’s turn to shoot again from wherever she’d like. If he makes the first shot, he doesn’t get a letter but it’s again Alice’s turn to shoot from wherever she’d like. If Alice misses her first shot, she doesn’t get a letter but Bob gets to select any shot he’d like, in an effort to obligate Alice. Every missed obligated shot earns the player another letter in the sequence H-O-R-S-E, and the first player to spell HORSE loses.

Now, Alice and Bob are equally good shooters, and they are both perfectly aware of their skills. That is, they can each select fine-tuned shots such that they have any specific chance they’d like of going in. They could choose to take a 99 percent layup, for example, or a 50 percent midrange jumper, or a 2 percent half-court bomb.

If Alice and Bob are both perfect strategists, what type of shot should Alice take to begin the game?

What types of shots should each player take at each state of the game — a given set of letters and a given player’s turn?

Here is how I solved the problem:

[Show Solution]

Let’s denote the score numerically to make notation a bit easier. A score of $k$ means the player has accrued $k$ letters. First player to reach a score of 5 loses. We’ll consider the game from the point of view of Alice and define $V(a,b)$ to be the probability that Alice will win if it’s currently her turn, she has a score of $a$, and Bob has a score of $b$. This assumes both players are playing optimally.

Suppose it’s Alice’s turn, the score is $(a,b)$, and Alice attempts a shot that succeeds with probability $p$. One of three things can happen:

- Alice and Bob both make it. This happens with probability $p^2$. The score remains $(a,b)$, it’s still Alice’s turn, and she wins with probability $V(a,b)$.
- Alice makes the shot but Bob misses. This happens with probability $p(1-p)$. The score is now $(a,b+1)$, and it’s still Alice’s turn. So Alice wins with probability $V(a,b+1)$.
- Alice misses her shot. This happens with probability $1-p$. In this case, it’s now Bob’s turn and the score is still $(a,b)$. Since both players are playing optimally, by symmetry Bob will use the strategy Alice would use if the score had been $(b,a)$ and therefore win with probability $V(b,a)$. So Alice wins with probability $1-V(b,a)$.

We can therefore write the following recursion:

\[

V(a,b) = p^2 V(a,b) + p(1-p) V(a,b+1) + (1-p) \bigl( 1-V(b,a) \bigr)

\]Alice will choose $p$ in order to maximize $V(a,b)$, her probability of winning. We’ll now work backwards to find $V(a,b)$ for all values of $a$ and $b$.

### Computing $V(4,4)$

Setting $a=b=4$, defining $x=V(4,4)$, and using the fact that $V(4,5)=1$ (Alice wins if Bob reaches a score of 5), the recursion becomes:

\[

x = p^2 x + p(1-p) + (1-p)( 1-x)

\]Rearranging, this becomes:

\[

(1-p)(2+p)x = (1-p)(1+p)

\]One solution is to pick $p=1$, which makes the equation vacuously true and we learn nothing about $x$. This corresponds to the case where Alice chooses a shot that goes in 100% of the time. In such a case, Alice would keep shooting forever and the game would never end. So Alice would never lose, but she would also never win. To avoid this case (and to make this solution more realistic), let’s assume $0 \le p \le 1-\epsilon$, where $\epsilon\gt 0$ is a small positive number that characterizes how far from perfect the “easiest” shot is. This leaves us with:

\[

x = \frac{1+p}{2+p}

\]Alice wants to choose $p$ to maximize $x$, her probability of winning. The function above is an increasing function of $p$, and its maximum value is therefore $x=\frac{2-\epsilon}{3-\epsilon}$, which occurs when $p=1-\epsilon$. In short, Alice should shoot her easiest shot. In the limit, her probability of winning will be $\frac{2}{3}$.

### Computing $V(a,b)$ in general

Rearranging the recursion and dividing by $p-1$, we obtain:

\[

V(a,b) = \frac{p}{p+1} V(a,b+1) + \frac{1}{p+1} (1-V(b,a))

\]Let’s consider the cases $(a,b)=(3,4)$ and $(a,b)=(4,3)$ where the decisions made are $p$ and $q$ respectively. This leads to the pair of equations:

\begin{align}

V(3,4) &= \frac{p}{p+1} + \frac{1}{p+1} (1-V(4,3)) \\

V(4,3) &= \frac{q}{q+1}V(4,4) + \frac{1}{q+1}(1-V(3,4))

\end{align}Solving these equations, we obtain:

\begin{align}

V(3,4) &= 1-\frac{q}{p q+p+q} V(4,4) \\

V(4,3) &= \left(1-\frac{p}{p q+p+q}\right) V(4,4)

\end{align}Recall the goal is to pick $p$ to maximize $V(3,4)$ and pick $q$ to maximize $V(4,3)$. This happens when $p$ and $q$ are as large as possible. So setting $p=q=1-\epsilon$, we obtain:

\[

V(3,4)=\frac{\epsilon ^2-5 \epsilon +7}{(\epsilon -3)^2},\quad\text{and}\quad

V(4,3)=\frac{(\epsilon -2)^2}{(\epsilon -3)^2}

\]Or, when $\epsilon \to 0$, $V(3,4)=\frac{7}{9}$ and $V(4,3)=\frac{4}{9}$. Ultimately, we can keep repeating this process of solving for pairs of values at a time, until we fill out the whole table. In every case, the same thing happens: Alice should always play as well as she can. The easiest way to solve these equations is to write them out with $p=1-\epsilon$:

\[

V(a,b) = \frac{1-\epsilon}{2-\epsilon} V(a,b+1) + \frac{1}{2-\epsilon}(1-V(b,a))

\]and these are simultaneous linear equations for all choices of $a$ and $b$.

and here is the solution:

[Show Solution]

The optimal strategy is for both Alice and Bob to attempt the surest shots possible no matter what the score is. Using this strategy, if it’s Alice’s turn, her chances of winning are:

\[

\begin{array}{c|cccccc}

& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline

0 & \frac{10802}{19683} & \frac{4241}{6561} & \frac{545}{729} & \frac{617}{729} & \frac{227}{243} & 1 \\

1 & \frac{2984}{6561} & \frac{1216}{2187} & \frac{487}{729} & \frac{191}{243} & \frac{73}{81} & 1 \\

2 & \frac{256}{729} & \frac{328}{729} & \frac{46}{81} & \frac{19}{27} & \frac{23}{27} & 1 \\

3 & \frac{176}{729} & \frac{80}{243} & \frac{4}{9} & \frac{16}{27} & \frac{7}{9} & 1 \\

4 & \frac{32}{243} & \frac{16}{81} & \frac{8}{27} & \frac{4}{9} & \frac{2}{3} & 1 \\

\end{array}

\]Here, the rows correspond to Alice’s current score, and the columns correspond to Bob’s current score. If Alice and Bob can’t play perfectly, and the highest percentage shot they can make goes in with probability $1-\epsilon$, then the probability of winning as a function of $\epsilon$ is given by this table.

What about at the beginning of the game? Assuming Alice goes first and she can attempt shots that go in with probability $0 \le p \le 1-\epsilon$, her chances of winning as a function of $\epsilon$ are:

\[

P(\text{Alice wins}) = \tfrac{(\epsilon -2) \left(\epsilon ^8-20 \epsilon ^7+194 \epsilon ^6-1130 \epsilon ^5+4221 \epsilon ^4-10245 \epsilon ^3+15704 \epsilon ^2-13870 \epsilon +5401\right)}{(\epsilon -3)^9}

\]Here is what the plot looks like as a function of $(1-\epsilon)$.

So, for example, say your easiest layup shot goes in 85% of the time. Then you would substitute $\epsilon = 0.15$ into the formula above (or read it off the plot, and find that if you go first, your chances of winning against an equally matched opponent are about 54.3%. The optimal strategy is for both players to attempt the 85% shot every time.

In the limit of perfect shooting, when players can shoot a shot that goes in 99.999…% of the time, the player that goes first will win on average $\tfrac{10802}{19683}$ of the time, or about 54.88% of the time. Note that playing this way will lead to very long games!

I did not address the version of HORSE with $N$ players, as there are many regional variants of this game with different rules and I wasn’t sure which to look at. It would be interesting to see if the optimal strategy is still for all players to play their best shot all the time!