How do you calculate %xHKO?

If it is within my capacity to do, I would like to know how. Also, it is possible to have it work with crits? I know it's hard, as Stereo said, but I'm very much interested in making a hits to kill calc for all most classes.

If I see it correctly, one should be able to use it with N different damage-"ranges", where N is 1 or higher. Assume that all these damage ranges have the Range R_n and the probability P_n to occur (It will work with a constant damage, such as 0 or so, or with a probability of 1 or 0).

I thought about Convolution first, then I found out that IFS have a better potential when using combining probability mass functions and probability density functions, and then take the integral of the lower limit (monster's HP) after iteration. Sounds kinda messy right now, as I've not got time to think much about it, as well as exams going on now. Hopefully some of that made sense.

Noah

Not that it's entirely helpful, but to just run a damage simulation for my Paladin (of 1,000,000 kills, not perfectly optimized) that averages 9.4 hits each takes me 8.3 seconds on my Pentium 4. I guess that's a rate of about 1.7 million hits per second.

And even with 10,000 runs it gets 2 decimal accuracy on the mean hits to KO (0.05ms).


The nice thing is that it easily expands in number of hits. I can simulate killing 1000 Zakums (500,000,000 hp - over 25000 hits each) and it only takes 12 seconds. Of course at that point it's so close to the average that it's hardly worthwhile... the 1st/3rd quartiles are 25350 to 25400. (variance 45?)

 Spoiler

Hurr, QQ plot. It's not quite normal, slightly heavier tails.

It's only about 40 lines of code in R, most of which is just getting all the input into a damage range. Could pretty easily turn it toward criticals.

Sorry I know the thread is old, but perhaps I can help.

You can do Monte Carlos simulation as suggested if you're rusty on statistics. Or you can approximate it by using normal. If you want the exact probability, here's how it's done: (I think)

What you are looking for is the Irwin-Hall distribution: http://en.wikipedia.org/wiki/Irwin-Hall_distribution
You have to integrate each pdf to get the desired cdf value. Essentially, you are looking at the point where the area to the right of point x = your desired success rate

The general formula to normalize uniform random variable isy-a)/(b-a) where Y is your random variable (damage), a is your lower range, b is your upper range.
You want to match that to the value of 1-F(X), or c.

(y-a)/(b-a) = 1-F(X) = c
=> b=(y+ac-a)/c

Note that we'll need a in order to solve for b, so here's where the approximation comes in, if you want exact, then you'll have to find a formula to express a in terms of b. It'll be the ratio of MIN/MAX = [(Primary Stat * 0.9 * Skill Mastery + Secondary Stat) * Weapon Attack / 100]/[(Primary Stat + Secondary Stat) * Weapon Attack / 100] Courtesy of Lucida
I just prefer to work with 0.9m, where m is mastery %, and call it d,

So we have:
b= y/(d + c(1-d))
where b is the total damage output range, not per hit/attack

Now, what's tricky about k-hitting is that the distribution differs as k changes, for one hit (k=1), c is just 0.05

If you want to one hit something with 20,000 hp, you'd need (working with 60% mastery)
b= 20,000/(0.9*0.6 + 0.05(1-0.9*0.6)) = 35523.979 upper range (d is approximated, remember you can use the exact ratio if you want)

For 2-hitting, you want c = 0.316227766/2 = 0.1581139 (integrate from 0 to 0.05, and divide by 2 to normalize to uniform(0,1))
b = 20,000/(0.9*0.6 + 0.1581139(1-0.9*0.6)) / 2 = 32640.67 / 2 = 16320.338 (you divide by k to get per hit range, instead of total damage)

The above examples are using attack with 100% base, so you're using cannon (400%), just divide your final answer by that. For multihit attacks, you have to treat each hit as an attack, so one hitting with cannon you have to work with k=4, 2-hitting with k=8, etc. Uniform is scalable so it wouldn't affect the distribution shape.

You do the same for k=3 and 4, but values of k and c will change. For example, c for k=3 will be 0.6694/3 for 95% chance, 1.046635/4 for k=4. If you want to find something like 50% chance, you have to make sure you're integrating the pdf correctly, but for the most part, if you're looking for high chance value, just integrating the first piece should be fine.

Some may want to find out with their existent range, what are their chance to 1,2,3-hit a mob. Instead of solving for b, you just solve for c, and then solve for x from the cdf.

If you want to incorporate critical, sorry, you're best off either approximating it by normal or Monte Carlos.

Note: b is calculated on several assumptions. One being the numbers being uniform generated in game. b is calculated with 0 monster def, so you can easily modify that in the end if you wish. Critical is not calculated, if you want to factor that in, best approach is to approximate it by normal or by simulation. That's about it, PM me if you need further clarification or examples.

I like to add how to approximate with normal with critical, instead of running simulations, plus the approximation is pretty close too with multiattacks.

Damage variable can be modeled as:

Y = ∑ (rB + 1) x tU where r is critical multiplier(100% for normal crit, 240% with SE), B is Bernoulli with q=final critical rate, U is uniform (a,b) - (lower, upper) of damage range, t is the skill %

Then, E[Y] = kt(rq + 1)((a+b)/2), Var(Y) = kt² (Var((rB +1)U) B and U independent, and rB + 1, U are indep.
Var((rB +1)U) = E[(rB+1)²U²] - E[(rB+1)U)]² = E[r²B²+2rB+1]E[U²] -( E[rB+1]E[U])²
= (r²q + 2rq + 1)((a²+ab+b²)/3) - [(rq+1)((a+b)/2)]²

Var(Y) = kt² x [(r²q + 2rq + 1)((a²+ab+b²)/3) - [(rq+1)((a+b)/2)]²]

(Y-mean)/s.d ~ N(0,1) where X is the HP of the monster desired. Solving for damage range required to x% k-hit a monster will be harder. You have to algebraically manipulate the formula to solve for b, and expressing a in terms of b once again. If you have programs like R, you can just type in the formula, and use the solve function, except I forgot how to do it. Or better yet, type the formula in Excel and use solver, since I think a lot of you use it for your DPS calculations anyway. You'll have to look up the normal values though.

Woah, thanks Steve. I'll look into this when I get some free time.

So the distribution actually exists/has a name! Why did Google not come up with it when I searched for something such? ._.

Sorry for being gone from this thread for some time. I finally found some time to work a little with it.

The idea I'm going to use for calculating %xHKO is discrete convolution. Exactly how I'm planning to do it is written in this pdf. (Instead of giving the range a uniform distruction though, I'll let the endpoints get another probability, and the inner points a uniform distribution. Not extremely different, but it gives the exact probability, which I very much like.)

The biggest issue with this way of calculating is really to keep track of exact values. In any programming language, I'd recommend that you use fractions to get an exact answer.

Noah

Mm, interesting. I never thought of the binary approach.

Edit: But it actually doesn't save time if you want to calculate each p_n anyway. Hm...

Code:

function convolute(a, b)
  local p = {
    min = a.min + b.min,
    max = a.max + b.max,
  }
  for n = p.min, p.max do
    local sum = 0
    for k = math.max(a.min, n-b.max), math.min(a.max, n-b.min) do
      sum = sum + a[k]*b[n-k]
    end
    p[n] = sum
  end
  return p
end

 Time complexity

The convolution step as I've written it here has time complexity O(r1*r2) where r1 is the range of the larger interval and r2 is the range of the smaller interval. I tried to explain why without using example numbers, but it was too hard.

Assume interval 1 is [200, 700] and interval 2 is [100, 300]
n=300 to n=500 -> inner loop iterates n-300 times (average 100) -> r2*r2/2
n=500 to n=800 -> inner loop iterates 200 times -> (r1-r2)*r2
n=800 to n=1000 -> inner loop iterates 1000-n times (average 100) -> r2*r2/2
total -> (r1-r2+r2)*r2 -> r1*r2

If you loop a single interval with range r and convolute cumulatively k times:

r1	r2	r1*r2
r	r	r^2
2r	r	2r^2
3r	r	3r^2
4r	r	4r^2
kr	r	kr^2
sum	sum	k(k+1)/2 * r^2

And so the total time complexity is on the order of k^2*r^2. Since k = hp/min and r = max-min, this is also hp^2*(max/min-1)^2.

Quadratic time in HP? Yikes.

Of course, one optimization would be to binary convolute until you actually need the numbers. In that case you'd have something like

r1	r2	r1*r2
r	r	r^2
2r	2r	4r^2
4r	4r	16r^2
8r	8r	64r^2
kr	kr	k^2*r^2
sum	sum	(4k^2-1)/(4-1)*r^2

Which is still somehow quadratic.

I tested this on my system and it took about 6.2 seconds to compute hits(1000, 2000, 10000). Quadratic in HP means it takes ten minutes to work with 100000 HP.

One thing about this I was thinking recently. For magic damage considering defense, the defense can have a multiplier of 0.5 to 0.6 meaning that the most extreme values of your damage range have a lower priority than those in the "middle" since they need to combine both the probability of being at the extreme of the uniform distribution AND the extreme of the defense multiplier.

So the distribution wouldn't be exactly uniform, it would have some rise/fall on the borders (don't know if that's what Noah was talking about but this caught my attention).

One thing about this I was thinking recently. For magic damage considering defense, the defense can have a multiplier of 0.5 to 0.6 meaning that the most extreme values of your damage range have a lower priority than those in the "middle" since they need to combine both the probability of being at the extreme of the uniform distribution AND the extreme of the defense multiplier.

So the distribution wouldn't be exactly uniform, it would have some rise/fall on the borders (don't know if that's what Noah was talking about but this caught my attention).

I'm not sure about this, actually, whether the defense is also randomized or if it's simply subtracted from the range. I assumed the latter when I wrote up my order of operations for the thread.

Defense is randomised afterward, you can see it with a character that's all secondary stat (eg. pure dex warrior) there's still some variation in damage with no str at all, if you're hitting something with more than 0 defense.

Mm, interesting. I never thought of the binary approach.

Edit: But it actually doesn't save time if you want to calculate each p_n anyway. Hm...

Code:

function convolute(a, b)
  local p = {
    min = a.min + b.min,
    max = a.max + b.max,
  }
  for n = p.min, p.max do
    local sum = 0
    for k = math.max(a.min, n-b.max), math.min(a.max, n-b.min) do
      sum = sum + a[k]*b[n-k]
    end
    p[n] = sum
  end
  return p
end

 Time complexity

The convolution step as I've written it here has time complexity O(r1*r2) where r1 is the range of the larger interval and r2 is the range of the smaller interval. I tried to explain why without using example numbers, but it was too hard.

Assume interval 1 is [200, 700] and interval 2 is [100, 300]
n=300 to n=500 -> inner loop iterates n-300 times (average 100) -> r2*r2/2
n=500 to n=800 -> inner loop iterates 200 times -> (r1-r2)*r2
n=800 to n=1000 -> inner loop iterates 1000-n times (average 100) -> r2*r2/2
total -> (r1-r2+r2)*r2 -> r1*r2

If you loop a single interval with range r and convolute cumulatively k times:

r1	r2	r1*r2
r	r	r^2
2r	r	2r^2
3r	r	3r^2
4r	r	4r^2
kr	r	kr^2
sum	sum	k(k+1)/2 * r^2

And so the total time complexity is on the order of k^2*r^2. Since k = hp/min and r = max-min, this is also hp^2*(max/min-1)^2.

Quadratic time in HP? Yikes.

Of course, one optimization would be to binary convolute until you actually need the numbers. In that case you'd have something like

r1	r2	r1*r2
r	r	r^2
2r	2r	4r^2
4r	4r	16r^2
8r	8r	64r^2
kr	kr	k^2*r^2
sum	sum	(4k^2-1)/(4-1)*r^2

Which is still somehow quadratic.

I tested this on my system and it took about 6.2 seconds to compute hits(1000, 2000, 10000). Quadratic in HP means it takes ten minutes to work with 100000 HP.

Sounds like too much... Also, I'm not using the binary approach, though it's probably easier to use that to find a relatively short path instead of going into a deep-broad-search.

Keep in mind that you do not need to calculate if , and max is the highest damage one could do with one attack.

My calculator does not take randomized def into account. I assume that the defense is constant.

Noah

Keep in mind that you do not need to calculate if , and max is the highest damage one could do with one attack.

But you still need to calculate the array somehow, and the best and most straightforward approach seems to be to perform the convolution on each P_n in succession. Binary convolution as you mentioned near the end of your pdf still ends up being quadratic because you're working with larger and larger intervals, so it wouldn't be a significant time saving.

Regarding defense, you could use another convolution with a negative interval for that and use that as your base interval.

But you still need to calculate the array somehow, and the best and most straightforward approach seems to be to perform the convolution on each P_n in succession. Binary convolution as you mentioned near the end of your pdf still ends up being quadratic because you're working with larger and larger intervals, so it wouldn't be a significant time saving.

Regarding defense, you could use another convolution with a negative interval for that and use that as your base interval.

Hmm, sorry about the spoiler, I didn't read it. Indeed correct that both are O(HP^2).

I've implemented the discrete convolution function, and it is indeed way slower than I thought it would be. Binary convolution does apparently not seem to help enough either.

Seems like I have to do a more direct approach with convolution, which is kind of messy:
Make a real convolution-function which takes two functions in and returns the convoluted function. If done correctly, should be way faster than discrete convolution. It is not exact, however. (Though the error-margin is minimal)
Wouldn't be too difficult, I hope. As the functions are only compositions of polynomials, it shouldn't be impossible to work out something that works.

Noah

I asked my friend about this, heres the chat log (I do not know if this is correct or not)

Me: I have a question in probablities
Me: assume you are in maple
Me: and there is a monster with x HP
Me: and your damage is L~H
Me: what is the probablity to kill it in n hits
Him: oh, I think I know how to solve it
Him: first you move from L~H to 0~K (K being H - L)
Him: then you solve the equation x1 + x2 + x3 + ... + xn = x (with each n being a natural number between 0 and K)
Him: now take this (1 + x + x^2 + x^3... + x^k)^n
Him: and you need to find the coefficient of x^k
Him: you can split it to (1-x^(k+1))^n * (1+x+x^2+x^3.......)^n
Him: then you need to open the finite part with Newton's Binomial
Him: for example if N is 2, you get: (1 - 2x^(k+1) + x^(2k+2)) * (1 + x ...)^n
Him: D(n, x) - 2D(n, x - k - 1) + D(n, x - 2k - 2)
Him: D(n, k) = C(n + k - 1, k)
Him: let me solve that
Him: I think thats the solution, if I didn't have any mistakes

Him: That circle in the beginning is supposed to be a capital Sigma
Him: This is supposed to give the number of successes, you should divide it with the number of possible options

Edit: he said he had a mistake and that this is the correct solution

Edit: he said he had a mistake and that this is the correct solution

Function doesn't work at all.

 Spoiler

Code:

(defun prob-hits (&key L H x n)
  (/ (loop for k to n
      sum (* (ncr n k)
             (expt -1 k)
             (ncr (+ (* n (- 1 L)) (* k (+ 1 H (- L))) x -1)
                  (1- n))))
     (expt (- H L -1) n)))

Function doesn't work at all.

 Spoiler

Code:

(defun prob-hits (&key L H x n)
  (/ (loop for k to n
      sum (* (ncr n k)
             (expt -1 k)
             (ncr (+ (* n (- 1 L)) (* k (+ 1 H (- L))) x -1)
                  (1- n))))
     (expt (- H L -1) n)))

Oh yes, it's also apparently the probability to hit exactly the hp required (not including anything above it).

Oh yes, it's also apparently the probability to hit exactly the hp required (not including anything above it).

That sounds... entirely useless. Is it even dynamic enough to work with crits?

I solved this problem exactly on Pari. I have the pari program but it's still not quite intuitive enough to use. I'll be re-writing the code to try to make it more intuitive. Once it's done though, other people would need Pari (which is free) to make any use of it though T.T

Due to projects I'm hoping I'll have it done by the weekend. Seems like it'll be mostly useless for the calculator though since you'd need a supplemental but quite small program.

Oh yes, it's also apparently the probability to hit exactly the hp required (not including anything above it).

Then the probability on first hit (L = 1000, H = 2000, x = 2000, n = 1) should be 1/1000, not 0.