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

God Does Not Play Dice-He Plays Cards

This deck mechanism is not without its costs. A little detour from the mathematics department and into the computer science department will explain why. Each mechanism is implemented from an algorithm (which is a precise procedure for the rules of the game). Computing the amount of time required for the die mechanism is straightforward, as listed in Table 1.

Step in the algorithm Computations
For 20 attacks: 20
            Roll a die.             d
Total Time Complexity 20 d

Table 1. Algorithm outline of a die mechanism.

The deck mechanism is not much more complicated. A naive shuffling algorithm can shuffle in linear time with one random call per element. So, this implies a running time not worse than 19 fold of the running time of the die mechanism. This shuffling only needs to be called once every 20 attacks. As listed in Table 2, the time complexity (which is an abstraction of the amount of time required to execute the algorithm) for a card mechanism is greater than the die mechanism, but not by much. Although there are two operations to perform instead of one, the drawing of a card (c) from a shuffled deck is a trivial operation. In addition, within an efficient shuffling algorithm, shuffling one card in a deck of 19 (s) is approximately comparable to rolling a die with 19 sides (d).

Step in the algorithm Computations
Shuffle a deck of 19 cards. 19 s
For 19 attacks: 19
            Draw a card.             c
Total Time Complexity 19 c + 19 s = 19 (c + s)

Table 2. Algorithm outline of a card mechanism.

A more elegant algorithm may shuffle one card per attack, which means one randomization per attack, as listed in Table 3. This does not alter the total time complexity, but does distribute the computations more evenly, so that there is not a delay (for shuffling) after each 20th attack.

Step in the algorithm Computations
For 19 attacks: 19
            Draw a card.             c
            Shuffle that card.             s
Total Time Complexity 19 (c + s)

Table 3. Algorithm outline of a gradually shuffled card mechanism.

Of course, compared to the die, the deck requires memory, but this may be as little as an additional 19 bits per player to as much as 50 bytes per player.

Albert Einstein once remarked on another detailed mechanism, a mechanism for the elementary fabric of the universe. When presented with the random mechanism for modeling quantum physics, Einstein said, "God does not play dice." In the case of our RPG, maybe the Creator plays cards, instead.

Does it Matter?

Does it matter whether a die or deck is used? Both probabilities are negligible, making it unlikely for a designer to encounter such frustration. Yet even small probabilities, such as one in a thousand, are worth considering given enough players.

To understand, first we need to learn another distribution common to discrete probability. We want to know how many instances of player frustration will occur. Each instance is rare, so the mean of a Poisson distribution, E(X), is a good approximation, as formulated in Equation 6.

Equation 6. Poisson distribution models the count of frustrations.

In general, the Poisson distribution is used to measure the number of occurrences (λ) per unit time. We have already calculated the probability of a single instance of frustration (p). What remains to be determined are the number of attack strings in which frustration may occur (n). Let's consider two scenarios with sufficient sequences of player attacks, both in massively multiplayer games and in single-player games.

Case Studies

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

  Printable version
  Discuss this article