Channels ▼
RSS

Design

Computing Competing Probabilities


We've discussed important topics in the last few columns — reliability, dynamic programming, and competitive algorithms. But now it's time to get down to serious business: basketball. Our goal is guide an imaginary coach in his decision about which play to call. We want to do this now, while there is plenty of time to prepare for the next season and beat the predictions for the next March Madness (see http://netprophetblog.blogspot.com/).

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?"

The answer depends on many factors. We will focus on three:

  1. The chance that the team that takes a given shot gets the basket;
  2. 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);
  3. 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. Assume further that these probabilities include the likelihood that a team that is committed to taking a k point shot will take the next shot and will make it a k point shot — thus incorporating the aforementioned considerations (1) and (2). Under this assumption, p2 is the probability that the team will get a two point shot before losing possession; similarly, for 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 and on the criterion for winning the game.

In informal games, there are two ways to play:

  1. "winner-takes-out" — the team that has just made the basket takes the ball out again
  2. "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. 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 1: 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.

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. (We can change our software later to take care of winning and losing streaks.)

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 on its possession 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). And so on; see Figure 1.

Figure 1: Possibility tree.

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 and makes the programming easier when we deal with more general cases.


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