Can You Systematically Solve A Friday Crossword?
A FiveThirtyEight Riddler puzzle.
By Vamshi Jandhyala in mathematics Riddler
April 30, 2021
Riddler Express
You’re playing a game of cornhole with your friends, and it’s your turn to toss the four bean bags. For every bean bag you toss onto your opponents’ board, you get $1$ point. For every bag that goes through the hole on their board, you get $3$ points. And for any bags that don’t land on the board or through the hole, you get $0$ points.
Your opponents had a terrible round, missing the board with all their throws. Meanwhile, your team currently has $18$ points — just $3$ points away from victory at $21$. You’re also playing with a special house rule: To win, you must score exactly $21$ points, without going over.
Based on your history, you know there are three kinds of throws you can make:
- An aggressive throw, which has a $40$ percent chance of going in the hole, a $30$ percent chance of landing on the board and a $30$ percent chance of missing the board and hole.
- A conservative throw, which has a 10 percent chance of going in the hole, an $80$ percent chance of landing on the board and a $10$ percent chance of missing the board and hole.
- A wasted throw, which has a $100$ percent chance of missing the board and hole.
For each bean bag, you can choose any of these three throws. Your goal is to maximize your chances of scoring exactly $3$ points with your four tosses. What is the probability that your team will finish the round with exactly $21$ points and declare victory?
Solution
Let us consider the general case of an $N$-throw game, and let the state be the number of points. The optimal probability $P_k(x_k)$ at the start of the $k^{th}$ throw as a function of the number of points $x_k$ is given by the dynamic programming recursion
$$
\begin{align*}
P_k(x_k) = \max[&a_h P_{k+1}(x_k+3) + a_b P_{k+1}(x_k+1) + a_m P_{k+1}(x_k), \\
&c_h P_{k+1}(x_k+3) + c_b P_{k+1}(x_k+1) + c_m P_{k+1}(x_k),\\
&P_{k+1}(x_k)]
\end{align*}
$$
where $a_h,a_b,a_m$ and $c_h,c_b,c_m$ are the probabilities of a throw landing in the hole, on the board and missing the board under aggressive and conservative throws.
The maximum above is taken over the three possible decisions:
Aggressive throw, which keeps the score at $x_k$ with probability $a_m$, changes it to $x_k+3$ with probability $a_h$ and $x_k+1$ with probability $a_b$.
Conservative throw, which keeps the score at $x_k$ with probability $c_m$, changes it to $x_k+3$ with probability $c_h$ and $x_k+1$ with probability $c_b$.
Wasted throw, which keeps the score at $x_k$ with probability $1$.
The required probability is obtained by calculating $P_1(0)$ given $N=4$ and the following terminal conditions:
$$
\begin{align*}
P_4(0) &= 0.4 \\
P_4(1) &= 0 \\
P_4(2) &= 0.8 \\
P_4(3) &= 1
\end{align*}
$$
From the code below, the probability that the team will finish the round with exactly $21$ points and declare victory is $\bf{85.48}%$.
Computation
N, max_pts = 4, 3
P = zeros(Float32, N, N*max_pts+1)
P[N,1], P[N,3], P[N,4] = 0.4, 0.8, 1
aₕ, aᵦ, aₘ = 0.4, 0.3, 0.3
cₕ, cᵦ, cₘ = 0.1, 0.8, 0.1
for k in N-1: -1 :1
for x in 1:k*max_pts+1
P[k,x] = max(aₕ*P[k+1,x+3]+aᵦ*P[k+1,x+1]+aₘ*P[k+1,x],
cₕ*P[k+1,x+3]+cᵦ*P[k+1,x+1]+cₘ*P[k+1,x],
P[k+1,x])
end
end
print(P[1,1])