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.
