Many-Sided Dice, Lots of Sums -- and Even More CombinationsDate: 01/13/2011 at 14:05:45 From: Ryan Subject: RPG dice algorithm First off: you don't have to solve this, but ANY information would help. A few of my friends and I want to compare the probabilities and bell curves of the dice we use in our role-playing games (RPG) -- such as d4, d6, d8, d10, d12, d20, d24, and d100 -- or at least be able to generate an algorithm, given enough information. It is easy to calculate the probability of rolling an individual number on a fair die: (times desired # appears) ------------------------- (number of sides) Two is just as easy: (times desired # appears) ------------------------- (number of sides)^2 If pressed or stumped, I could even resort to brute force and write out all those possibilities on paper. But we're interested in including multiple dice of the same values, such as 1d20 vs 2d10 vs 5d4, or 1d12 vs 2d6 vs 3d4 vs 4d3 -- and figuring out the algorithm beyond 2 of the same dice seems difficult. 1d20 = 1/20 for all values 2d10 = {0, 1/100, 1/50, 3/100, ... up to 1/10 (at 11), then down} The only way I've been able to generate 3 or more of any single die is to list all possible values: 1-1-1 1-1-2 1-1-3, etc. I'm not even sure how to graphically write in three dimensions, let alone four or more. Date: 01/16/2011 at 23:34:32 From: Doctor Vogler Subject: Re: RPG dice algorithm Hi Ryan, Thanks for writing to Dr. Math. So you want to compute the probability of rolling a k on an n-d-m -- that is, n rolls of an m-sided die which sum to k. As you say, this is easy when n = 1, because then the probability is 1/m when 1 <= k <= m, and zero otherwise. And it seems like there should be a simple formula for larger n ... but things change rapidly when n grows. For example, for n = 2 when 2 <= k <= m + 1, you get (k - 1)/m^2 But when m + 1 <= k <= 2m, you get (2m + 1 - k)/m^2 (In the first case, the first die can be anything from 1 to k - 1 and then the second die is determined; in the second case, the first die can be anything from k - m to m, and then the second die is determined.) To see what happens in the case of n = 3, check out this Dr. Math conversation: http://mathforum.org/library/drmath/view/55804.html It turns out that you get three different regions: 3 <= k <= m + 2 : (k - 1)(k - 2)/(2m^3) m + 2 <= k <= 2m + 1 : [(k - 1)(k - 2) - 3(k - m - 1)(k - m - 2)] ------------------------------------------- (2m^3) 2m + 1 <= k <= 3m : (3m + 2 - k)(3m + 1 - k) ------------------------ (2m^3) Now have look at this conversation: http://mathforum.org/library/drmath/view/72008.html It explains why, when n <= k <= m + n - 1, the probability of the first region is always ... 1/m^n * (k - 1 choose k - n), ... which is the same as (k - 1 choose n - 1). (In case you're unfamiliar with this notation of binomial coefficients, n choose r, or nCr, is equal to n!/(r!(n - r)!).) Similarly, the last region is the mirror image of this. Namely, when mn - m + 1 <= k <= mn, then the probability is ... 1/m^n * (mn + n - k - 1 choose mn - k), ... which is the same as (mn + n - k - 1 choose n - 1) It takes a little more work to figure out what the second region will be. You get the first region by putting n balls (one ball each) in the n boxes that are your dice and then counting the number of ways to divide up the k - n remaining balls into the n boxes. Since k - n is at most m - 1, no box gets more than m - 1 balls, so there is no problem with asking too much of one die. If you do the same thing when k - n is a little bigger than m - 1, then you will also be counting ways where some box gets too many balls, so you should subtract off the number of ways to distribute the k - n remaining balls into n boxes such that one of the boxes gets more than m - 1 balls. That's the same number as n (to pick the box with at least m additional balls) times the number of ways to distribute the k - n - m other balls, which is n*((n - 1) + (k - n - m) choose n - 1) = n*(k - m - 1 choose n - 1) This computation is correct as long as it's not possible to get two or more boxes each with more than m - 1 balls, so you need k - n <= 2(m - 1). In other words, if n + m - 1 <= k <= n + 2(m - 1), then the probability of the second region is 1/m^n * [(k - 1 choose n - 1) - n*(k - m - 1 choose n - 1)] (You can check that this gives the same result as the last region in the case where n = 2.) Similarly, if mn - 2(m - 1) <= k <= mn - (m - 1), then the probability of the second-to-last region is 1/m^n * [(mn + n - k - 1 choose n - 1) - n*(n - 1 + mn - k - m choose n - 1)] (You can check that this gives the same result as the first region in the case where n = 2; and gives the same result as the second region in the case where n = 3.) To continue this kind of analysis to get formulas for the third and fourth regions, and so on, the inclusion-exclusion principle might come in useful: http://en.wikipedia.org/wiki/Inclusion_exclusion_principle There is a simple formula to determine i from k, namely i = 1 + floor((k - n)/(m - 1)). Now, I do believe that one could write an efficient algorithm to compute the probability with a computer program. But I expect you'll find that the formulas get increasingly complicated as n grows and the regions proliferate. In particular, I don't think that you'll be able to find a simple formula for the i'th region in terms of the number i. I hope this was helpful. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/