Slaying the dragon

Callum Ilkiw takes us through a Dungeons and Dragons dice dilemma

post

Against all the odds, your plan has worked. Your thief snuck in ahead of the team and got a surprise backstab, the paladin’s shield deflected the would-be deadly dragon’s fire breath and a well-aimed wizard’s frostbolt took out the columns of the building. You move your dwarven barbarian in for the killing blow. The trapped red dragon looks up with anger in its eyes. You know, all that stands between this creature and death is a single good hit of your axe. Even with all the work from the other players, the difficulty class of landing a hit on this creature is 16, meaning you will only hit it with a roll of 16 or higher on a d20 (a 20-sided die for those not in the know). That’s a $1/4$ chance of hitting.

Luckily, there is one last hope. The druid spent their turn giving you the help action. This means your next attack has advantage. Advantage allows you to now roll two d20s and choose the highest of those two values. This is obviously helpful, but what are the new odds that you will be able to give this dragon a one-way ticket to the afterlife?

Sure, the odds that anyone reading this has even found themselves in that specific situation are pretty low. But over the course of lockdown, many new players found themselves taking to the famous tabletop role-playing game Dungeons and Dragons, known to fans as ‘DnD’.

A d20 has faces numbered from 1 to 20. In this picture, a 2 has been rolled.

Whilst playing a typical weekly game of DnD, I had a similar situation to the one above. For anyone out there who has never played or watched a game of DnD, here is the main thing you need to know: almost every action in the game requires the roll of a 20-sided die to determine how well you did. This is called a skill check. Each of these skill checks has a difficulty class, which is the number you need to overcome to succeed in the roll. A higher difficulty class means the check is more difficult. For example, persuading a merchant to give you a discount might have a class of eight, but trying to stealthily steal his supplies would have a class of 20. A roll of 10 would pass the first case but fail the other.

In some cases, the player might also have a situational bonus to reflect what is happening around them. For example, sneaking past the merchant might be made considerably easier by having another player distract them. In the rules of DnD, this is called advantage. If, however, the situation is not in players’ favour, eg persuading a guard you insulted moments earlier, the player would have disadvantage. When applying advantage or disadvantage the player rolls two d20s instead of one. If the player has advantage, they take the highest of the two values shown. If the player has disadvantage, they take the lower of the two. The mathematically inclined may be wondering, how do your odds change when rolling with advantage or disadvantage?

A d4. As there is no face at the top, the number you have rolled is written around the top point.

Let’s start with a simpler version of this problem. The smallest die used in DnD is four-sided. When we roll two four-sided dice, there are 16 possible results:
$\begin{matrix}
& & & \\
(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).
\end{matrix}$

If you score the highest of the two rolled values, we can compute the following odds:

$n$ $P(\text{scoring $n$ with advantage})$
$1$ $1/16$
$2$ $3/16$
$3$ $5/16$
$4$ $7/16$

Hazarding a guess, it looks as if each score $n$ has $2n-1$ ways of getting it. Let’s check this makes mathematical sense.

Any pair $(a,b)$ will give a score of $n$ if at least one of $a$ or $b$ is equal to $n$ and the other is less than or equal to $n$. If $a=n$, there are $n$ possible options for $b$. If $b=n$, there are $n$ options for $a$. That’s $2n$ possible ways of getting $n$, but we counted the pair $(n,n)$ twice in those two lists, meaning the real number of ways to score $n$ is $2n-1$. So, when rolling advantage on a $y$-sided dice, the probability is given by $P(N=n)=(2n-1)/y^2$. When rolling with disadvantage, this becomes $P(N=n)=(2y+1-2n)/y^2$.

For a d20, in the case of advantage, this will give:

$n$ $P(\text{scoring $n$ with advantage})$
$1$ $1/400$
$2$ $3/400$
$3$ $5/400$
$4$ $7/400$
$5$ $9/400$
$6$ $11/400$
$7$ $13/400$
$8$ $15/400$
$9$ $17/400$
$10$ $19/400$
$11$ $21/400$
$12$ $23/400$
$13$ $25/400$
$14$ $27/400$
$15$ $29/400$
$16$ $31/400$
$17$ $33/400$
$18$ $35/400$
$19$ $37/400$
$20$ $39/400$

In the original scenario, our hero needed to roll a 16 or more, and only had a one in four chance of success. With advantage, the new odds of success become $(31+33+35+37+39)/400= 175/400$ or about 44%. While still not a likely win, the chances of success have gone from one in four to almost one in two.

With hope in their heart, the barbarian goes to swing down their axe, and you prepare to roll the two d20s in your hand. Wait!—your friend sitting next to you reminds you that your dwarven barbarian has the lucky feat. This feat allows you to roll three d20s and take the highest when rolling with advantage, instead of the pitiful two that most players would get.

Let’s see if we can take our probability equation for advantage and generalise it for any number of dice.

Generalisation

Generalisation is the inevitable step any maths problem reaches once the initial problem is solved. In this case, I want to extend our original problem to ask: If you rolled $x$ dice, each with $y$ sides, what is the probability of rolling any positive whole number $n$?

The problem now extends from one of probability to one of combinatorics. Combinatorics is best thought of as the study of how many ways you can combine a set of elements. In this problem, we can best express the result of the roll as a vector of scores $(n_1, \dots , n_x)$, where $f(n)=\text{max}(n_1,\dots , n_x)$ is the result of using advantage with $x$ dice. Each $n_i$ is drawn randomly, uniformly and independently from the set $(1,2,3,\dots,y-1,y)$.

There are many ways to begin a problem like this, but I like to start case-by-case.

When $n=1$, there’s only one way, all ones: $(1,1,1,\dots,1,1)$.

What about when $n=2$? There are $2^x$ ways to get only ones and twos in our roll, due to there being only two options for each of the $x$ slots. This answer includes the option of all ones that we’ve already counted, hence there are $2^x-1$ ways of scoring two.

And when $n=3$? This is achieved by any combination of all threes, twos and ones, excluding the combinations that don’t have any threes. This gives $3^x-(2^x-1)-1=3^x-2^x$ ways of getting a three.

There seems to be a general rule emerging, so let’s hypothesise that the number of ways to score $n$ is $f(n):=n^x-(n-1)^x$.

Proof by induction

For the base case, we select $n=1$: There is only one way of scoring one regardless of number of dice and $f(1)=1$.

Next, we assume that the number of way to score $k$ is given by $f(k)$ and show that our formula is also true for $n = k+1$. If this proposal holds for all values $k$ and lower, there are $(k+1)^x$ rolls that involve only numbers $k+1$ and lower. We also know that $\sum_{j=1}^k \left( j^x-(j-1)^x\right)=k^x$ of these contain no instance of $k+1$. Therefore, there must be $(k+1)^x-(k)^x$ ways of scoring $k$, which matches our hypothesis.

We have proven that when you roll $x$ dice with $y$ sides each, and take only the highest result, your odds of getting any score $n$ $(\leq y)$ is given by $P(n)=\left(n^x-(n-1)^x\right)/y^x.$

Now, this is a good step, but in DnD we are rarely concerned with getting an exact score. So, we can use this equation to find the probability of getting at least $n$ when rolling $x$ $y$-sided dice with advantage: \begin{align*} P\left(\text{at least }n\right) = \frac{1}{y^x}\sum_{j = n}^y\left(j^x -(j-1)^x\right)=\frac{y^x-(n-1)^x}{y^x}=1-\left(\frac{n-1}{y}\right)^x. \end{align*} I know what you’re all wondering, what does this mean for our barbarian? Well, when rolling normal advantage in DnD, we always use a d20, so that means $y=20$. This gives the equation of $P(\text{at least $n$}) =1 -((n-1)/20)^x $. Therefore, the odds of rolling more than 16 when rolling three d20s with advantage are $P(\text{at least 16})=1 -(15/20)^3=1-27/64=37/64=57.8\%$. This means that the odds of success are suddenly more than 50%.

You regather your composure and thank your friend for the advice. As you grip the three d20s in your hand, so too does your barbarian tighten his grip around the greataxe passed down through many generations of his bloodline. You roll a 6, an 11 and… a lucky 19 and slice the dragon in twain. This is a success. A success made easy with the help of combinatorial mathematics—the best kind.

How do you want to do this?

With the conclusion of this story so too comes the conclusion of this article. For those of you who play DnD, I hope this advice comes in handy during your next game and spares your hero from an untimely meeting with death. For those of you that have never played, maybe seeing the maths working behind the scenes has persuaded you to pick up some dice and try the game for yourself. Either way, I wish you the best of luck in your next quest. But be wary adventurers, here be dragons.

Callum is a maths graduate from both Keele and Warwick, with an interest in all things nerdy. From DnD to drama games, he likes to find the maths hidden away in plain sight.

More from Chalkdust