Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
49 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Randomness without Replacement


Counting Cards

Calculating the probability of frustration with replacement is simple. Suppose f equals the number of consecutive misses that will result in frustration, which we shall consider at 10 consecutive misses. With replacement, this is equivalent to a binomial distribution with a given probability of missing being the measure of consecutive trials. With a probability of a single failure being 50%, we may understand Equation 1. This logic is simple. The probability of failure ten times a row is the multiplication of the probability of failure ten times. So, in a sequence of ten attacks, the probability of frustration is about one in a thousand.


Equation 1. The probability of frustration, with replacement.

Calculating the probability of frustration without replacement is complicated, because the probability of each attack hitting depends on the success or failure of the previous attacks. A general method to solve problems of discrete probability is to count all the ways in which the event may occur, and divide this number by the count of all ways in which any outcome may occur.

In order to count possible occurrences of frustration, recall that the probability equals the number of ways to have a consecutive string of 10 misses out of 20 attacks. To simplify analysis and further limit frustration, set the first attack to be one of the hits. This corresponds to rolling a natural 20 in OGC. Since frustration (i.e., the string of 10 misses) is immutable, this is equivalent to the number of ways to select a single string of 1 out of 10. Recalling the basics of combinatorics (which is the mathematics of counting), this simplification makes computation trivial, as shown in Equation 2.


Equation 2. How many ways an attacker may be frustrated, without replacement.

Then count the total number of ways to have 9 hits and 10 misses in a sequence of 19 attacks, as shown in Equation 3.


Equation 3. How many ways an attacker may attack, without replacement.

By dividing the count of frustrations by the count of all attacks, we arrive at the probability of frustration, as demonstrated in Equation 4. So, the probability of frustration in the course of twenty attacks is about one in ten thousand.


Equation 4. The probability of frustration, without replacement.

By dividing the solution of Equation 4 by Equation 1, we see that the sample without replacement decreases the probability of frustration by an order of magnitude, shown in Equation 5. To keep the analysis simple, multiply the probability of frustration with replacement by 2 (or divide without replacement by 2), since the probability in a sequence of 20 attacks (without replacement) is being compared to a sequence of 10 attacks (with replacement).


Equation 5. Nonreplacement dramatically decreases frustration.

Clearly, this mechanism reduces frustration. Furthermore, the mechanism without replacement guarantees never to have more than 10 consecutive misses (since the 1+20kth occurrence always hits).

Although the above analysis is only a solution for one of the parameters that a player may have of hitting an opponent (i.e., melee attack of +0 versus armor class 11), the same analysis can be carried out on all possible parameters. Likewise, this analysis can be carried out for any given lower bound to frustration. If worst-case analysis of player satisfaction had predetermined 5 consecutive misses to be the maximum tolerance before frustration occurs, then the deck could be divided into two separate decks, each without replacement, so long as each deck had no more than 5 in it. For the sake of uniformity, two decks might be evenly divided (i.e., 75% success rate = 7 out of 10 and 8 out of 10).





God Does Not Play Dice-He Plays Cards


Contents
  Reducing Frustration
  Counting Cards
  God Does Not Play Dice-He Plays Cards
  Case Studies

  Printable version
  Discuss this article