Tabletop role-playing games and probability generating functions

Back to homepage

Tabletop role-playing games like Dungeons & Dragons and Pathfinder are as much about inventiveness and imagination as they are about throwing and adding dice. Any attack, action or reaction that requires some skill basically goes like this: throw the appropriate dice and add the results, apply bonuses and penalties, and check whether the resulting number is equal to or larger than some target - higher numbers are better.

For example, in Pathfinder , to attack a zombie with a shortsword, you would roll a twenty-sided die (called a $d 20$ ), add your Strength modifier and check whether it's equal or greater than 12. If it is, then you would roll a regular six-sided die (called a $d 6$ ) and add your Strength modifier to determine how much damage you deal.

Different weapons and characters will have different dice, modifiers, and choices involved in even a single action. But which action is "best"? Let's say you're offered two options: to roll either a single $d 8$ , or two $d 4$ s and add the results. Which would you pick, and why?

Your first approach might be to look at the average results of both options, known as the expected value of the two options - it's a weighted average for all the possible outcomes, where the weights are just the probabilities of the associated outcomes. (The expected value of a variable $X$ is written as $E [X]$ .) For the given options, these are: $\begin{matrix} E [d_{8}] & = & 4.5, \\ E [d_{4} + d_{4}] & = & 5 . \end{matrix}$ So rolling two four-sided dice is better than a single eight-sided die, right? Well, it depends. If we know that dealing 7 or 8 damage is required to slay the monster, then choosing the $d 8$ might be preferable, since that would make it more likely to slay the monster in a single action: $\begin{matrix} P (d_{8} \geq 7) & = & \frac{1}{4}, \\ P (d_{4} + d_{4} \geq 7) & = & \frac{3}{16} . \end{matrix}$ There is third way by which we might compare distributions of die rolls: we could say that one beats another when it is more likely that it lands higher than the other way around. In other words, we can check the probability of either roll being larger than the other. After crunching some numbers, this turns out to be: $\begin{matrix} P (d_{8} > d_{4} + d_{4}) & = & \frac{3}{8}, \\ P (d_{4} + d_{4} > d_{8}) & = & \frac{1}{2} . \end{matrix}$ Interestingly, this final method of comparison turns out to be "intransitive". In other words, you would expect that if A is better than B and B is better than C, than A would be better than C, but this is generally not true when comparing distributions in this way!

There are a bunch of different ways by which we can compare distributions, but before we can even compare distributions, we need a way to reliably determine them in the first place. A good approximation method would be the Monte Carlo method, which relies on performing a lot of independent random samples, and aggregating the results. This approach is for example used to calculate odds in poker. However, for our area of interest, we don't need approximations or simulations, we can simply create an exact method. We just need one concept from mathematics: the probability generating function.

Probability generating functions

Let's say we have some stochastic variable $X$ which can, with some distribution, randomly take some non-negative integer value (0, 1, 2, et cetera), then we define its probability generating function, as: $\begin{matrix} G_{X} (x) = \sum_{k = 0}^{∞} P (X = k) x^{k}, \end{matrix}$ which is a power series (a sort of infinite polynomial) where the exponents represent the possible values the stochastic variable can take, and their coefficients are simply the probability of taking that particular value. $x$ holds no real meaning - you shouldn't think of it as a function in which you will plug in values, but just as a fancy mathematical way to represent the distribution, which will turn out to be very convenient for certain operations.

For example, let's consider again $d_{8}$ and $d_{4} + d_{4}$ , their probability generating functions are, respectively: $\begin{matrix} G_{d_{8}} (x) = \frac{x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} + x^{7} + x^{8}}{8}, \\ G_{d_{4} + d_{4}} (x) = \frac{x^{2} + 2 x^{3} + 3 x^{4} + 4 x^{5} + 3 x^{6} + 2 x^{7} + x^{8}}{16} . \end{matrix}$ Another probability generating function that is quite illustrative is that of a variable that has a 100% probability to get a single specific value. The following probability generating function belongs to the "stochastic variable" that always equals three: $\begin{matrix} G_{3} (x) = x^{3} . \end{matrix}$ Probability generating functions have an interesting property, which is that for independent variables $X$ and $Y$ : $G_{X + Y} (x) = G_{X} (x) G_{Y} (x)$ , so we could have determined $G_{d_{4} + d_{4}} (x)$ by squaring the probability generating function for $d_{4}$ , and this works for any distributions! You can simply "add" the underlying stochastic variables by multiplying their probability generating functions!

Furthermore, we can create a mixture of two independent variables $X$ and $Y$ , by taking the weighted sum of their probability generating functions (assuming the weights are non-negative, and sum to 1). Hence, if $Z$ equals $X$ with probability $p$ and equals $Y$ with probability $1 - p$ , then: $\begin{matrix} G_{Z} (x) = p G_{X} (x) + (1 - p) G_{Y} (x) . \end{matrix}$ Using just these two facts, we can determine the exact distribution of combined dice results!

For a more a complicated example, consider the puzzle posed in the XKCD comic from earlier. Grabbing two arrows at random out of ten when five of them are cursed means there is a $\frac{2}{9}$ probability of not grabbing any cursed arrows (calculated through $5 * 4 /(10 * 9)$ ). The question is whether this corresponds to landing 16 or higher on $d_{6} + d_{6} + d_{6} + d_{4}$ ? Armed with our new tools, this becomes pretty easy! Simply determine the probability generating function, discard all terms with exponent 15 or lower, and sum their coefficients, which turns out to be exactly equal to $\frac{2}{9}$ !

Modeling attacks

With this new mathematical tool at our disposal, let's return to TTRPGs. When making an attack, one of three things can happen: you miss, you make a regular hit, or you make a critical hit. Whether you hit or not is based on a $d 20$ roll:

rolling a 1 means you miss, dealing zero damage;
rolling a 20 results in a critical hit, meaning you roll your normal damage two times and add the results to determine your damage. In some cases, lower rolls may already result in a critical hit, or you may have a higher multiplier. Pathfinder requires you to make a second $d 20$ roll to "confirm" the critical hit, where you only deal critical damage if this roll also hits, otherwise dealing regular damage;
for any other result, it depends on characteristics of the enemy you are attacking whether you hit or not.

In short, the weapon damage of a single attack can be described by the following probability generating function:

\begin{matrix} G_{attack} (x) = p_{miss} x^{0} + p_{hit} G_{hit} (x) + p_{crit} G_{crit} (x), \end{matrix}

where

p_{miss}

p_{hit}

, and

p_{crit}

are the probabilities of missing, hitting and critting respectively, and

G_{hit} (x)

and

G_{crit} (x)

are the probability generating functions for the damage distributions for regular hits and critical hits. Note that missing an attack is represented by

x^{0}

(the distribution with 100% chance of hitting zero). Higher level characters may make multiple attacks during a turn, to do so we just multiply their probability generating functions.

Consider a Pathfinder fighter with a +2 Strength modifier and +1 base attack bonus attacking a Zombie (Armor Class 12) with a shortsword (shortswords have a critical hit range of 19-20). First we need to determine probabilities and probability generating functions:

$p_{miss} = \frac{2}{5}$ , since 8 out of 20 rolls would cause you to miss (rolling a 9 would still make you hit the target due to the total +3 bonus on the attack roll);
$p_{crit} = \frac{1}{10} \cdot \frac{12}{20} = \frac{3}{50}$ , corresponding to rolling a critical threat and then confirming it, and;
$p_{hit} = \frac{27}{50}$ , which is the remainder;
$G_{hit} = \frac{1}{6} (x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}) x^{2}$ , which corresponds to a $d 6$ roll with the Strength modifier added to it;
$G_{crit} = {G_{hit}}^{2}$ , which means that if you land a critical hit, you roll damage twice.

Putting it all together, the probability generating function of the attack would look like this:

\begin{matrix} \frac{2}{5} + \frac{9}{100} x^{3} + \frac{9}{100} x^{4} + \frac{9}{100} x^{5} + ... + \frac{1}{300} x^{15} + \frac{1}{600} x^{16}, \end{matrix}

which, for example, shows there's a 1 in 600 chance of dealing 16 damage (corresponding to making a confirmed critical hit and rolling maximum damage twice:

p_{crit} \cdot \frac{1}{6} \cdot \frac{1}{6}

). If we want to consider the total damage dealt by two of these attacks, we simply square the probability generating function:

\begin{matrix} \frac{4}{25} + \frac{9}{125} x^{3} + \frac{9}{125} x^{4} + \frac{9}{125} x^{5} + ... + \frac{1}{90000} x^{31} + \frac{1}{360000} x^{32}, \end{matrix}

which similarly shows there is a 4 in 25 chance of dealing no damage at all, and a 1 in 360000 chance of dealing 32 damage for this particular example.

Implementation

Let's get programming! From a programmer's perspective, a probability generating function can simply be represented by an array of floating point numbers with addition and mixing defined as before. Assuming the indices of the entries in the array correspond to the exponents in the generating function, we can add two distributions by multiplying their probability generating functions as follows: /** * Adds two independent distributions */ function addDistributions(distribution1, distribution2) { const newLength = distribution1.length + distribution2.length - 1 let newDistribution = Array(newLength).fill(0) distribution1.forEach((outcome1, index1) => { distribution2.forEach((outcome2, index2) => { newDistribution[index1 + index2] += outcome1 * outcome2 }) }) return newDistribution } Here we go through every combination of exponents from both generating functions, and accumulate the results in the appropriate term. The worst-case time complexity of this approach is $O (m \cdot n)$ where $m$ is the length of distribution1, and $n$ is the length of distribution2.

For the earlier mentioned mixing of distributions, we require a helper method, since the arrays representing the generating functions we are mixing may not have the same length yet. That's what zipWithDefault takes care of: it iterates the pairs of entries of two arrays, yielding defaultValue in place of one of the two values in the pair belonging to the the shorter of the two arrays, once its values have been exhausted. Using it, we can easily implement mixing: /** * Used to zip two arrays, if either array runs out of elements before the * other, its elements are replaced by defaultValue. */ function zipWithDefault(array1, array2, defaultValue) { return Array.from(Array(Math.max(array1.length, array2.length)), (_, i) => [array1[i] || defaultValue, array2[i] || defaultValue]) } /** * Mixes two independent distributions by sampling from distribution1 with the * given probability, and sampling from distribution2 with 1-probability. */ function mixDistributions(distribution1, distribution2, probability) { return zipWithDefault(distribution1, distribution2, 0).map(outcomes => probability*outcomes[0] + (1-probability)*outcomes[1]) } And that already wraps up the main logic! We can go one step further by defining some helper functions for convenience, to allow us to easily generate uniform distributions, "constant distributions" (like the distribution that yields 3 in 100% of the cases), and a way to multiply distributions (which is just repeated addition): /** * Used to generate the distribution of a regular die. Each outcome is * equiprobable, with a probability of 1/numberOfSides of occurring. Since * counting starts at 0, the first outcome has probability 0 of occurring. */ function die(numberOfSides) { return [0, ...Array(numberOfSides).fill(1/numberOfSides)] } /** * Used to generate the distribution for sampling the given value with * certainty. */ function constant(value) { return [...Array(value).fill(0), 1] } /** * Add multiple independent identically distributed distributions */ function multiplyDistribution(distribution, number) { if (number == 0) return constant(0) if (number == 1) return distribution return addDistributions(distribution, multiplyDistribution(distribution, number-1)) }

All that remains is combining it into a nice UI, and we have a blazingly fast exact distribution calculator!

The worst-time complexity of addDistributions can be improved by using the fast Fourier transform, though the given implementation is already fast enough for our purposes.

The worst-time complexity of multiplyDistribution can also be improved. We're doing number-1 power series multiplications (i.e. addDistributions calls), which are pretty expensive. We could utilize binary exponentiation to greatly reduce the number of required multiplications (its the sum of number of 1s in the binary expansion of number and the length of the binary expansion minus two). The key insight is that taking a square is also just a single multiplication, such that, for example, the number==16 case can be calculated with just four multiplications instead of fifteen. The actual minimal number of multiplications for a given exponent is obtained through so called addition-chain exponentiation, but finding the optimal way turns out to be way harder than just doing binary exponentiation.

Damage distribution calculator

Below you will find a tool that uses the above approach to determine the damage distribution of specific attacks.

Attacks

Damage dice can be specified as sums of dice, e.g. $3 d 6 + d 4 + 2$ . The extra damage dice represent the dice that are not multiplied by critical hits, they are added after the crit multiplier is applied, and are specified in the same format as the normal damage dice. I.e., when a roll hits the critical hit range or higher, a critical hit is scored, multiplying the damage dice, but not the extra damage dice. A critical hit range of 21 represents not being able to score critical hits with that attack.

Require confirmation rolls for critical hits

The following bonuses are added to all attacks:

Attack bonus Damage dice Extra damage dice

Attack			Critical hit
Attack bonus	Damage dice	Extra damage dice	Range	Mult.	Conf. bonus

Enemy statistics Armor class Damage reduction Miss chance Immune to critical hits

Output

\begin{matrix} E [X] & = \\ var (X) & = \end{matrix}