Expected Hits/Kill [mathy thread]

Now I'm not sure if someone came up with this method before I did, but this is a problem I thought about a long time ago and I decided to revisit today while I'm not doing all that much else.

Consider a player with a damage range 6-10. Our goal is to calculate e(n), the expected number of hits the player needs to deal n damage, for any value of n.

The first few values are easy. e(0) is 0, and e(1) thru e(6) are all 1.

e(7) is the first interesting one. There are 5 possibilities: 6, 7, 8, 9, and 10 damage. Of these, four result in a kill, and one results in 1 HP left. So, 1/5th of the time, you have to add e(1) to account for the remaining 1 HP:

e(7) = 1 + 1/5 * e(1) = 1.2

We can keep doing this:

e(8) = 1 + 1/5 * (e(2) + e(1)) = 1.4
e(9) = 1 + 1/5 * (e(3) + e(2) + e(1)) = 1.6
e(10) = 1 + 1/5 * (e(4) + e(3) + e(2) + e(1)) = 1.8
e(11) = 1 + 1/5 * (e(5) + e(4) + e(3) + e(2) + e(1)) = 2
e(12) = 1 + 1/5 * (e(6) + e(5) + e(4) + e(3) + e(2)) = 2

Now this is a working formula but it's not very desirable. Suppose we have a big damage range, in the thousands. Then we have to add up thousands of numbers just to get each next number in the sequence, and then keep doing that until we get the value we want. Computers can do that but it's... not ideal.

But we can do better. Notice that each expression for e(n) is very similar to the previous one. We can write it like this:

e(8) = e(7) + 1/5 * e(2)
e(9) = e(8) + 1/5 * e(3)
e(10) = e(9) + 1/5 * e(4)
e(11) = e(10) + 1/5 * e(5)
e(12) = e(11) + 1/5 * (e(6) - e(1))
e(13) = e(12) + 1/5 * (e(7) - e(2))

Now we're in business. If we define e(n) = 0 for any negative number, we now have a nice, short recursive formula for e(n), with any positive damage range a-b:

e(1) = 1
e(n) = e(n-1) + 1/size * (e(n-a) - e(n-b-1)),

where size = b-a+1 is the "length" of the damage range.

(Why did I never think of this before?)

 Python test implementation

Code:

# expected number of hits to deal 'hp' damage with range a-b
def hits(a, b, hp):
    e = [0] * (hp+1)
    size = b-a+1

    for n in range(1, hp+1):
        if n-a < 0:
            e[n] = 1
        elif n-b-1 < 0:
            e[n] = e[n-1] + float(e[n-a])/size
        else:
            e[n] = e[n-1] + float(e[n-a] - e[n-b-1])/size

    return e[hp]

# test with arbitrary numbers
print hits(6000, 20000, 85000)

Code:

7.08549445306

Takes about 1 second on my machine to calculate up to 500000 HP, in Python. Quite reasonable, and when you get to values much higher than that you can take some liberties with precision anyway.

With PsycoPy I can do 5m HP in 1 second.

C2D E6400 @ 3.0 GHz.

Now do it with a damage range based on a function f(x)!

Noah

Well with any general function it won't collapse nicely into a 3-term recurrence relation. But you could probably come up with something to account for endpoints, and criticals and attack combinations and whatnot.

hm...you get a slightly different answer by doing:

(summation (ceil (/ n a)))/(max-min-1) where "a" is every different number you can do, and range from min to max.

can't wrap my head around the difference.

Yeah, that's assuming you deal the same damage over and over to that mob.



The fact that each roll is independent makes a difference.

But you could probably come up with something to account for endpoints, and criticals and attack combinations and whatnot.

In principle for the more simple ones you could just do
nc(hp) = number of hits to kill, when the next hit is non-crit
c(hp) = number of hits to kill, when the next hit is crit
The two would be calculating with different min+max + size, and then combined to give
e(n) = %crit * c(n) + (1-%crit)*nc(n)
Which would be fed into the next recursive step.

I expect it would take twice as long to run compared to the non-crits version.


For example (simple) if your non-crit range is 1-2, and your crit range is 2-4, with 50% chance of crits,
nc(i) = nc(i-1) + 1/2 * (e(i-1) - e(i-2))
c(i) = c(i-1) + 1/3*(e(i-2)-e(i-4))
Plus some initial conditions
nc(1) = 1
c(1) = 1
c(2) = 1
Which leads obviously to
e(<=0) = 0
e(1) = 1
nc(2) = 1.5
e(2) = 1.25 <- (nc(2) + c(2)) *0.5
nc(3) = 1.625
c(3) = 1.333...
e(3) = 1.4791666...
nc(4) = 1.7396
c(4) = 1.7497
e(4) = 1.7446
etc.

I'm not sure this approach is valid though since it's weird c(4) < nc(4). Probably better to work through the logic on the recursive definitions for nc() and c().

If you guys are willing to download a small little program I've already solved this problem along with how to account for crits.

I programmed the solution in something called Pari.

The trouble is when you have huge ranges, then you have to scale everything down otherwise you get huge overflows and I really dont want to have to bother with programming around that since I... frankly... dont really care.

It involves the expanding the polynomial

[ x^(lower range) + ... + x^(higher range) ] ^ a*n. Where a is the number of attacks your skill does, and n is the number of times you'll use the skill.

It checks for n's between 1 and 6, since anything past that isn't really that important to me.

If it doesn't cause an overflow, the solution time is quite slow.

Well, yeah. That method works. But it's either way inefficient or somewhat inaccurate (due to scaling everything down).

I'm not sure this approach is valid though since it's weird c(4) < nc(4). Probably better to work through the logic on the recursive definitions for nc() and c().

Hmm.

Well in the simpler version, you have the following:

e(n) = 1 + 1/size * (e(n-a) + ... + e(n-b+1))
e(n-1) = 1 + 1/size * (e(n-a-1) + ... + e(n-b))
and so:
e(n) = e(n-1) + 1/size * (e(n-a) - e(n-b))

So by extension:

c(n) = 1 + 1/size * (e(n-a1) + ... + e(n-b1+1))
c(n-1) = 1 + 1/size * (e(n-a1-1) + ... + (n-b1))

c(n) = c(n-1) + 1/size * (e(n-a1) - e(n-b1))

So it should work...

Edit: I ran the numbers (they match yours) and something is wrong. e(n) plateaus at 2.4 with these numbers, even as n increases to infinity.

Well, if you're worried about being off by a small percent or so then yeah, sure it'll be inaccurate. But it comes with the upside of actually being able to take critical into account.

Edit: Going for the night, will contribute some other time.

If you're less worried about accuracy and want to do complicated stuff like crits and other percent chance stuff, Monte Carlo simulation is easier. Efficiently coded, it only takes a second or so to do a million trials (accuracy is approximately 1/sqrt(trials), so you get 3 digit accuracy from a million)

I found my mistake. The correct recurrence is e(n) = e(n-1) + 1/size * (e(n-a) - e(n-b-1)). Yay off by one errors!

Not a noticeable difference with large numbers in the thousands, but significant for single digits.

Now I'm getting:

nc(2) = 1.5
c(2) = 1
e(2) = 1.25

nc(3) = 2.125
c(3) = 1.333
e(3) = 1.7291666

nc(4) = 2.48958333
c(4) = 1.75
e(4) = 2.119791666

Makes more sense. Edited OP to reflect the change.