Our goal is guide an imaginary coach in his decision about which play to call.
In basketball, shots beyond a certain distance are worth three points while inside shots are worth only two points. The question we will ask is when should a team go for the three and when should it be happy with the two.
This depends on many factors. We will focus on three:
(i) the chance that the team that takes a given shot gets the basket;
(ii) the chance that the team that takes a shot gets to take the next shot (either by getting the rebound or by stealing from the other side); and
(iii) whether the game is played with "winner-takes-out" or "loser-takes-out"
Let's say that your team's probability of hitting an inside shot is p2 and the probability of hitting an outside shot is p3 where p2 > p3. Naively, you might think it is better to shoot a three point shot when 3*p3 > 2*p2, but that depends on the take-out rule.
In informal games, there are two ways to play:
(i) "winner-takes-out" -- the team that has just made the basket takes the ball out again; and
(ii) "loser-takes-out" -- the opponents of the team that made the basket take the ball out.
Warm-up 1: Consider a game up to three. Suppose that after a missing shot by one team, the other team always makes the next shot (i.e., no steals and no offensive rebounds). Can you think of values p2 (probability of hitting a two point shot) and p3 (probability of hitting a three point shot) in which it would be a better strategy for a team to take a three point shot under "loser-takes-out" but a two point shot under "winner-takes-out"?
Solution to warm-up: Here is one scenario. Suppose that p2 = 1 and p3 = 0.8 for both teams. Under winner-takes-out, if the team with initial possession takes a two point shot, then it will surely hit it and then retain possession to hit a second two point shot and win. Under loser-takes-out, if the team with initial possession takes a two point shot, then it will surely hit it, but then the other team can attempt a three point shot and win with a likelihood of 0.8. End of Warm-Up 1.
When probabilities are lower, there may be several missed shots before anyone scores. How do we analyze that? To make this simple, let's say that both teams take only three point shots, each with probability p3, where these probabilities are independent. Independence means that the chance that a team gets a basket when it has possession does not depend on history.
Let's call the team with initial possession A and the other team B. Team A will get the next basket in the next shot with probability p3. But A can get the next basket also if it missess and then B misses and then A hits (probability (1-p3)*(1-p3)*p3). In addition, A could miss initially, then B misses, then A misses, then B misses, then A hits (probability (1-p3)*(1-p3)*(1-p3)*(1-p3)*p3). See figure http://cs.nyu.edu/cs/faculty/shasha/papers/basketballfig1.docx And so on.
We cut this possibility tree off when the probability falls below a threshold. For example, if the threshold is 0.005, then we won't add in probabilities below that number.
Warm-Up 2: Suppose in a game up to three, the threshold is 0.005, only three point shots are allowed, and p3 for both teams is 0.7. What is the likelihood that team A, the team with initial possession, wins?
Solution: The exact solution is s1 = 0.7 + (0.3)*(0.3)*(0.7) + (0.3)*(0.3)*(0.3)*(0.3)*(0.7) + ... because all these possibilities are mutually exclusive. To compute the exact solution, recall from high school algebra that 0.09 * s1 = (0.3)*(0.3)*(0.7) + (0.3)*(0.3)*(0.3)*(0.3)*(0.7) + ... Therefore, s1 - 0.09 * s1 = 0.7. So 0.91*s1 = 0.7 or s1 = 0.769. The approximate solution using the cutoff is 0.763. The approximate solution is close enough for our purposes makes the programming easier when we deal with more general cases. End of warm-up 2.
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)) + (1-p3)*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-take-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) mean "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 pseudo-code 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 http://cs.nyu.edu/cs/faculty/shasha/papers/basketballfig2.docx shows some of the possible calls for the loser-takes-out situation.
Warm-up 3: How would the pseudo-code 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). End of Warm-Up 3.
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.
Your task is to design a coach. You will be playing against another coach. You will be given a probability of a two point shot and a probability of a three point shot. Each team will be given a different p3 and p2, but they will have the properties that p3 will always be less than p2 and the sum of the expected values for the team having initial possession will equal the sum for the other team. For example, the team having initial possession may have p2 = 0.8 and p3 = 0.6 so the sum of the expected values is 1.6 + 1.8 = 3.4. The non-initiating team in that case may have p2 = 0.7 and p3 = 0.6667 thus having sum of expected values of 1.4 + 2 = 3.4. You will also be given the number of points in the game (e.g. 11 or 15). Finally, you will be told whether the game is winner-takes-out or loser-takes-out.
Each time you have possession, you can decide whether your team will attempt a two or three point shot. The architect will use a random number generator (with a seed I provide) to determine which shots make it into the basket and which don't. You will play two games with each opponent. In the first game, one of you has initial possession. In the second game, the other does. (The probabilities depend on which team is initiating.) Your score will be the total number of points you win over the two games. The winner of each competition is the person with the highest score.
Receive shot choice from team in possession of the ball. Returns result of the shot based on probabilities and then asks the appropriate team (depending on whether we are playing winner-takes-out or loser-takes-out) for its shot choice. You will keep score and ensure that each player's program stays within the two minute limit.