To start with, I am going to retell the tale of some dice rolling statistics I spent time calculating circa October 2006. My demonstration code is in Python, because it’s fairly legible even if you aren’t familiar with it.
### Intro
I like to play games, and playing games often requires one to roll dice. In Warmachine, in particular, one rolls a number of six-sided dice, sums the values together, and checks if the total is greater or smaller than another number. I found myself wondering one day how different numbers of dice affected the probability of reaching (or exceeding) certain sums.
### Trivial Solution
In the case of Warmachine, one most often rolls two dice, sometimes rolls three dice, and rarely rolls four dice and then adds the values together. Let’s make a quick test program to use `for` loops to make a chart of outcomes for two six-sided dice to demonstrate where this is going:
#!/usr/bin/python
def roll():
# make results array for how many outcomes there are
results = [0] * 13
numresults = 0
for i in range(1, 7):
for j in range(1, 7):
# mark that we found one more way of getting i+j
# and that we have made one more combination
results[i+j] += 1
numresults += 1
return (results, 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()
printres(results, numresults)
The output looks like this:
N #N %N #N+ %N+
0 0 0.00 36 100.00
1 0 0.00 36 100.00
2 1 2.78 36 100.00
3 2 5.56 35 97.22
4 3 8.33 33 91.67
5 4 11.11 30 83.33
6 5 13.89 26 72.22
7 6 16.67 21 58.33
8 5 13.89 15 41.67
9 4 11.11 10 27.78
10 3 8.33 6 16.67
11 2 5.56 3 8.33
12 1 2.78 1 2.78
The `N` label means the number being rolled. `#N` is the number of ways that number may be rolled. `%N` is the chance of that number being rolled. `#N+` and `%N+` are the number of ways and percentage chance of rolling a value equaling or exceeding `N`.
As you can see, this method is fairly simple, but the use of nested `for` loops to control how many dice I’m rolling is very restrictive. For the particular scenario I have outlined, I could have gotten away with nesting four loops and ignoring the ones I didn’t need, but that would have been an inelegant solution. I wanted something general.
### OK Solution
I quickly came up with an obvious solution to the problem of needing variable numbers of nested loops – recursion. As this section’s title might suggest, it was not the ultimate solution, but it more than solved the initial problem.
Let’s update and clean the code a bit so that it is rolling `n` `s`-sided dice.
#!/usr/bin/python
def _roll_recursive(n, s, r, results):
numresults = 0
for i in range(1, s+1):
if n == 1:
results[r+i] += 1
numresults += 1
else:
numresults += _roll_recursive(n-1, s, r+i, results)
return numresults
def roll(n, s):
# roll n s-sided dice
# make results array for how many outcomes there are
results = [0] * (n * s + 1)
numresults = _roll_recursive(n, s, 0, results)
return (results, 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)
It’s not much longer (only 4 lines, and those are mostly function definitions and some associated whitespace), and it takes the number and sides of the dice as arguments. The output is the same as that for the trivial solution above. Let’s have it roll 3 dice and see what that looks like.
N #N %N #N+ %N+
0 0 0.00 216 100.00
1 0 0.00 216 100.00
2 0 0.00 216 100.00
3 1 0.46 216 100.00
4 3 1.39 215 99.54
5 6 2.78 212 98.15
6 10 4.63 206 95.37
7 15 6.94 196 90.74
8 21 9.72 181 83.80
9 25 11.57 160 74.07
10 27 12.50 135 62.50
11 27 12.50 108 50.00
12 25 11.57 81 37.50
13 21 9.72 56 25.93
14 15 6.94 35 16.20
15 10 4.63 20 9.26
16 6 2.78 10 4.63
17 3 1.39 4 1.85
18 1 0.46 1 0.46
There we go. Just in case you ever wondered, you have a 0.46% chance of rolling boxcars on three dice.
As stated above, this solution was more than enough to generate all the tables I could have ever wanted for playing Warmachine. However, by this point I no longer had gaming on my mind. I wanted to play around a little, and generate all sorts of weird tables. For example, I wanted to see what the various probabilities looked like if I rolled ten ten-sided dice.
What I found was that it took several minutes to calculate. Now, Python is a very slow language. I gained some ground by rewriting my solution in C, but I still had a fundamentally slow algorithm. It was some time before I had a better solution, which will be discussed in the next post.