In the last piece I wrote, I was describing how I was trying to make a tool to efficiently calculate the probability of rolling or exceeding a particular sum on a number of dice. I had gotten as far as a recursive solution which allowed me to roll any number of `s`-sided dice, but which rapidly slowed down as more dice were added.
I spent a good amount of time at this point tearing my hair out looking for patterns in the numbers that would allow me to directly calculate the total number of ways to roll a particular number on `n` `s`-sided dice. I never came up with one. What I did end up doing was mentioning my problem to a mathematically inclined officemate, who found a paper on an interesting technique for me
### The Technique
The general gist of this method is to, for each face of your current die, add it to the various sums you made on your previous dice.
Let’s give it a try, because that explanation was nearly worthless. I’ll roll two six-sided dice (by hand) to keep things simple, and verify my results against what my prior calculator generated. Then I’ll write a program that will use this method for any `n` `s`-sided dice, as before.
For the first die, I can roll any number 1 through 6 exactly one way.
| pips | ways |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
Now, when I roll the second die, I can get a 1 through 6, and add it to each of the pips/ways pairs above. I’ll show what I mean. In the case that my second die is a 1, the table updates like this:
| total pips | old pips | new pips |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 4 | 1 |
| 6 | 5 | 1 |
| 7 | 6 | 1 |
OK, so that chart isn’t completely enlightening, at least not yet. Please do note that total pips is old pips + new pips. Now I’m going to see what happens if my die comes up a 2.
| total pips | old pips | new pips |
|---|---|---|
| 3 | 1 | 2 |
| 4 | 2 | 2 |
| 5 | 3 | 2 |
| 6 | 4 | 2 |
| 7 | 5 | 2 |
| 8 | 6 | 2 |
Then I add the charts from rolling 1 and 2 and count the number of ways I can get each number.
| total pips | total ways |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 2 |
| 6 | 2 |
| 7 | 2 |
| 8 | 1 |
I’ll do the whole thing again for a three. Possible outcomes:
| total pips | old pips | new pips |
|---|---|---|
| 4 | 1 | 3 |
| 5 | 2 | 3 |
| 6 | 3 | 3 |
| 7 | 4 | 3 |
| 8 | 5 | 3 |
| 9 | 6 | 3 |
And add it to the running count of new possibilities:
| total pips | total ways |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 3 |
| 6 | 3 |
| 7 | 3 |
| 8 | 2 |
| 9 | 1 |
If you recall from last time what the chart of how many ways you can roll a given number on two dice looked like, you’ll see that we’re well on our way to generating it. I’m just going to jump ahead and show the results for applying this from 1 all the way to 6 for the second die.
| total pips | total ways |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 4 |
| 6 | 5 |
| 7 | 6 |
| 8 | 5 |
| 9 | 4 |
| 10 | 3 |
| 11 | 2 |
| 12 | 1 |
So, let’s have some code.
### The Code
#!/usr/bin/python
def roll(n, s):
# roll n s-sided dice
numresults = s ** n # s^n results
# make two buffers, with 1 for each value on 1 die
# neededd because we only do a proper calculation for 2+ dice
buff = [0] + [1] * s + [0] * ((n - 1) * s)
oldbuff = [0] + [1] * s + [0] * ((n - 1) * s)
for d in range(2, n + 1): # for dice 2 through n
# clear buffer
buff = [0] * (s * n + 1)
for i in range(1, s + 1):
# for each face, sum with old outcomes
for j in range(d - 1, (d - 1) * s + 1):
# We are doing die 'd' now
# prior results are thus in the range of (d-1, (d-1)*s)
# We found one way * oldbuff[j] ways = oldbuff[j] ways to get here
buff[i + j] += oldbuff[j]
oldbuff = buff
return (buff, numresults)
def printres(results, numresults):
remaining = numresults
print "N\t#N\t%N\t#N+\t%N+"
for i in range(len(results)):
chance = 100.0 * results[i] / numresults
pluschance = 100.0 * remaining / numresults
print "%d\t%d\t%0.02f\t%d\t%0.02f" % \
(i, results[i], chance, remaining, pluschance)
remaining -= results[i]
(results, numresults) = roll(2, 6)
printres(results, numresults)
This produces the same results in only a fraction of the time. It actually goes about the summing in a slightly less efficient manner than the paper that I was shown, but makes up for it by being less mysterious.
### The Results
How much faster is it?
When I mentioned calculating 10 10-sided dice last time I actually told a little lie. I didn’t actually bother running the test to the end. During the course of writing this entry I started it running and although I’m not using the fastest machine out there it took more than 2 hours to complete. This version can calculate those results in less than 0.02 seconds.
To be a bit more mathematical, the way the recursive solution is nesting `for` loops is O(s^n). This solution, however, is O(s*n).