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

A blade spider is at your throat. It hits and you miss. It hits again and you miss again. And again and again, until there's nothing left of you to hit. You're dead and there's a two-ton arachnid gloating over your corpse. Impossible? No. Improbable? Yes. But given enough players and given enough time, the improbable becomes almost certain. It wasn't that the blade spider was hard, it was just bad luck. How frustrating. It's enough to make a player want to quit.

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

In the opening story, one way to prevent frustrating results is to reduce randomness. Several massively multiplayer role-playing games, such as Lineage 2, reduce variance of hits and misses and reduce the variance of damage. Reason? As Alex Chacha stated, if the probability for a string of failures is above zero, then the probability for that string occurring at least once in the lifespan of a long game is very high ("Randomness," MUD-Dev Mailing List, February 2004.). And once it does, it is a frustrating experience. So, in this article, let us call such a long string of consecutive failures frustration.

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 sampling. There are two basic methods for sampling: with replacement (as in a die roll), or without replacement (as in drawing cards from a deck). The difference seems simple, but the implications, as we shall see, may be dramatic.

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 Dungeons & Dragons 3.5 on. So, instead of rolling a twenty-sided die (1d20), draw from a deck of twenty cards, perfectly shuffled.

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 Cards

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

  Printable version
  Discuss this article