Can You Systematically Solve A Friday Crossword?

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