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