Archive for February, 2008

Dice Rolling

Thursday, February 28th, 2008

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.