A Mathematical Analysis of Exploding Dice

A Mathematical Analysis of Exploding Dice March 22, 2009

Posted by eric22222 in General, Math.
trackback

(Session 66 has been posted)

I’m guessing the title caught your eye? I wrote this essay a while back, but decided to hold off on posting it until I had my power cord back. So… here we go:

With a normal die roll, the result is either 1, 2, 3, 4, 5, or 6. This will later be generalized to N-sided dice, but for now, the standard six-sided variety will suffice. Some games (dice-based tactics games, usually) use a system called “exploding dice.” With this system, rolling the maximum value on a die allows the roller to roll the die again and add the new result to the previous one. There is usually no limit on the number of rerolls.

For example, a player rolls a six. He rerolls the die, which lands on six once again. Once more, he rolls, but this time gets a two. His final result for this roll is effectively fourteen, even though the die has only six faces $(6+6+2 = 14)$ .

Put simply, expected value is what the average result for an experiment would be if were tried an infinite number of times. For example, if a coin flip was worth one point if heads lands and two points for tails, the expected value would be 1.5 since heads and tails are equally likely.

To compute expected value, the sum of each possibility times its respective chance is taken. For the coin flip example, this would be $0.5 \times 1+0.5 \times 2$ . That is, a 50% chance of 1 point plus a 50% chance of 2 points.

So the problem to be tackled here today is this: how does the expected value of an exploding die differ from its standard expected value?

The first step will be to find a pattern. Here is a quick comparison of values and their respective probabilities:

x, Pr(x)
1, 1/6
2, 1/6
3, 1/6
4, 1/6
5, 1/6
7, 1/36
8, 1/36
9, 1/36
10, 1/36
11, 1/36
13, 1/216
14, 1/216
…

So how can these be put into an elegant formula? First of all, a simple sum of products will be used:

$\frac{1}{6} \times (1+ \ldots +5) + \frac{1}{36} \times (7+\ldots+11) + \frac{1}{216}(13+\ldots +17) + \ldots$

The factors preceeding each sum are powers of six, so they can be consolidated into a nested sum:

$\frac{1}{6} (1+2+3+4+5+ \frac{1}{6} (7+8+9+10+11+ \frac{1}{6} ( \ldots )))$

Each sum, such as $1+2+3+4+5$ , is equal to the average value times the number of elements. The number of elements remains a constant 5, but the average value is increased by 6 for each subsequent sum, beginning with a value of 3. The formula can now be rewritten like so:

$\frac{1}{6} (3 \times 5 + \frac{1}{6} ((3+6) \times 5 + \frac{1}{6} ( (3+12) \times 5 + \frac{1}{6}( \ldots ))))$

Simplifying some of the products, the formula can be rewritten once again:

$\frac{1}{6} (15 + \frac{1}{6} (15 + 5 \times 6 \times 1 + \frac{1}{6} (15 + 5 \times 6 \times 2 + \frac{1}{6} ( \ldots ) )))$

Now an obvious pattern begins to develop. By expanding these nested products, the pattern becomes even more clear:

$\frac{15 + 30 \times 0}{6^1} + \frac{15 + 30 \times 1}{6^2} + \frac{15 + 30 \times 2}{6^3} +\ldots$

Six is factored out of all terms:

$\frac{2.5 + 5 \times 0}{6^0} + \frac{2.5 + 5 \times 1}{6^1} + \frac{2.5 + 5 \times 2}{6^2} +\ldots$

This new formula can be rewritten in sumation notation:

$\displaystyle\sum_{N=0}^\infty \frac{2.5 + 5 \times N}{6^N}$

For each term added, our error will be reduced by a factor of 6, so just a few terms will return a very accurate result:

N, sum to N
0, 2.5
1, 3.75
2, 4.0972222
3, 4.178240741
4, 4.194058642
5, 4.197595165

The sum is swiftly approaching exactly 4.2, but what is the relation of that value to a six-sided die’s normally expected value?

$3.5x = 4.2$

$x = \frac{4.2}{3.5} = \frac{6}{5}$

Adding the exploding modifier to a six-sided die changes its expected value by a factor of $\frac{6}{5}$ . That is, the ratio of the number of sides on the die to the number of sides that do not “explode.”

I have performed the same calculations on four and eight-sided dice to compare results, and the forumla holds.

For any N-sided die numbered 1 to N with all sides equally likely, the exploding modifier will increase the die’s expected value by a factor of $\frac{N}{N-1}$ .

Interestingly enough, this formala holds for a hypothetical one-sided die. Heuristically, since the highest number will always be rolled, the total will constantly increase, returning an infinite result. Mathematically, the expected value of 1 will increase by a factor of $\frac{1}{0}$ , which approaches positive infinity from positive values.

This essay was written by Eric Dobbs, an undergraduate student of computer science at the University of Tennessee, Knoxville. He can be reached at erictdobbs -at- gmail -dot- com.

Like this:

One blogger likes this post.

Comments»

1. Johnny Angel - April 9, 2009: The Pathfinder Chronicles campaign setting sets some heavy restrictions on the user of firearms, what with chances to misfire, the need to have a special feat, penalties for different sized creatures and an obscene entry cost. The fact that these weapons do exploding damage might make up for this, but by this analysis, it doesn’t look like much of a difference.

But, a player might object, despite the vanishingly small probability at each iteration, there is at least some chance of blowing away a dragon with one shot. Okay. Well, in order to make an informed decision about that we would need to know for one thing what the chances even are of doing more than the maximum of the same damage roll that doesn’t explode. Is there a way to calculate that, or to calculate an expected maximum value?

Reply
2. eric22222 - April 10, 2009: Thanks for the comment, Johnny.

There’s a simple way to determine just how easily the result can explode. For a d6, you have a one in six chance of getting anything greater than 6; if you roll a natural six (one in six chance), you’ll add another roll.

The chance of it exploding a second time is a further one in six, so the chance of rolling higher than 12 is one in six to the second power, or one in thirty-six.

So the probability of rolling higher than x*N on a dN is N^(-x).

Reply
3. Exploding dice | Polymath Programmer - August 10, 2009: [...] then I had the brilliant idea of searching on the Internet. And I found Eric, who did an actual math analysis of exploding dice. Much better than my feeble attempt. I almost wanted to tear up all my calculations in shame. His [...]

Reply
4. Roman McLaze - November 2, 2009: Thank you for the great essay!

I’m fiddling with an exploding coin-based system (heads count as “hits”, and get one reroll as well), and you’ve made it much easier for me to figure out target numbers.

Reply
5. Math Brainteaser – Coin Flipping « Eric Online - November 11, 2009: [...] like to start with some data, then find a pattern. This is going to use expected value, too, so brush up on that if you need [...]

Reply
6. Michael - October 28, 2010: In the hope the author is still active…I have a question on the subject, how if the system your playing is built so that you if you roll a 6 have to pick it up, add another die and roll them together and if any of them is a six you do the same thing over, then the value of the two die could be lower than your first six, how would you calculate the average result of rolling 3 dices then? I myself calculated it to 10,66666 but i’m sceptical beacuse it’s very close to the “normal” average of 10,5.

Reply
eric22222 - October 28, 2010: Thanks for the question Michael.

If I’m reading your post right, the idea is that the player starts by rolling one die. If a six is rolled, the player discards the result and rolls two dice. If either of them is a six, the player discards that total and tries again with three, and so on.

Am I on the right track? I’ll see if I can come up with an answer sometime in the next bit, but let me know if you had some other system in mind for how this works.

Reply
7. Michael - October 28, 2010: Yes it’s how it works, the number of dice you throw in the beginning is based on the difficulty of the task but the normal is 3D6. And like you say if you roll a six you pick it up and roll 2 dice and so on.

But i guess the simpliest is to calculate for one dice and multiply that with 3. Thx for the help

Reply
8. Making Rolls | Bearded Dork - May 17, 2011: [...] meant in my discussion of Dice to explain why I don’t like exploding dice, I’ve had this prejudice since I first encountered it with the firearms rules of AD&D 2nd [...]

Reply
9. Fingers - May 26, 2011: I’m hoping the author is still active and can answer my question.

If, using a 6 sided die, all 1′s were rerolled, how would it affect the exploding dice result? And what would the average value now be for each die?

Reply
eric22222 - May 26, 2011: Thanks for the question. I’ve tried quickly recalculating things with only 1′s being rerolled, and the results are pretty awesome:

It doesn’t change the expected value at all!

This completely unintuitive, and I keep thinking of several reasons that this shouldn’t happen, but the numbers don’t lie. I’d guess the same would hold true regardless of which number explodes.

It’s hardly proof, but I’m in a rush right now, so this link will act as an explanation for now: http://tinyurl.com/3e5tsrc

Reply
10. Anthony - December 7, 2011: So what would the “exploding’ relationship be say if:

Dice still “exploded” on rolls of six but in addition, all 1′s were rerolled but not tallied towards the sum of the roll. Specifically I’m thinking of 4E’s “Brutal” mechanic.

For example, a player rolls a six. He rerolls the die, which lands on six once again. Once more, he rolls, but this time gets a one. He then rolls again getting a two. His final result being fourteen (6+6+2) not counting the 1 which is a reroll but does not count towards the sum.

(How) Does this relate compared to the standard die roll?

Reply
11. Eric - December 7, 2011: Anthony:

With 1s not being counted, you essentially have each die roll being from 2 to 6, rather than 1 to 6. So it’s like using a five-sided die, but adding the total number of rolls made to the sum. It would take a little number-crunching, but shouldn’t be too difficult to figure out what the expected value of that system would be.

I may go through that problem in more detail if time permits in the near future. Thanks for the comment!

Reply
12. Russ - December 16, 2011: Eric:

What would happen with Fudge dice? Consider two scenarios:

1) Uncancelled fudge positives explode. The probabilities for -4,-3,-2,-1, and zero should remain unchanged right? What about the right hand side of the distribution?

2) All positives explode. I don’t have any intuition as to what would happen.

I am interested in modifying Fudge to be unbound on the top end. I like the distribution being zero centered and bound on the lower end but want to skew the normal distribution to be more like a gamma distribution.

Reply
13. eric22222 - December 16, 2011: Russ:

On 1), the probabilities for some values seem like they’ll be the same, but zero becomes MORE likely. Consider getting -1, +1, +1, and +1. Your net value of 2 means 2 exploding dice, and a 1/3 ^ 2 chance of dropping back down to zero! (This is assuming I understand how this system works; I read through it pretty quickly and think I have the idea of it).

For 2), I _think_ it wouldn’t change anything on the expected value. Regardless of which numbers explode, this system has an expected value of zero. Even with positive values exploding, you have a chance of getting negatives just as easily. Granted, this does mean you have a slim chance of getting high positives, but you also have a higher chance for dropping your value a little bit.

Ah, I wish I had more time to crunch the numbers on this, and look into the exact values for 1)… Sorry I can’t give you a more though-out answer than that right now, but thanks for the question!

Reply
14. Russ - December 19, 2011: Thanks for your reply Eric. I will see if I can write a script to simulate both case 1 and 2 and plot the distributions.

Reply
15. Russ - December 19, 2011: Case 1:

def reroll(seed):
roll=randint(-1,1)
if roll==1: seed=reroll(seed+roll)
return(seed)
y=[(randint(-1,1),randint(-1,1),randint(-1,1),randint(-1,1)) for i in range(temptemp)]
z=dict((x,0) for x in range(-5,20))
for quartet in y:
current=sum(quartet)
foobar=current
while foobar > 0:
current=current+reroll(0)
foobar-=1
try: z[current]+=1
except: pass
summer=0
for i in range(-5,20):
print(i,’ >> ‘, z[i])
summer+=i*z[i]
print(‘mean = ‘,summer/temptemp)

-5 >> 0
-4 >> 12551
-3 >> 49539
-2 >> 122722
-1 >> 198097
0 >> 233946
1 >> 132184
2 >> 98732
3 >> 65732
4 >> 40320
5 >> 22953
6 >> 12045
7 >> 6019
8 >> 2846
9 >> 1298
10 >> 572
11 >> 251
12 >> 126
13 >> 39
14 >> 14
15 >> 11
16 >> 2
17 >> 1
18 >> 0
19 >> 0
mean = 0.32029

Case 2:

def reroll(seed):
roll=randint(-1,1)
if roll==1: seed=reroll(seed+roll)
return(seed)
y=[(randint(-1,1),randint(-1,1),randint(-1,1),randint(-1,1)) for i in range(1000000)]
z=dict((x,0) for x in range(-5,20))
for quartet in y:
current=sum(quartet)
for i in quartet:
if i == 1: current=current+reroll(0)
try: z[current]+=1
except: pass
summer=0
for i in range(-5,20):
print(i,’ >> ‘, z[i])
summer+=i*z[i]
print(‘mean = ‘,summer/1000000)

-5 >> 0
-4 >> 12154
-3 >> 49208
-2 >> 106949
-1 >> 159171
0 >> 181193
1 >> 165938
2 >> 128313
3 >> 86641
4 >> 52673
5 >> 29122
6 >> 14992
7 >> 7302
8 >> 3515
9 >> 1625
10 >> 660
11 >> 330
12 >> 125
13 >> 51
14 >> 30
15 >> 5
16 >> 0
17 >> 2
18 >> 1
19 >> 0

mean = 0.666231

Reply
16. Russ - December 19, 2011: realized I screwed up, reroll should return (seed+roll)

Reply
17. Russ - December 19, 2011: Case 1:
-5 >> 0
-4 >> 12386
-3 >> 49185
-2 >> 123586
-1 >> 198264
0 >> 316030
1 >> 98861
2 >> 53122
3 >> 49220
4 >> 29381
5 >> 23082
6 >> 14679
7 >> 10782
8 >> 7001
9 >> 5001
10 >> 3233
11 >> 2128
12 >> 1403
13 >> 955
14 >> 576
15 >> 392
16 >> 268
17 >> 167
18 >> 101
19 >> 60
mean = 0.316747

Case 2:
-5 >> 0
-4 >> 12315
-3 >> 65853
-2 >> 147959
-1 >> 188539
0 >> 163155
1 >> 118834
2 >> 89146
3 >> 65830
4 >> 46828
5 >> 32605
6 >> 22580
7 >> 15367
8 >> 10570
9 >> 7045
10 >> 4648
11 >> 3072
12 >> 2022
13 >> 1314
14 >> 801
15 >> 544
16 >> 344
17 >> 234
18 >> 132
19 >> 99
mean = 0.659422

Reply
18. Russ - December 19, 2011: Case 2 is a lot smoother at (0,1) I think I like it better. I just wish it would drop off faster.

Reply
19. Russ - December 19, 2011: I will get this right eventually. Should be:

def reroll(seed):
roll=randint(-1,1)
if roll==1:
roll=roll+reroll(0)
return(roll)

Reply
20. Russ - December 19, 2011: Case 1:

-5 >> 0
-4 >> 12298
-3 >> 48920
-2 >> 123273
-1 >> 198050
0 >> 315862
1 >> 133076
2 >> 79703
3 >> 44299
4 >> 23107
5 >> 11543
6 >> 5373
7 >> 2516
8 >> 1120
9 >> 499
10 >> 217
11 >> 63
12 >> 50
13 >> 21
14 >> 4
15 >> 4
16 >> 1
17 >> 1
18 >> 0
19 >> 0
mean = 0.00216

Case 2:

-5 >> 0
-4 >> 12491
-3 >> 65801
-2 >> 153794
-1 >> 211560
0 >> 202355
1 >> 150298
2 >> 95262
3 >> 54115
4 >> 28080
5 >> 13999
6 >> 6751
7 >> 3115
8 >> 1404
9 >> 571
10 >> 233
11 >> 98
12 >> 51
13 >> 11
14 >> 4
15 >> 7
16 >> 0
17 >> 0
18 >> 0
19 >> 0
mean = 0.001973

Reply
21. Chris - March 23, 2012: Thanks! This is great for determining the average, but how can you help me even further by telling me how I can use this (or other some other smarter-than-me-math) to determine the probability of a specific sum (or more) being rolled for a given dice pool of exploding dice? We know six exploding d4 will result in a sum of 20+ more often than four d6, but how can I determine the specific probability? Ultimately I’d like to be able to map these probabilities and compare them against different targets and numbers of dice in the pool so as to better understand the impact and effectiveness of lowering the target or adding a die (and vice versa).

Reply
22. Om hvordan jeg lærte å slutte å bekymre meg og omfavne spillressurser – Imagonem - April 3, 2012: [...] Exploding Dice: Noen spill bruker et system med “eksploderende terninger” – det vil si at om man ruller det høyeste mulige tallet på en terning, får man kaste om igjen og legge resultatet til totalen. Gitt uendelig hell, er derfor det teoretisk mulige høyeste resultatet på terningkastet uendelig stort. Se også: A Mathematical Analysis of Exploding Dice (Eric22222, 22.03.09) [...]

Reply

Eric Online