### Dice, probabilities, and Go - Part 1

A post on dmg42 got me thinking about damage rolls in D&D. The main point of the post was that in 4e, damage doesn't scale with the players' abilities to mitigate the damage. He makes a great argument for new damage rolls (with graphs!) but it got me thinking, how do I distinguish the damage brutes do vs lurkers? I wanted something a little more flexible with burstier damage so I figured I'd write an app to show how damage is distributed for different sets of dice. Other tools exist which do most of what I want but that would make for a boring project. So I'm working on a tool written in Go.

Why Go?

I went with go because 1) I've never used it, 2) someday I may want to use it seriously, and most importantly 3) it has the cutest mascot. I mean just look at it:

I have one on my shelf. This one is from someone else's shelf. |

Learning new languages is fun and I'll have a post on surprising features of Go sometime later, once I feel more comfortable with it. For the impatient, check out golang.org and play with it too.

Figuring out the math

I started with trying to see how specific die rolls are distributed. If I roll 1d6, well that's not very special but it makes for a good base case. 2d6 is more interesting and easy to spot check with other people's work online. Through a combination of Wolfram and Wikipedia articles I was able to mostly understand how to get at the value. Wikipedia gives a nice recursive formula for this:

So F

_{6,2}(7) is the percent of 2d6 rolls which total to 7, with F_{s,1}(k) = 1/s for k in [1, s] and 0 otherwise.
This approach worked really well for 3d6 but started being noticeably slow at 7d6 and noticeably wrong at 6d12 (using anydice.com as a reference). My best guess for the wrongness is that it's using a lot of floating point calculations with small values. As for being slow, I decided not to optimize until I had something that I felt was correct for large values. Still, I had something here which was reasonably good for smaller values. Go code below (you can paste it right into the code box at golang.org and run it yourself!)

package main import "fmt" func main() { printRolls_firstTry(6, 6) } func dieRolls_firstTry(sides, rolls, dieSum int) float64 { if rolls == 1 { if dieSum >= 1 && dieSum <= sides { return 1.0 / float64(sides) } else { return 0 } } sum := 0.0 for i := 1; i <= dieSum - rolls + 1; i++ { sum += dieRolls_firstTry(sides, 1, i) * dieRolls_firstTry(sides, rolls - 1, dieSum - i) } return sum } func printRolls_firstTry(sides, rolls int) { fmt.Printf("%dd%d rolls: \n", rolls, sides) maxValue := rolls * sides for value := rolls; value <= maxValue; value++ { fmt.Printf(" %2d %8.5f%%\n", value, dieRolls_firstTry(sides, rolls, value) * 100) } }

At this point I looked for a method which used only integer math or as close as I could get to that. From the same wikipedia page I found a formula which uses binomial coefficients for the same calculation. Cool! Binomial coefficients are always integer values so as long as I don't hit integer overflow it'll all be good.

I haven't seriously looked at 4e rules, and haven't read the linked post, but this reminded me of something a friend of mine in grad school (who now writes and designs role playing games, among other things) noticed while working out a dice system for one of their games:

ReplyDelete1) Imagine you're doing combat in your system by throwing

nd6, wheren>= 3.2) Your players will either need to make a certain fixed total to accomplish something (e.g. cast a spell correctly, detect something) or will need to roll better than some similar roll by the DM (e.g., parry a monster's attack).

3) Players may have advantages/disadvantages added to their roll (e.g. magical +3 sword)

Then, the surprising effect is that a +3 advantage against a moving target (player must exceed DM's roll) is about equal to a +2 advantage against a fixed target. Likewise, +6 against a moving target is about equivalent to a +4 against a fixed target, and this is more obvious when simulating truly huge numbers of dice. (Except that the ratio between a similar moving and fixed target approaches 1.414... (=sqrt(2))) Something else to look at.

(There's an elegant geometric explanation for this which I might sketch out next time I come hang out in NYC if you're interested)

Also, if you define N(s, n, k) == s^n * F(s,n,k), you get a nicer recursion relation: (in pseudo-python)

N(s, 1, k) == 1 if 1 <= k <= s else 0

N(s, n, k) == sum(N(s, n-1, k-i) for i in [1..s])

Note that this recurrence relation is all integer math.

4e rules remove lots of the opposed check type stuff and keeps the math the same between hitting moving targets vs non-moving targets, I'd be interested in finding out what ruleset your friend was looking at.

ReplyDeleteAs for changing the recurrence that does indeed fix it. Something to that effect was going to be in part two but you came to it much sooner than I had. :) I actually started from the binomial coefficient method, made it fast then tried this one.