Posts Tagged ‘dice’

Infinity Dice Rolling Engine

Thursday, June 19th, 2014

The miniatures game Infinity has some interesting and unique mechanics. The first is that the player who is not currently taking their turn gets to have their models react to the actions of the active player. The second mechanic is that if the action and reaction are directly opposed (for example, the two models are firing at one another), both players roll dice at the same time (called a Face to Face roll). The player who scores “better” wins the contest and their models performs the action.

Let’s take a very simple case of two basic infantry troops shooting each other. The active model is he Fusilier Angus, firing his Combi Rifle with Ballistic Skill (BS) of 12. This weapon lets him roll 3 20-sided dice, which will succeed on a roll of his BS of 12 or less on each die. His opponent is the Zhanshi Wen Liu, firing his Combi Rifle with BS 11. As he is reacting, he only gets a single die, and his BS is lower, so he is looking to roll an 11 or less. They both roll their dice at the same time, and then compare results. First, any dice that missed (rolled above the firer’s BS) are discarded. Then, any successes that rolled lower than the opponent’s highest die are discarded. This leaves at most one player with any successful hits, which are then applied to the target. There are a few more complexities, but this outlines the basic flow. To make it concrete – Angus rolls a 15, 10, and 7, and Wen Liu rolls a 9. Angus’s 15 is discarded as a miss (since he rolled greater than 12), and his 7 is discarded since it is lower than Wen Liu’s 9. Meanwhile, Wen Liu’s 9 is discarded since Angus rolled a 10. The only die left is Angus’s 10, meaning he scored one hit on Wen Liu.

In this basic case, the probabilities are relatively easy to calculate. For each of the active player’s dice, it is easy to calculate the chance that they rolled less than or equal to their target, minus the chance that their opponent rolled higher without going over their own target value. And in fact, there has long been an online tool called Infinity Math to help calculate probabilities where the reactive player is limited to one die.

The calculations get much more complicated when the reactive model is allowed to roll multiple dice. I attempted for some time to come up with a reasonably simple numerical way of calculating these chances, but kept on coming up short. Eventually, I remembered that my personal strengths are not in numerical analysis, but rather in computational and algorithmic optimization. Therefore, I decided to make a program which implements a really simple and straightforward means of calculating these probabilities, and then optimize it until it was acceptably efficient.

Basic Design Overview

The basic design of my dice rolling engine is to enumerate every possible permutation of dice that could be rolled, evaluate the results, and then calculate how likely each possible result is. Since the number of dice required can change for every scenario, my program implements this step using recursion. This allowed me to produce accurate results, but very slowly. Even a moderately complex calculation could easily take several minutes to complete. As such, looked for ways to optimize the algorithm to reduce the time taken.

Optimization – Matrix Symmetries

The first and biggest optimization that I implemented that decreased my running time by several orders of magnitude was to take advantage of symmetries in the matrix of all dice rolls I was generating. In other words, I made sure I never calculated results that varied only by the order of the numbers rolled.

Take this matrix showing all possible combinations of two four-sided dice as a simplified example:

(1,1) (1,2) (1,3) (1,4)
(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)
(4,1) (4,2) (4,3) (4,4)

Because a player doesn’t care what order they rolled their dice in (since all dice are rolled simultaneously), we can cut the number of dice rolled approximately in half, by including only those rolls where the second number is greater than or equal to the first.

(1,1) (1,2)*2 (1,3)*2 (1,4)*2
      (2,2)   (2,3)*2 (2,4)*2
              (3,3)   (3,4)*2
                      (4,4)

As you can see, the second matrix doesn’t have any duplicate entries, but does mark the ones that need to be double-counted. As the number of dimensions increases, the multiplicative factor can become much larger than 2, based on the number of repeated values.

As the number of dice increases, so do the number of dimensions of the matrix. In these higher-dimension matrices, the savings from matrix symmetries increase exponentially.

DicePermutationsAfter OptimizationPercentage
12020100%
240021052.5%
38000154019.25%
416000088555.35%

And so forth.

Optimization – Miss Consolidation

The great thing about that optimization is that it always works, no matter what the scenario. The next one I did, however, helps in most common cases, but will occasionally offer little to no benefit.

Since all dice that roll higher than the target number are discarded without being used, it is unnecessary to roll all of them. I let the first failing die through in order to count it in the statistics for failures and misses, and I simply multiply the number of results by how many other failure states I rolled up. From the initial example of Fusilier Angus trying to roll a 12 or less, this:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Becomes this:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 8

Obviously, the lower the target numbers involved, the greater the value of this optimization. Due to the way that this optimization stacks with the prior one, it frequently reduces the number of rolls calculated by well more than half.

Optimization – Multithreading

The final optimization I implemented was to make the tabulating of dice rolls multi-threaded. I start one thread for each of the 20 possible values of the first die, and then tabulate the results when all threads have completed. My hosting company gives me access to 2 CPU cores, so the calculation takes approximately half as long to complete. Due to the various optimizations in the prior sections, different threads will take different amounts of time to complete, but how the operating system balances them between the cores evens everything out.

Web App

With that done, I had the time consuming part of the calculations taken care of. The next step was to create a web frontend that allows you to select what sort of scenario you would like to run, and then hands the data off to the back end utility. This has been another significant challenge, but has overall been pretty straightforward. My tool is available here, for you to play around with if such things interest you. I periodically update it with new features and to keep it up-to-date with the latest releases for the game.

Prologue – Numerical Analysis

After I had already mostly completed work on this part of my tool, one of my fellow Infinity players from Maryland took the time to find a solution to this that is as close to closed-form as possible, using Mathematica and my tool to check his results. His description of his method is available in HTML or PDF, if you are interested.

Dice Rolling 2

Saturday, March 1st, 2008

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.

pipsways
11
21
31
41
51
61

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 pipsold pipsnew pips
211
321
431
541
651
761

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 pipsold pipsnew pips
312
422
532
642
752
862

Then I add the charts from rolling 1 and 2 and count the number of ways I can get each number.

total pipstotal ways
10
21
32
42
52
62
72
81

I’ll do the whole thing again for a three. Possible outcomes:

total pipsold pipsnew pips
413
523
633
743
853
963

And add it to the running count of new possibilities:

total pipstotal ways
10
21
32
43
53
63
73
82
91

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 pipstotal ways
10
21
32
43
54
65
76
85
94
103
112
121

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).

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.