Can You Systematically Solve A Friday Crossword?

A FiveThirtyEight Riddler puzzle.
mathematics
Riddler
Published

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])