Channels ▼
RSS

Design

Computing Competing Probabilities


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.

Figure 2: Possible calls.

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video