Probability – Calculating the Chance of Defeating a Dragon with a 20-Sided Die in One Turn

algorithmsgamesprobability

In math class we were asked an optional problem I can't solve on my own:

You are fighting a dragon with 250 hit points and are rolling a 20 sided die to deal damage. The dragon takes damage equal to the number rolled on the die with 2 exceptions: If you roll a 20 you deal no damage (dragon is immune to critical damage) and if you roll a 1 you break your combo and the dragon kills you immediatly. You roll until the dragon is defeated or you roll a 1 and break your combo. What is the probability of defeating the dragon?

My mathematical approaches included calculating the expected damage per roll $$ E_{ w }= \frac{ \sum_{ n=2 }^{ w-1 }{ n } }{ w } $$ where $$ E_{ 20 }= 9.45 $$ and then tried calculate the probability of not failing in the minumum number of rolls required to defeat the dragon but in the end that led me to a probability so low anyone would consider it 0 and didn't seemed right to begin with.

I did understand that the problem is a lot more complex than it seems, since the probability changes drastically with the number of rolls before any other roll and their results.

Through empirical testing with a small python program, the probability of winnng came out to be only about 25%, which surprised me, given the chance of dealing damage is 90%.

How would you correctly tackle the problem and even leave it "parameterized" so the HP of the dragon and number of sides on the die could be changed?

Best Answer

Your suggestion to solve a general version of the problem is spot on. Let's set this up.

The die has two special outcomes: "death," which terminates the process, and 0, which has no effect. We might as well remove the 0, creating a "truncated die" of 19 sides. Let the probability that the die shows up a numeric value $\omega$ be $p(\omega)$ and let $p_{*}$ be the probability of death. $\Omega$ is the set of all these possible numeric values (not including "death," which is non-numeric).

You aim to reach a total of $T$ before observing "death." When $T\le 0,$ you have achieved this threshold, so the chance of winning is $1.$ Otherwise, when $T \gt 0,$ partition the event "eventually I win" into the separate numbered outcomes occurring within $\Omega.$ It is an axiom of probability that the chance of this event is the sum of the chances of its (non-overlapping) components.

$$\Pr(\text{Reach } T) = \sum_{\omega\in\Omega}p(\omega) \Pr(\text{Reach } T-\omega).$$

This recursion can be carried out with a simple form of a dynamic program. Unless the values and probabilities are very special, you can't hope to write a nice closed formula for the solution. You just have to carry out the calculation by computing the values for $T=1,$ $T=2,$ etc., in order. (This is called "eliminating tail recursion" in computer science.)

The number of calculations performed by this algorithm is proportional to $T$ times the number of unique values on the truncated die. That makes it effective for moderately large $T$ and realistic dice.

By means of such a program (using double precision floating point) I find the chance of reaching $T=250$ is $0.269880432506\ldots.$

As a reality check, you expect to deal about 9.5 damage points per roll, suggesting it will take about $250/9.5 \approx 27$ rolls to win. But on each roll there is a $1-1/20$ chance of surviving, so your chance of surviving by then is $$(1-1/20)^{27} = \left[(1-1/20)^{20}\right]^{27/20} \approx \exp(-27/20) = 0.25924\ldots.$$

That's pretty close to the answer I obtained.

As another reality check, that's also close to your simulation results. Indeed, I obtain comparable simulation results: they do not differ significantly from the exact answer.

I leave it to you to write the program. It will require a data structure that can store all the values of $\Pr(\text{Reach } T-\omega)$ given on the right hand side of the formula. Consider using an array for this, indexed by the values $0,1,2,\ldots, T.$

BTW, there are other solution methods. This problem describes a Markov Chain whose states are the total values that have been reached (from $0$ through $T,$ since anything larger than $T$ might as well be combined with $T$), along with a special (absorbing) "death" state. This chain can be analyzed in terms of a large matrix (having $250+2$ dimensions). As a practical matter this formulation isn't worth much, but the theory of Markov Chains provides insight into the process. You can mine that theory for information on your chances of winning and on how many rolls it is likely to take you to win if you do.

Yet another approach was suggested in a comment to the question: exploit a geometric distribution. This refers to analyzing the process according to how many rolls you will have before dying. To deal hit points, imagine rolling the die, with its "death" face removed parallel with flipping a (biased) coin, whose function is to determine whether you die. (Thus, in the situation of the question, each of the 19 remaining sides of the die--including the $0,$ which must be left in--has a $1/19$ chance; more generally, the side with value $\omega$ has a chance $p(\omega)/(1-p_{*}).$) The two sides of the coin are "death" (with probability $p_{*}$) and "continue" (with probability $1-p_{*}$). At each turn you separately roll the truncated die and flip the coin, accumulating hit points until you reach the threshold $T$ or the coin turns up "death."

A simplification is available, because it's easy to work out the chance of never flipping "death" in the first $n=0,1,2,\ldots$ turns: it equals $(1-p_{*})^n$ because all the flips are independent. Formally, this describes a random variable $N$ whose value equals $n$ with probability $p_{*}(1-p_{*})^{n}.$ (This is a geometric distribution).

To model the rolls of the truncated die, let $X_1$ be its value in the first roll, $X_2$ its value in the second roll, and so on. The sum after $n$ rolls therefore is $S_n = X_1 + X_2 + \cdots + X_n.$ (This is a random walk.) The chance of reaching the threshold can be computed by decomposing this event into the countable infinity of possibilities corresponding to the number of rolls needed. The basic rules of conditional probability tell us

$$\Pr(\text{Reach }T) = \sum_{n=0}^\infty \Pr(S_N\ge T\mid N=n)\Pr(N=n).\tag{*}$$

The right hand side requires us to find these chances of each $S_n$ reaching the threshold. Although this isn't much of a simplification for a general die ($S_n$ can have a very complicated distribution) , it leads to a good approximation when the process is likely to take many rolls before dying or reaching the threshold. That's because the sum of a large number of the $X_i$ approximately has a Normal distribution (according to the Central Limit Theorem). When the expectation of the truncated die is $\mu$ (equal to $9.45/(1-0.05)$ in the question) and its variance is $\sigma^2,$ the distribution of $S_n$ has an expectation of $n\mu$ and variance of $n\sigma^2$ (according to basic laws of expectation and variance as applied to the independent variables $X_1,X_2,\ldots, X_n$). Writing $\Phi(x;n\mu,n\sigma^2$ for the Normal distribution function with expectation $n\mu$ and variance $n\sigma^2,$ we obtain

$$\Pr(S_N\ge T\mid N=n) \approx 1 - \Phi\left(T-\frac{1}{2}; n\mu, n\sigma^2\right).$$

Plugging this into $(*)$ along with the geometric distribution law yields

$$\Pr(\text{Reach }T) \approx \sum_{n=1}^\infty \left(1 - \Phi\left(T-\frac{1}{2}; n\mu, n\sigma^2\right)\right)p_{*}(1-p_{*})^n.$$

As a practical matter, we may terminate the sum by the time $\sum_{i=n}^\infty p_{*}(1-p_{*})^i$ is less than a tolerable error $\epsilon\gt 0,$ because the $\Phi$ factor never exceeds $1.$ This upper limit equals $\log(p_{*}\epsilon)/\log(1-p_{*}).$ (For the situation in the question, that upper limit is around 418.) We can also work out a reasonable value for beginning the sum (by skipping over really tiny initial values). That leads to the relatively short and simple code shown below (written in R). Its output, obtained through the command dragon.Normal(), is $0.269879\ldots,$ agreeing with the exact answer to five significant figures.

# Use `NA` to specify the "death" sides of the die; otherwise, specify the 
# values on its faces.  `p` gives the associated probabilities.
dragon.Normal <- function(threshold=250, die=c(NA, 2:19, 0), p=rep(1/20,20), eps=1e-6) {
  #
  # Find and remove the "death" face(s) to create the truncated die.
  #
  i.death <- which(is.na(die))
  p.death <- sum(p[i.death])
  if (p.death <= 0) return(1)
  die <- die[-i.death]
  p <- p[-i.death]
  p <- p / sum(p)
  #
  # Compute the expectation and variance of the truncated die.
  #
  mu <- sum(die * p)
  sigma2 <- sum((die-mu)^2 * p)
  #
  # Establish limits for the sum.
  #
  N <- ceiling(log(eps * p.death) / log(1 - p.death))
  if (N > 1e8) stop("Problem is too large.")
  Z <- qnorm(eps)
  n <- min(N, max(1, 
       floor((Z * (1 - sqrt(1 + 4*threshold*mu/(Z^2*sigma2)))/(2*mu))^2 * sigma2)))
  #
  # Compute the sum.
  #
  n <- n:N
  sum(p.death * (1-p.death)^n * 
        pnorm(threshold - 1/2, mu*n, sqrt(sigma2*n), lower.tail=FALSE))
}
Related Question