# Rolling Dice

May 30, 2020

Let’s talk dice. I was reading this blog post, and in it the author asks a simple question. If he rolls 1 dice, and his son rolls 2 dice, then what is the probability that his roll will beat his son’s roll. The solution proposed was to narrow the scope based on the criteria of beating the opposing roll. For example, if my opponent rolls a 5 with 2 dice, then how many ways can I beat a 5 with a single die? The only way is with a 6. This is better than enumerating every possible scenario which is also proposed, but immediately discarded. Definitely a fun post, and you can read it here at DataGenetics.

This got me thinking. Is there another way to do this sort of calculation without having to manually enumerate each probability even when the scope is narrowed? Moreover, what would a general solution to this problem look like? For any number of dice rolled by person A, and for any number of dice rolled by person B what is the probability that the roll of person A will beat the roll of person B? I’ll be following the same rules as in the linked article where a win means to have a higher sum. For example, if I roll 2 dice, and my opponent rolls 3 dice what are my chances of having a higher sum. This led me to a sub-problem of for any number of dice rolled how many possible ways can I roll a given number? For example, if I roll 5 dice, then how many ways can the number 23 come up.

## Research

The first thing I found was a post on math.stackexchange asking exactly the question I wanted answered. How many ways to roll n with any number of dice. The lone answer to which pointed to something called a generating function for the solution. A generating function or series being a, usually better, way to express an infinite series or in this case even a partial series.

$(x+x^2+\cdots&space;+x^6)^m=x^m&space;\left(\frac{1&space;-&space;x^6}{1-x}&space;\right&space;)^m$

The second(not really second) post I found was a little more specific, but one of the answers to the post was also greatly expanded. Focusing on 3 doce rolled to a sum of 13. The expanded explanation rewrote the generating function by using something called a binomial series. The important bit here is the ability to rewrite our generating function into something a little more malleable with the following:

$(1&space;+&space;x)^\alpha&space;=&space;\sum_{k=0}^{\infty&space;}&space;\binom{\alpha}{k}&space;x^k$

Which when worked through ended with:

$[xS]g(x)=\sum_{j=0}^{&space;\lfloor&space;\frac{&space;S&space;-&space;3}{6}&space;\rfloor}&space;(-1)^j&space;\binom{3}{j}&space;\binom{S&space;-&space;1&space;-&space;6j}{2}$

Now, this is specific to 3 dice being rolled with 6 sides. Rewritten generally it is:

$[xS]g(x)=\sum_{j=0}^{&space;\lfloor&space;\frac{&space;sum&space;-&space;dice}{sides}&space;\rfloor}&space;(-1)^j&space;\binom{dice}{j}&space;\binom{sum&space;-&space;1&space;-&space;sides*j}{dice&space;-&space;1}$

An excellent, and vastly expanded article that I found which explains, and confirms the above is here: https://www.lucamoroni.it/the-dice-roll-sum-problem/. In it he dives deep into this problem, and links to yet another wonderful resource: https://mathworld.wolfram.com/Dice.html. He also points out one more thing worth mentioning. $\binom{\alpha}{k}$ is a notation for the number of combinations and can be prounounced “α choose k”. Which is calculated as:

$C(\alpha&space;,&space;k)&space;=&space;\binom{\alpha}{k}&space;=&space;\frac{\alpha&space;!}{&space;k!&space;(\alpha&space;-&space;k)!}$

With this I have everything I need to move forward including a generalized function for the calculation, and a basic understanding of what is going on, and how it was derived.

## Let’s write a program

As I’ve previously mentioned there are kind of two parts to this problem. The first is the subproblem of figuring out the number of ways to rolls a given number of dice. The second is to use that to calculate the probabilities we want to know. I’m going to expand the problem a bit to include the probability of both losing, and tying in addition to winning a given die roll. As such I’ll end up with a waystoroll function, and a collection of probability functions Pwin, Ptie, and Plose. Now for a little bit of design.

Note: D1 is person 1, and D2 is person 2.

1. D1 wins against D2 if for any result D2 rolls that D1 rolls higher.
2. D1 ties with D2 if for any result D2 rolls that D1 rolls the same.
3. D1 loses against D2 if for any result D1 rolls lower.

Rewritten with having to write this with code in mind gives the following.

Note: waystoroll(sum) will be a function that finds the number of possible ways to roll a given sum.

Tie: D2 rolls dice#(min)…dice#sides(max) Multipled by D1 rolls dice#(min)…dice#sides(max)

Wins: For all dice rolls of D2, then D1 rolls all sums where sumD1 > sumD2. Foreach call of waystoroll(sumD2), then multiply by combined waystoroll(D1) for all sumD1 > sumD2.

Loses: For all dice rolls of D2, then D1 rolls all sums where sumD1 < sumD2. Foreach call of waystoroll(sumD2), then multiply by combined waystoroll(D1) for all sumD1 < sumD2.

## Code

### WaysToRoll

To code the WaysToRoll function we are going need a couple parts first. A way to compute combinations, and for combinations a way to compute the factorial.

public static BigInteger Factorial(int num)
{
BigInteger sum = 1;
for (int i = 1; i <= num; i++)
{
sum *= i;
}
return sum;
}
public static decimal Combinations(int n, int k)
{
BigInteger a = Factorial(n);
BigInteger b = Factorial(k);
BigInteger c = Factorial(n - k);
return (decimal)(a / (b * c));
}

Ended up going with BigInteger because the numbers can quickly become very large.

public static decimal WaysToRoll(int sum, int dice, int sides)
{
var kMax = (int)Math.Floor((double)(sum - dice) / sides);

decimal total = 0;
for (int k = 0; k <= kMax; k++)
{
total += (decimal)Math.Pow(-1, k) * Combinations(dice, k) * Combinations((sum - sides * k - 1), (dice - 1));
}

}

I tested the WaysToRoll function with the sum 31 from 10 dice problem from https://www.lucamoroni.it/the-dice-roll-sum-problem/. Along with a couple other smaller test cases. Now with the function doing the bulk of the work out of the way let’s move on to probabilities.

### Probabilities

Note: The sums of the below probabilities will sum up to 1.

#### Win

public static decimal ProbabilityToWin(int d1, int d2, int sides)
{
decimal prob = 0;
int min = d2;
int max = d2 * sides;
for (int i = min; i <= max; i++)
{
var waysToRollD2 = WaysToRoll(i, d2, sides);
decimal waysToRollD1 = 0;
for (int j = d1 * sides; j > i; j--)
{
waysToRollD1 += WaysToRoll(j, d1, sides);
}
prob += waysToRollD1 * waysToRollD2 / (decimal)Math.Pow(sides, d1 + d2);
}
return prob;
}

#### Lose

public static decimal ProbabilityToLose(int d1, int d2, int sides)
{
decimal prob = 0;
int min = d2;
int max = d2 * sides;
for (int i = min; i <= max; i++)
{
var waysToRollD2 = WaysToRoll(i, d2, sides);
decimal waysToRollD1 = 0;
for (int j = d1; j < i; j++)
{
waysToRollD1 += WaysToRoll(j, d1, sides);
}
prob += waysToRollD1 * waysToRollD2 / (decimal)Math.Pow(sides, d1 + d2);
}
return prob;
}

#### Tie

public static decimal ProbabilityToTie(int d1, int d2, int sides)
{
decimal prob = 0;
int min = d2;
int max = d2 * sides;
for (int i = min; i <= max; i++)
{
var waysToRollD2 = WaysToRoll(i, d2, sides);
var waysToRollD1 = WaysToRoll(i, d1, sides);
prob += waysToRollD1 * waysToRollD2 / (decimal)Math.Pow(sides, d1 + d2);
}
return prob;
}

And that’s that. With these three functions I can now find for any number of dice d1, and for any number of dice d2 with any number of sides the probability that d1 will beat, tie, or lose to d2.

### Cache and Testing

Now something I noticed was that the same calculation was being made many times throughout the run of the program. This can be improved through a cache or memoization. I’m not going to post the code directly in this post as it is not significantly different from the above, but if you want to take a look you can find it here at my github. The important bit is this.

var prevCalc = new Dictionary<int, Dictionary<int, decimal>>();

It’s a dictionary of dictionaries where the first key is the sum or target currently being looked for, and the second key is the number of dice being rolled. The value stored is the number of ways that sum can be rolled with that many dice.

Just for fun, and to confirm it was working as expected I ran some tests with a stopwatch. For lower numbers of dice i.e. 3 the cache seemed to slow down the program a bit. However, for slightly bigger numbers of dice i.e. 30 the cache significantly improved performance.

## Checking my work

### Against the original problem 1 vs 2 dice

win - 9.26% lose - 83.80% tie - 6.94%

The winning percentage here matches the solution found in the datagenetics article.

### 1 v 1 dice

I would expect fairly even odds here, and it is easy to check manually.

win - 41.67% lose - 41.67% tie - 16.67%

## Questions

With all of this said, and done I’m still not really happy with the result. There are a lot of nested for loops in this program. Is there a better way to go about making these calculations? One of the loops that is bugging me is the loop to calculate factorials. Is there a way to do this without a loop? Apparently, there is stirling’s approximation which approximates the value of a factorial. However, it seems too imprecise to be useful. Another problem I noticed was that for large numbers of dice i.e. 150 the program runs into an overflow error where it says the decimal type can’t hold the number. To make the program more robust it might be worth looking into how to handle very large numbers with something other than a BigInteger type. A lot of math was used in this program. Is there a mathematical expression for the above program. For this question I tried my hand at it below.

### Ways to Roll

$Kmax&space;=&space;\left&space;\lfloor&space;\frac{sum&space;-&space;dice}{sides}&space;\right&space;\rfloor$ $W(sum,dice,sides)&space;=&space;\sum_{k=0}^{Kmax}&space;(-1)^k&space;\binom{dice}{k}&space;\binom{sum&space;-&space;sides*k&space;-1}{dice&space;-&space;1}$

### Probabilities

$P_{tie}(d1,&space;d2,&space;sides)&space;=&space;\sum_{i=d2}^{d2*sides}&space;\frac{w(i,d2,sides)&space;*&space;w(i,d1,sides)}{sides^{d1+d2}}$ $P_{lose}(d1,&space;d2,&space;sides)&space;=&space;\sum_{i=d2}^{d2*sides}&space;\frac{w(i,d2,sides)&space;*&space;\sum_{j=d1}^{i}&space;w(j,d1,sides))}{sides^{d1+d2}}$ $P_{win}(d1,&space;d2,&space;sides)&space;=&space;\sum_{i=d2}^{d2*sides}&space;\frac{w(i,d2,sides)&space;*&space;\sum_{j=d1*sides}^{i}&space;w(j,d1,sides))}{sides^{d1+d2}}$

Written by Carl Lloyd. He spends his time playing with technology, and learning new things.