A hero attacks a monster. The hero deals 100 damage with every successful hit...

[Embarassed]

This should be a simple task but I'm not getting something.

There's a game hero that attacks a monster. The hero deals 100 damage with every successful hit. The hero has a 20% chance to miss, in that case he deals 0 damage. If an attack is successful, the next successful hit deals 10% more damage. This bonus stacks: one hit is 100, next is 110, next is 121, and so on, until the hero misses. When the hero misses, he loses all the bonuses stacked from previous attacks and his next successful hit will deal 100 damage.

The monster has 10 000 health points.

What is an expected value of the number of attacks the hero needs to kill the enemy?
What is an expected value of the damage dealt with one hit?
And finally, what is an expected value of the damage dealt with one hit if monster's health points are infinite?

So I thought I should build a row and then sum it.
A = 100, H = 10000, B = 10%, P = 80%

Average damage of 1st hit = D1 = A * P
Average damage of 2nd hit = D2 = A * P * B + A * (1 - P)
Average damage of 3rd hit = D3 = A * (P * P * B * B + (1 - P) * (1 - P) + P * (1 - P) + (1 - P) * P * B)
...
Average damage of Nth hit = DN = ?

Average damage of 1 hit is <D> = [imath]\displaystyle\sum_{n=1}^{N} \frac{D_n}N[/imath]. Then the average number of hits is H / <D>. But I got stuck with building the row and I'm pretty sure I'm going the wrong way since it should be simpler.

I could say that on the average there are 8 successful hits out of 10, then the average damage of 1 hit is [imath]\frac {A \displaystyle\sum_{n=0}^7 (1.1)^n} {10}[/imath]. But what if it's 4 hits then 1 miss then 4 hits then 1 miss? The average combo is not 8...

If you can explain me how should I approach this task, I would be grateful.

 

[blamocur]

A question: when the hero misses does the monster restore his health points?

 

[Embarassed]

A question: when the hero misses does the monster restore his health points?

No, his health only decreases by the amount of damage the hero deals.

 

[blamocur]

I would approach this using Markov chains, with the number [imath]m[/imath] of the preceding successful hits describing the current state.
Unfortunately there is infinite number of states here, so instead of defining the transition matrix I would write down recursive expressions for probabilities of ending up in state [imath]m[/imath] after [imath]n[/imath] steps.

 

[BigBeachBanana]

What is an expected value of the number of attacks the hero needs to kill the enemy?

Let K be the number of attacks needed to kill the boss.

[math]\mathbf{E}(K) = \sum_{k=1}^{\infty}k\Pr(K=k)[/math]
The tricky part is to calculate [imath]\Pr(K=k)[/imath]
For the first attack, the probability of the enemy being killed on the first attack is
[math]P(K=1) = P(H=1)P(D=1) = 0.8\times P(100(1.1)^{1-1}) \ge 10000)= 0.8 \times 0 = 0[/math]
For the second attack, the probability of the enemy being killed on the second attack is
[math]P(K=2) = P(K=1) + P(H=2)P(D=2)P(K=1)^c=0+0.8P(110 \ge 10000)(1-0) = 0[/math]
In this equation, P(H=1)P(D=1) is the probability of the enemy being killed on the first attack, P(H=2)P(D=2) is the probability of the enemy being killed on the second attack, and [imath]P(K=1)^c[/imath] is the probability of the enemy not being killed on the first attack, which is 1 - P(K=1).

For the k-th attack, the probability of the enemy being killed on the k-th attack is
[math]P(K=k) = P(H=1)P(D=1) + P(H=2)P(D=2)P(K=1)^c + ... + P(H=k)P(D=k)P(K={k-1})^c[/math]
This recursive calculation is computationally expensive. My recommendation is to run Monte Carlo simulations.

What is an expected value of the damage dealt with one hit?
And finally, what is an expected value of the damage dealt with one hit if monster's health points are infinite?

I don't understand these 2 questions.

 

[blamocur]

I believe I can compute the average amount of damage inflicted during the [imath]n[/imath]-th attack, but I don't know how add them up, i.e., how to compute the average amount of damage inflicted during the first [imath]n[/imath] attacks.

[math]D_n = d_0 p\left( \frac{1 -p + p^{n}a^{n-1}-p^na^n}{1-pa} \right)[/math]where [imath]d_0=100[/imath] is the amount of damage from a single hit, [imath]a = 1.1[/imath] is the increase of damage with each consecutive hit and [imath]p=0.8[/imath] is the probability of a successful hit. I derived it from recursive formulae, and it seems correct for [imath]n=1[/imath] and [imath]n=2[/imath].

 

[BigBeachBanana]

My recommendation is to run Monte Carlo simulations.

My simulation with 10,000 samples tells me that it's 76.

 

[BigBeachBanana]

I believe I can compute the average amount of damage inflicted during the [imath]n[/imath]-th attack, but I don't know how add them up, i.e., how to compute the average amount of damage inflicted during the first [imath]n[/imath] attacks.

[math]D_n = d_0 p\left( \frac{1 -p + p^{n}a^{n-1}-p^na^n}{1-pa} \right)[/math]where [imath]d_0=100[/imath] is the amount of damage from a single hit, [imath]a = 1.1[/imath] is the increase of damage with each consecutive hit and [imath]p=0.8[/imath] is the probability of a successful hit. I derived it from recursive formulae, and it seems correct for [imath]n=1[/imath] and [imath]n=2[/imath].

I was thinking something like
[math]D_n =d_0a^{n-1}p^n\\ \sum_{n=1}^k D_n= d_0p + d_0ap^2 +\dots + d_0a^{n-1}p^{n} =d_0p(1+ap+\dots +(ap)^{n-1})\\ \sum_{n=1}^k D_n= d_0p\left[\dfrac{1-(ap)^n)}{1-ap}\right] [/math]

 

[blamocur]

I was thinking something like
[math]D_n =d_0a^{n-1}p^n\\ \sum_{n=1}^k D_n= d_0p + d_0ap^2 +\dots + d_0a^{n-1}p^{n} =d_0p(1+ap+\dots +(ap)^{n-1})\\ \sum_{n=1}^k D_n= d_0p\left[\dfrac{1-(ap)^n)}{1-ap}\right] [/math]

Your formula says, for example, that during step # 50 the expected damage will be about 0.17, but I believe it must be more than 80. In fact, my formula yields [imath]\approx[/imath]133.3

Also, I was having doubts whether the expectations can be simply summed up here since [imath]D_n[/imath]'s are not independent. Not sure what I was thinking , but summing them up gives the expectation of cumulative damage after [imath]n[/imath] steps:
[math]C_n = pn\frac{1-p}{1-pa} + p \frac{p-pa}{1-pa} \frac{1-(pa)^n}{1-pa}[/math]Unfortunately it does not answer the more important question, i.e., what is the distribution of the cumulative damage, which would let tell what is the average number of tries needed to kill the monster. But the graph of [imath]C_n[/imath] shows that [imath]C_{78} > 10000[/imath], which is quite close to @BigBeachBanana's estimate:

 

[Embarassed]

Wow, since it's an exercise for high school students, I really thought the solution must be the simplest. I must have been wrong ?

I believe I can compute the average amount of damage inflicted during the [imath]n[/imath]-th attack, but I don't know how add them up, i.e., how to compute the average amount of damage inflicted during the first [imath]n[/imath] attacks.

[math]D_n = d_0 p\left( \frac{1 -p + p^{n}a^{n-1}-p^na^n}{1-pa} \right)[/math]where [imath]d_0=100[/imath] is the amount of damage from a single hit, [imath]a = 1.1[/imath] is the increase of damage with each consecutive hit and [imath]p=0.8[/imath] is the probability of a successful hit. I derived it from recursive formulae, and it seems correct for [imath]n=1[/imath] and [imath]n=2[/imath].

How did you derive this formula? Analytically or by estimating the terms to the first Dn-s?

 

[BigBeachBanana]

I plotted @blamocur 's formula vs. my Monte Carlo simulation. I have my simulation to assume the first hit always lands so the curve shifted up by 100. Otherwise, the curves almost perfectly overlap.

Wow, since it's an exercise for high school students, I really thought the solution must be the simplest. I must have been wrong ?

Not the way it was presented. Perhaps you have the original source of the question?

 

[blamocur]

Wow, since it's an exercise for high school students, I really thought the solution must be the simplest. I must have been wrong ?

This makes me suspect that I am misunderstanding the problem. Or that I am missing something more simple and elegant.

How did you derive this formula? Analytically or by estimating the terms to the first Dn-s?

I considered the probability [imath]P_{m,n}[/imath] of ending up in state [imath]m[/imath] after [imath]n[/imath] tries. State [imath]m[/imath] means that there are exactly [imath]m[/imath] consecutive hits in the last [imath]m[/imath] tries. Then I wrote recursive equations for [imath]P_{s,n}[/imath] and ended up with with this formula for [imath]n>0[/imath]:
[math]P_{m,n} = \left\{ \begin{array}{lll} p^m P_{0,n-m} = (1-p) p^m & {if} & m < n \\ p^n &{if} & m = n \end{array} \right.[/math]Since the damage inflicted in the last step is [imath]d_0 a^{m-1}[/imath] we simply need to sum up the products [imath]d_0 P_{m,n} a^{m-1}[/imath].

 

[blamocur]

View attachment 34894
I plotted @blamocur 's formula vs. my Monte Carlo simulation. I have my simulation to assume the first hit always lands so the curve shifted up by 100. Otherwise, the curves almost perfectly overlap.


Not the way it was presented. Perhaps you have the original source of the question?

I've done my own simulation, and it matches my formula somewhat better. The attached images are for 10000 and 1000000 simulation rounds respectively:

 

[Embarassed]

Not the way it was presented. Perhaps you have the original source of the question?

I don't, unfortunately. But I do wonder if there's some simplification of initial conditions of the question. Maybe some information was passed incorrectly and hence complicates the task. For example, it's not +10% to the last damage dealt but +10% to the initial damage, like 100, 110, 120, 130 and so on. Not sure if it simplifies anything.

Anyway, thank you for sharing your approach for this exercise, I'll try to repeat it on my own.