How do we deal with games having more points? For this we use recursion. Suppose again that both teams shoot only three point shots under "loser-takes-out." Let **probAwin(Aposs, x, y) **mean "the probability that **A** wins when **A** has possession, **A** has **x** points to win, and **B** has **y** points to win." Then we have:

probAwin(Aposs, x, y) = (p3 * probAwin(Bposs, x-3,y)) + (1p3)*probAwin(Bposs, x, y).

The first term corresponds to the case in which team **A** hits the three, so has only **x-3 **points to go, but **B** has possession because it is "loser-takes-out." The second term is the case in which **A** misses the three (with probability **1-p3**), but now the question is, "What is the probability that **A** can win (and I mean **A**) if **B** has possession, **A** has **x** points to go, and **B** has **y** points to go?"

Whereas this formulation is correct, it incorporates neither a point nor a probability cutoff, so it will never stop. The point cutoff is easy: When either **x** or **y** is zero (or negative), the game is over. For the probability cutoff, we fold the probability into **probAwin**. We might call this folded probability **f**. That is, **probAwin(f, Aposs, x, y) ** means "the probability that **A** wins when **A** has possession, **A** has **x** points to win, **B** has **y** points to win, and the folded probability is **f**."

probAwin(f, whohas, x, y) begin if (x <= 0) return 1 // A has won if (y <= 0) return 0 // B has won so probability that A will win is 0 if (f < 0.005) return 0 // no more contribution to A's winning if(whohas == Aposs) return (f * p3 * probAwin(1, Bposs, x-3,y)) + probAwin(f*(1-p3),Bposs, x, y) end

The last line requires some explanation. The first term **(f * p3 * probAwin(1, Bposs, x-3,y)**) again corresponds to the total contribution to **A**'s winning probability given that **f** is the folded probability, **A** has possession, and **p3** is the probability that a three point shot will go in. The **1** in the recursive call has to do with the fact that **B** will be taking it out when **A** has **x-3** points to go and **B** has **y** points to go, so the folded probability is **1** for that call. The second term **probAwin(f*(1-p3),Bposs, x, y)** corresponds to the contribution to **A**'s winning probability given that the case in which **A** misses in this situation has probability **f*(1-p3)**. For completeness, we should also write the pseudocode when **B** has possession (but we are still computing the probability that **A** will win).

probAwin(f, whohas, x, y) begin if (x <= 0) return 1 // A has won if (y <= 0) return 0 // B has won so probability that A will win is 0 if (f < 0.005) return 0 // no more contribution to A's winning if(whohas == Bposs) return (f * p3 * probAwin(1, Aposs, x,y-3)) + probAwin(f*(1-p3),Aposs, x, y) end

When **p3 = 0.7**, Figure 2 shows some of the possible calls for the "loser-takes-out" situation.

**Warm-up 3:** How would the pseudocode for** probAwin(f, Bposs, x, y)** change under a "winner-takes-out" rule?

**Solution:** The only change is to the first term of the last **return** statement. Possession would not change, so it should read: **return (f * p3 * probAwin(1, Bposs, x,y-3)) + probAwin(f*(1-p3),Aposs, x, y)**.

### Challenge

First, in a "loser-takes-out" game up to 12 in which each side shoots only three point shots, each with a probability of 0.7, what is the probability that team **A** (the one with initial possession) wins?_{[1]}

How do we deal with the case when a team can shoot for two, three, or (if you ask the Harlem Globetrotters) four points? We use the same basic structure of **probAwin**, but this time we must consider the various shooting options. Because **A** wants to win, when **A** has possession, the procedure should consider each possible shooting option and choose the one that gives **A** the GREATEST probability of winning the whole game. When **B** has possession, the procedure should again consider each possible shooting option, but should choose the one that gives **A** the LEAST probability of winning the whole game. In the "loser-takes-out" case, we would have:

probAwin(f, whohas, x, y) begin if (x <= 0) return 1 // A has won if (y <= 0) return 0 // B has won so probability that A will win is 0 if (f < 0.005) return 0 // no more contribution to A's winning if(whohas == Aposs) begin shoot2prob := (f * p2 * probAwin(1, Bposs, x-2,y)) + probAwin(f*(1-p2),Bposs, x, y) shoot3prob := (f * p3 * probAwin(1, Bposs, x-3,y)) + probAwin(f*(1-p3),Bposs, x, y) return max(shoot2prob, shoot3prob) end if(whohas == Bposs) begin shoot2prob := (f * p2 * probAwin(1, Aposs, x,y-2)) + probAwin(f*(1-p2),Aposs, x, y) shoot3prob := (f * p3 * probAwin(1, Aposs, x,y-3)) + probAwin(f*(1-p3),Aposs, x, y) return min(shoot2prob, shoot3prob) end end

Finally, we deal with the question of efficiency. Suppose we play a game to 15. There may be many ways to arrive at the state when player **A** has, say, 7 points to go, player **B** has 5 to go, and **A** has possession. Instead of recomputing the probability of that situation each time, we keep a table that holds all these "end-game" answers. So, to compute the probability that team **A** wins a game up to some number **x**, the dynamic programming approach calculates the probability that **A** wins all shorter games first.

If you've built programs based on these guidelines, then the following challenges shouldn't be too hard for you.

Next, given a "winner-takes-out" setting in an 11-point game where **p2 = 0.8** and **p3 = 0.6**, how likely is it that **A** will win?_{[2]}

Next, how does this change if we have a "loser-takes-out" setting?_{[3]}

Next, suppose that four point shots are allowed and **p4 = 0.5**. In that case, what is **A**'s probability to win in a loser-takes-out setting?_{[4]}

Next, in many pick-up games, a two point shot is given one point and a three point shot is given two points (thus vastly increasing the benefit of the three point shot). In a "winner-takes-out" strategy where **p2 = 0.8** and **p3 = 0.6**, what is the probability of winning for the team having first possession?_{[5]}

Coaches could use such software to figure out which players to recruit if they have a choice between a player who could improve their team’s **p2** and another who could improve their **p3** (or could diminish the oppenent’s **p2** or **p3**).

Solutions appear on the next page.