January 31st, 2008 — Wordman
Based on an opinion voiced in an Exalted forum, I picked up the hardback of Reign, a game self-published by Greg Stolze. Stolze is the co-author of the incredibly good Unknown Armies and wrote the best “how to run a game” chapter that I’ve ever read (published in the otherwise unremarkable Gamma World Game Master’s Guide), so I was excited to see how he tackled the epic fantasy genre. Mechanically, he does so with something called the One Roll Engine. (If you want to sign up to a site with a not-very-helpful user interface, you can download a version of the basic system for free.) This engine makes use of dice in a way I haven’t seen a game utilize before, and I figured I’d blog about the probability of the system because a) I didn’t immediately know how to calculate it, b) a post on how to do such probability calculations will hopefully be useful to fellow gamers and c) I wanted an excuse to play with the statistical and graphing features of Numbers.
Reign uses pools of ten-sided dice (d10s), where results are determined by looking at how many dice match each other. It is a bit like poker, where a roll might generate, say, a three-of-a-kind, a pair, and some singles. Each of these matches is called a “set”, and the number of dice in the set is called the “width” of the set. So, for example, if you roll five dice and get 4, 4, 4, 2, 8, you have one set of width three. For many rolls in Reign, the actual number being matched, called the “height” of the set (4 in the previous example), doesn’t particularly matter. For other rolls, only the height matters. Still others rely on both the height and the width. Usually only a single set in a roll matters, but there are some mechanics that make use of the other sets as well. In this way, the rules in Reign pull a lot of meaning out of a single roll mechanic, and the probabilities employed are interesting but not obvious. I’ve done some (very) minor probability documentation on some other systems (an invented five-suit card game and the “excellencies” of Exalted, for example), but this is a bit more tricky.
The first basic observation to make is that if you have a pool with more than 10 dice in it, you will always get at least one set. If you have n+1 items that can only have n distinct values, at least one of those values will come up more than once. Reign is well aware of this, and has rules to match. Consequently, pools only exceed 10 dice in very extraordinary circumstances; however, these circumstances, though rare, do exist in the game, so this post will consider results with up to 15 die pools.
Secondly, for any given roll, the odds of achieving exactly a specific height are identical to achieving any other exact height. That is, odds of rolling two tens using 5d10 are exactly the same as rolling two nines. This means that, were you to build a chart where rolling height x means one thing and height y means something else, you have equal chances of getting either result. Thus, if you want one result more than the others, you need to assign that result to more than one height on the chart. Reign makes use of this idea at least once in the rules (as a hit-location table). More often, however, height is used in rules where the height must be at least that number or higher. This makes reaching a certain height harder as the number increases. A height of 10, for example, can only be reached if the dice conspired to built a set containing 10s, but a height of nine is reached by those same sets plus sets containing nines, making it more likely. As a result, when this post considers height, it will do so in the sense of reaching at least that height.
Because Reign deals with sets, the key technique in calculating probability is combinatorics. In particular, the concept of a combination is crucial. This looks scary, but you probably had to do some of this in high school math class. The basic idea is that you have some number of items in your hand, and you have to select a certain (smaller) number of those items. The combination calculation measures how many different ways you could make such as selection, where order does not matter. For example, say you have four cubes in your hand, one red (r), one blue (b), one green(g), one violet (v). You are instructed to select two cubes, where the order doesn’t matter. You can do this, it turns out, six different ways: rb, rg, rv, bg, bv, gv. This would be notated as C(4,2), read “four choose two”. Generically, C(n,k), or “n choose k“. You may also have vague memories of a permutation, which is the same idea as combination except that order does matter. For example, rb and br are considered the same combination, but different permutations. A permutation of two items from a set of four is notated as P(4,2). Calculating both combinations and permutations makes use of the factorial operator. This is a fairly simple idea to wrap your head around. A number like “4 factorial”, notated “4!” just means to multiply 4 × 3 × 2 × 1. So n! just means n × n−1 × n−2 × … × 3 × 2 × 1. Combinations and permutations are calculated as follows:
|k||k||k! (n − k)!||(n − r)!|
Fortunately, before you run screaming from this, most spreadsheets (and more advanced calculators) have functions for combinatorics. Excel, for example, uses
combin(n,k). It also has
power(x,y), which are also useful. (One note here: Numbers lacks a
permut(n,r) method, which is extremely irritating.)
Calculating odds of rolls like this is somewhat similar to calculating odds in poker: you figure out how many possible ways there are to get a certain result, and you divide by the total number of all results. This gives the percent chance of achieving that result. Calculating the total possible results for a die roll is easy: start with a single die and figure out how many results this die can yield. Unless you are using very strange dice, this will equal the number of faces on the die. For each die you add to the pool, multiply by the number of ways that die can come up. So, if you roll a d20, a d12 and a d6, the total possible outcomes are 20 × 12 × 6. Since Reign uses pools of n d10s, for any given roll the total possible outcomes are 10n.
Calculating the ways to get a given result is usually more difficult. One very trivial thing to figure out: what are the odds of all of the dice of a roll matching? In this case, all of the dice have to match, and there are ten possible values this match can have. Thus, no matter how many dice are rolled, there are only ten possible rolls that result in all of them matching. This means the probability is always 10 ÷ 10n = 1 ÷ 10n−1 = 101−n.
Another basic building block is also easy to calculate: when rolling n dice, what is the chance that you will get no set at all? To figure this out, you need to know how many ways you can roll the dice such that none match any of the others. So, try to actually construct such a roll, rolling one die at a time. The first die could come up as anything, so it would have 10 possible outcomes. The second die could be anything but the value of the first, so would have nine possible outcomes. The third could have eight possible values and so on. This sequence is sort of like 10! (that is 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) with the last few terms hacked off based on how many dice you had. If you had six dice, for example, you’d need to hack off the 4 × 3 × 2 × 1 part. Note that this is 4! and that “hacking off” the terms would be done by taking 10! ÷ 4!. Note that this is exactly the formula of P(10,6), above. (This is not a coincidence, but rather exactly what permutation is.) Knowing the chance of no match, you can take 1 minus this number to figure out the chance of at least one match. The outcome looks like this (note that this matches with page 57 of the main Reign rulebook):
Getting more detailed results requires more complexity. It happens that one of the tools needed to proceed requires figuring out the odds of rolling exactly one set with a given width, and all the rest of the dice not matching at all. By itself, this number is more of an intermediate result, but a general formula for figuring it out will help calculating more important results. We’ll call this formula “exact” and we do it like this:
- Let n be the pool size, i.e. the number of dice.
- Let d be the number of sides. In Reign, d is always 10.
- Let w be the desired width.
- If you were to hand pick a set of the desired width from your pool, you would need to select the height of the set you are going to build, and a number of dice. The number of possible ways to do this is d × C(n,w).
- The dice that are not part of the set have dn−w possible values, but some of these would either make the current set larger, or could combine to make sets of their own. We want to make sure that all of the remaining dice not only don’t match the set set, they don’t match each other, either. Since we used w dice to make the set, that leaves n−w dice. Using ten-sided dice, the first of these dice would have nine possible ways of not matching the set. The next would only have eight possibilities, as it should match neither the set nor the previous die. The next die (if there is one), would have seven possibilities and so on. If you look at the pattern, you can see that this winds up being equal to P(d−1,n−w).
- Taking these all together, that makes d × C(n,w) × P(d−1,n−w) possible ways to roll n d-sided dice such that they generate exactly one set of exactly width w.
- In Reign, the formula is Exact(n,w) = 10 × C(n,w) × P(9,n−w)
For reference, this formula gives the following values:
Calculating width odds
Armed with this information we can start answering real questions about the probability of specific results. Unfortunately, there is no one formula that provides a generic answer. Each roll of n dice acts a bit like a poker hand of n single-suited cards or, more closely, a roll in a game of poker dice (which is essentially a simplified version of Yahtzee). You have to look at the various possible results, and count them independently. Unfortunately, you have to do this separately for each value of n. We’ll show details of n=7, since it is large enough for interesting things to occur. With seven dice, you have 107 possible rolls, with the following possibilities:
- No match (0x). This we calculated above: P(10,7)
- Single pair (2x). This we calculated above: Exact(7,2)
- Two pair (2x,2x). There are C(10,2) ways to select the heights of the pairs. The first pair can be selected C(7,2) ways, the second C(5,2). The remaining three die can come up P(8,3) different ways without matching the two pair or creating new pair of their own (that is, 8 × 7 × 6). So, the total number of exactly two pair rolls with seven dice is C(10,2) × C(7,2) × C(5,2) × P(8,3). Note that this suggests a general formula for the number of exactly two pair results for any number of dice n: C(10,2) × C(n,2) × C(n−2,2) × P(8,n−4), with the realization that this is only possible for some values of n (i.e. if n is less than 4, you can’t actually build two pair, and P(8,n−4) becomes undefined as well).
- Three pair (2x,2x,2x). Similar to two pair, using this general formula: C(10,3) × C(n,2) × C(n−2,2) × C(n−4,2) × P(7,n−6).
- Single triple (3x). This we calculated above: Exact(7,3)
- Triple and a pair (3x,2x). Ten ways to select the height of the triple, the dice for which can be chosen C(7,3) ways. That leaves nine possibilities for the height of the pair, the dice of which can be selected C(4,2) ways. For the remaining two dice, there are 8 possible values for the height for the first and seven for the second (otherwise they match either each other or one of the other sets). Note that this is P(8,2). The total is then 10 × C(7,3) × 9 × C(4,2) × P(8,2). Again, a general formula suggests itself: 10 × C(n,3) × 9 × C(n−3,2) × P(8,n−5)
- Triple and two pair (3x,2x,2x). Ten ways to select the height of the triple, the dice for which can be chosen C(7,3) ways. There are C(9,2) ways to select the heights of the pairs. The first pair can be selected C(4,2) ways, the second C(2,2). The remaining three die can come up 7 different ways without matching the other sets (note that this is P(7,1)). 10 × C(7,3) × C(9,2) × C(4,2) × C(2,2). For more than seven dice, there would dice left over that could not match the value of any of the sets or each other, so permutations of the seven remaining possible values would be used: 10 × C(n,3) × C(9,2) × C(n−3,2) × C(n−5,2) × P(7,n−7).
- Two triples. Calculated much like two pair, with a general formula of C(10,2) × C(n,3) × C(n−3,3) × P(8,n−6).
- Four of a kind (4x). This we calculated above: Exact(7,4)
- Four of a kind and a pair (4x,2x). Similar to a triple and a pair: 10 × C(n,4) × 9 × C(n−4,2) × P(8,n−6)
- Five of a kind (5x). This we calculated above: Exact(7,5)
- Five of a kind and a pair (5x,2x). Similar to a triple and a pair: 10 × C(n,5) × 9 × C(n−5,2) × P(8,n−7)
- Six of a kind (6x). This we calculated above: Exact(7,6)
- Seven of a kind (7x). This we calculated above: Exact(7,7)
You can do similar analysis of all the other lengths, and you end up with the table below. Each row in the table shows a possible set combination that may be rolled, and the general formula to figure out how many possible outcomes will generate that set combination. Naturally, not all combinations are possible for a given number of dice. Try as you might, you’ll never get a width three set from two dice. Each cell in the table shows two different bits of information for given result for a given number of dice. The first is the numeric result of that number. The second, in bold, is the percentage chance of that result when rolling that many dice. Because the table gets obnoxious as the number of dice increases, this only shows results for two to 10 dice, but you should be able to use techniques shown above to extend it to more if you need to. (I also wrote some really horrid Python code to double-check these numbers by counting the sets made by every possible roll from 2 to 10 dice. It all matches.)
As mentioned above, calculating odds for height is only interesting when you need a roll of at least a given height. Such calculation is surprisingly cumbersome, even if you mostly leave width out of it. In order for width to “count”, you must have at least one match, and this is what makes things hard to figure. It is honestly easier just to write code to count all possible outcomes, but if you want to figure it out do the following:
- Let n be the pool size, i.e. the number of dice.
- Let d be the number of sides. In Reign, d is always 10.
- Let h be the minimum height needed. Naturally, 0<h≤d.
- You now need to break the problem into sub-problems. So let m take on values from 2 to n. For each value of m, figure out the following:
- Figure out how many rolls of n dice of d sides generate exactly m dice that have values of h or greater. This can be done with a function X(n,d,m,h) = C(n,m) × (d-(h-1))m × (h-1)(n-m). Note that when h=1 and m=n, the final term in that function is 00, which is technically undefined, so is omitted in that case.
- Figure out how many possible ways the n dice of d sides can come up. We did this above: dn.
- Find the probability of X(n,d,m,h). This is just the value of the function, divided by the total number of possible rolls. So ProbXm = X(n,d,m,h) ÷ dn.
- Now, given the m dice that came up h or greater, figure out the number of possible ways those dice can match. We do this much the same way we figured out the chance of at least one match, above. This time, though, we have only d-(h-1) possible values. So the possible ways to have no match with these dice is P(d-(h-1),m). The number of possible ways these dice can come up is ÷ (d-(h-1))m. So Y(d,m,h) = (d-(h-1))m − P(d-(h-1),m).
- Figure ProbYm = Y(d,m,h) ÷ (d-(h-1))m.
- Remember Probm = ProbXm × ProbYm.
- Now add up all values of Probm, and you have the probability of rolling at least height h on n dice of d sides.
This looks like this, again with the total number of rolls that meet a given height, followed by the percentage chance: