GameDev.netRandomness without Replacement

Randomness without Replacement
"Game mechanics" is one of those terms that every designer talks about. Everybody agrees that game mechanics is an important subject within game design. Yet almost nobody discusses, in detail, how the design of a mechanism may satisfy a player. In this article, I'm going to dissect a mechanism germane to role-playing games, the randomization function for determining whether a player's attack hits or misses its target. Roll up your sleeves for a modest amount of mathematics—just enough to demonstrate what a game mechanism is. ## Reducing FrustrationIn the opening story, one way to prevent frustrating results is to reduce randomness. Several massively multiplayer role-playing games, such as To reduce the occurrence of frustration, one possibility is to change the mechanism that models the randomness. For instance, let's change the method from sampling with replacement to sampling without replacement. But first, to understand this lingo, we need to know a little probability theory. It shouldn't be too hard for us, since probability theory was commissioned, in 1654, as the science of dice and card games. So we're in familiar territory: the mathematics of dice and cards. In probability, when a result of a random function is taken, it is called Back to the problem at hand: To reduce frustration, change from sampling with replacement to sampling without replacement. Basically, instead of rolling a die, draw a card. Let's use Open Game Content (OGC) as shared vocabulary. This is the system that Wizards of the Coasts based The key difference in the mechanism may be illustrated by a deck of cards alone. With replacement, after each draw, the card is shuffled back into the deck. Without replacement, the drawn cards are then discarded. Only after the deck has been consumed is the discard pile shuffled to reconstitute a full deck. To keep the analysis simple and further reduce frustration, remove one of the hit cards from the deck, and shuffle the remaining 19 cards. Then place this hit card on top of the shuffled deck. Suppose, in OGC terms, that the player has a melee attack of +0, then he would hit armor class 11 about 50% of the time. This may be modeled, with replacement, as a probability of success of 50%. To model this probability, without replacement, imagine there are 10 hit cards and 10 miss cards. If details are required to account for modifiers, then there may be 20 cards, valued from 1 to 20. Either way, 10 of these cards will result in a hit, and 10 will result in a miss. Without replacement, the player could sample 10 misses in a row, but the probability of this frustration is much less than by sampling with replacement. But how much less probable is it? ## Counting CardsCalculating the probability of frustration with replacement is simple. Suppose 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 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.
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. 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). Clearly, this mechanism reduces frustration. Furthermore, the mechanism without replacement guarantees never to have more than 10 consecutive misses (since the 1+20 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 CardsThis 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
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
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.
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, In general, the Poisson distribution is used to measure the number of occurrences ( ## Case Study: Massively Multiplayer RPGFor a simple example in a massively multiplayer role-playing game (MMORPG), there could average 1000 attacks per player per hour. To be crude, this could be coarsened to 100 strings of 10 attacks (Actually, only one of the ten possible combinations of ten consecutive failures conform to this demarcation). If—admittedly oversimplified—there were, for a reasonably small MMORPG, an average of 100 simultaneous players per day with uniform distribution of attacks, and independence of attacks, then there would be 100 strings / hour (24 hours / day) 30 days / month. The arithmetic equals 72,000 strings per month. Since this is very large and the probability is very small, the Poisson distribution approximates, with a rate of So there's going to be, on average for a low-traffic MMP, given these simplistic preconditions, 70 strings of frustration (i.e., 10 consecutive misses) per month using a mechanism analogous to a 1d20 die roll. Whereas, without replacement (a mechanism analogous to a 20-card deck), the expected number of frustrations is computed in Equation 8. For approximation, the number of trials is divided by two, because this is a sequence of 20, instead of a sequence of 10. So, there are about 18 times fewer occurrences of frustration. A distribution of the frustration may be estimated by the Poisson distribution, as shown in Figure 1. Because only whole numbers can occur, the distribution has been stepped at the rounded (midpoint) value of a continuous Poisson distribution. From comparing the distributions, it is obvious that without replacement, there are almost certainly going to be fewer cases of frustration. ## Case Study: Single-Player RPGThere's no theoretical or practical reason why such methods could not be applied to single-player and multiplayer RPG combat. The fact is, a game that sells a million copies, can expect similar figures to an MMP. It is a difference of penetration and time. The same Poisson distribution applies. Suppose the average player of a single-player RPG spends 10 hours with the game (since many more players quit sooner than those that play longer). If the rate of attacks remains constant (1000 attacks per hour), then only 7200 copies of the game need be sold to have the equivalent of a month of the modestly populated MMORPG above. ## Every Mechanism Should be Designed as Simple as Possible, but Not SimplerEinstein also said, "Everything should be made as simple as possible, but not simpler." Don't let mathematical precision dominate your analysis of a mechanism. While understanding the subtleties of a mechanism can make or break the design of a game, the relevance of the number crunching must be maintained. In this example, we computed the difference, not in terms of all kinds of player frustration that may occur, but only with one single variation to a mechanism within the game. We simplified the situation in order to keep the math brief. We did not consider players with probabilities to hit at above or below 50%, nor did we strictly adhere to the definition of independence for a Poisson distribution in the die mechanism. Astute readers will have also noted that the deck mechanism does not randomize the first card drawn. Doing so would further complicate the calculation of probability. Therefore, our result is only an approximation for a special deck. A more precise analysis was not necessary to prove the fitness of the deck mechanism. Bear in mind that a designer can correctly solve a problem but fail to solve the right problem. In this article, we honed in on one mechanism, ignoring the rest of the game and its effect on the player's satisfaction. Even if it were mathematically tractable, computing the distribution of loss of players due to this careful definition of one type of frustration is a tougher problem. ## About the AuthorDavid Kennerly directed five massively multiplayer games in the US and Korea. He localized Korea's first world, David encourages creativity among developers and players. He helped organize MUD-Dev Conferences, and founded an online library of fan fiction. David has authored on game design for Charles River Media, ITT Tech, Westwood College, Gamasutra.com, and IGDA. To discuss this article with the author, please visit his website www.finegamedesign.com ## Further ReadingJay L. Devore,
© 1999-2011 Gamedev.net. All rights reserved. |