How do you calculate %xHKO?

Instead of recursion, you could use an array to store the answers from each step and then generate the next step from that (there's a term for this but I forget). You have to generate every single answer, rather than just the few you need, but you only need to calculate each answer once instead of recursing forever.

Disclaimer: I haven't tried this so I don't know if it's actually an improvement.

Well, I wrote a new program to calculate this stuff. (Written in Excel VBA because almost everyone has Excel.) Inputs are taken from cells B1, B2, B3. (B1 = min damage, B2= max damage, B3 = Monster HP.)

To use this code, open Excel > open Visual Basic Editor (Alt+F11) > Insert > Module > Copy/Paste code into Module. Input values for min, max, monster hp in cells B1, B2, B3. Execute the code by Alt+F8 in main Excel window or by F5 in Visual Basic Editor. Output is spit out in column F.

Code:

Sub Test()

Dim min As Double
Dim max As Double
Dim monhp As Double
Dim n As Integer
Dim max_n As Integer
Dim damage As Double

Dim hko() As Double
Dim hkotemp() As Double

Dim sum As Double
Dim poss As Double
Dim prob As Double

min = ActiveSheet.Cells(1, 2)
max = ActiveSheet.Cells(2, 2)
monhp = ActiveSheet.Cells(3, 2)
max_n = Int(monhp / min)
If (max_n * min) < monhp Then
    max_n = max_n + 1
End If

For a = 1 To (max_n + 1)
    ActiveSheet.Cells(a, 6).Value = ""
Next a

ReDim hko(min To max)
For a = min To max
    hko(a) = 1
Next a

sum = 0
poss = (max - min) + 1
For i = min To max
    If i >= monhp Then
        sum = sum + hko(i)
    End If
Next i
prob = sum / poss * 100
ActiveSheet.Cells(1, 6).Value = prob

n = 1
Do While n < max_n
    For x = 1 To n
    
        Erase hkotemp()
        ReDim hkotemp(((x * min) + min) To ((x * max) + max))
        
        For y = min To max
            For z = x * min To x * max
                damage = y + z
                If x = 1 Then
                    Erase hko()
                    ReDim hko(min To max)
                    For a = min To max
                        hko(a) = 1
                    Next a
                    hkotemp(damage) = hkotemp(damage) + hko(z)
                Else
                    hkotemp(damage) = hkotemp(damage) + hko(z)
                End If
            Next z
        Next y
        
        Erase hko()
        ReDim hko(((x * min) + min) To ((x * max) + max))
        For g = ((x * min) + min) To ((x * max) + max)
            hko(g) = hkotemp(g)
        Next g
        
    Next x
    
    n = n + 1
    
    sum = 0
    For h = (n * min) To (n * max)
        If h >= monhp Then
            sum = sum + hko(h)
        End If
    Next h
    poss = ((max - min) + 1) ^ n
    prob = sum / poss * 100
    
    ActiveSheet.Cells(n, 6).Value = prob
Loop

End Sub

For reference, this webpage has tables of probabilities when rolling 1 to 25 (6-sided) dice:
http://wizardofodds.com/gambling/dice2.html

If you set the min/max to match dice, the output of this program matches what you would expect from those tables. However, when you change the values to numbers similar to in-game damage numbers (i.e., min/max are over 10000), the calculation takes way too long. Or actually, it starts to have problems when min/max get over 500 or so.

So the way to go is to generate a sample and calculate probability using the sample. The result is not going to be completely accurate, but it should be very close as long as you have a large enough sample size.

Yeah, I tested the method in Lua (which supposedly runs pretty fast, as far as interpreted scripting languages go) and found that it was kinda really loopy and inefficient, but couldn't come up with a better way, and so I sort of gave up on trying to get exact answers. What you could do is round the damage down by 10's or 100's as the range gets larger, or just calculate in units of 1/100th-of-damage-range or something like that. But in that case I prefer the calculus approach. Heheh.

Oh, interesting. I'm into some efficient way of calculating that exactly when I'm free.

So much probability within maple. What a godsend.

Noah

its quite easy to calculate

once you have done all the damage calculation and have your
max and minimum damage:

you can have 3 types of values:
worst case scenario = deal minimum damage for all hits
best case sceniaro = deal maximum damage for all hits
normal case scenario = deal average damage for all hits = (maxDamage + minDamage)/2

then find out the monster hp:

assuming that the monster is 9 hp
your max damage is 3
your min damage is 1
your average damage is 2 (maxDamage + minDamage) / 2 = (3+1)/2 = 2

then how many hits to ko monster would be:
maxDamage = 9/3 = 3 hits ko
minDamage = 9/1 = 9 hits ko
averageDamage = 9/2 = 4.5 hits ko

then you add in the probability:

what are the probability of having 3 hits maxDamage/minDamage?
(note: maxDamge would be same as minDamge)

its quite easy to calculate

once you have done all the damage calculation and have your
max and minimum damage:

you can have 3 types of values:
worst case scenario = deal minimum damage for all hits
best case sceniaro = deal maximum damage for all hits
normal case scenario = deal average damage for all hits = (maxDamage + minDamage)/2

then find out the monster hp:

assuming that the monster is 9 hp
your max damage is 3
your min damage is 1
your average damage is 2 (maxDamage + minDamage) / 2 = (3+1)/2 = 2

then how many hits to ko monster would be:
maxDamage = 9/3 = 3 hits ko
minDamage = 9/1 = 9 hits ko
averageDamage = 9/2 = 4.5 hits ko

then you add in the probability:

what are the probability of having 3 hits maxDamage/minDamage?
(note: maxDamge would be same as minDamge)

Not only did you bump a 4-month old thread, but with a worthless post that contributed nothing to the conversation.

They weren't looking for the average hits to KO (because that's easy to figure out, as you have shown), but rather your % chance to KO in a specific number of hits. Like, in your example of a damage range of 1-3, what's the % chance you'd KO in 2 hits, 3 hits, and 4 hits? At such small numbers, it's pretty easy to count up the possibilities. But with a range of say.... 9500-20000 on a 4-hit attack on a monster with 130k HP, it gets much more complicated.

I made a pretty good approximation (or so I'm told) of the formula for it in algebra on my Corsair calculator, but I don't know any real stats so it's not completely accurate, nor does it work at all with crits. If only someone with enough knowledge in the forum (NOAH) could share with us a method to calculate it with stats, that would be most helpful.

I'd like to go on record saying that the distribution of the sum of uniform distributions is not fun to work with

You can probably do it algebraically using multiple variable integrals of the p.d.f. (uniform distribution is P(x) = H(x) +(-1)H(x-1) ) so you end up with something like integral y = -inf to inf P(x)P(y) dy But just the fact that it's a piecewise function makes it annoying to work with.

Which, in 2 variables, just ends up being a triangle. P(x) = xH(x) - 2(x-1)H(x-1) + (x-2)H(x-2) But that limits you to finding 2hko probabilities. As a diagram, this would be like the diagonal area under a square, where the square has uniform height.

In the long run just running a few thousand simulations will probably get you close enough, and be a lot easier to write.

I'd like to go on record saying that the distribution of the sum of uniform distributions is not fun to work with

You can probably do it algebraically using multiple variable integrals of the p.d.f. (uniform distribution is P(x) = H(x) +(-1)H(x-1) ) so you end up with something like integral y = -inf to inf P(x)P(y) dy But just the fact that it's a piecewise function makes it annoying to work with.

Which, in 2 variables, just ends up being a triangle. P(x) = xH(x) - 2(x-1)H(x-1) + (x-2)H(x-2) But that limits you to finding 2hko probabilities. As a diagram, this would be like the diagonal area under a square, where the square has uniform height.

In the long run just running a few thousand simulations will probably get you close enough, and be a lot easier to write.

Well then what the hell did I do and why does it work for all numbers of hits? Also, as much as I'd like to claim otherwise, I don't really understand your math lingo.

I'd like to go on record saying that the distribution of the sum of uniform distributions is not fun to work with

You can probably do it algebraically using multiple variable integrals of the p.d.f. (uniform distribution is P(x) = H(x) +(-1)H(x-1) ) so you end up with something like integral y = -inf to inf P(x)P(y) dy But just the fact that it's a piecewise function makes it annoying to work with.

Which, in 2 variables, just ends up being a triangle. P(x) = xH(x) - 2(x-1)H(x-1) + (x-2)H(x-2) But that limits you to finding 2hko probabilities. As a diagram, this would be like the diagonal area under a square, where the square has uniform height.

In the long run just running a few thousand simulations will probably get you close enough, and be a lot easier to write.

When it comes to two hits, you can equate this to using a diagonal line to cut diagonally across a square in the XY plane using your damage range as both the x-axis and y-axis.

ex: with a damage range of 1~7

The chance that you'll do at least X amount of damage can be calculated by finding the area of such a triangle.

7_________
6------- /
5------/
4----/
3--/
2/
1_________
1 2 3 4 5 6 7

^ It's supposed to be a 45 degree line... and a square... but whatever

The issue very slightly steps in once you cross the half way point. You'll have to work with two separate sections.


If you move this to 3 attacks, it's the equivalent of cutting a cube using a plane. And sadly this splits up the area that you have to work on into three sections. Mainly because when you begin cutting off the corner of the cube you get shapes that look like pyramids with triangular bases. (Take a cube of cheese, stand it on one of it's vertices, then cut off from the top to see what I mean.) After cutting down enough you start getting hexagonal bases. And after more you go back to triangular bases.

So now you'd have to split this into three parts to calculate the volume.

Each dimension (or hit) that you want to add into this problem will just add yet another section that you have to calculate separately, further complicating the computation if you want to be precise.




~ ~ ~ ~ ~ ~ ~

After about 25 hits though, the uniform distribution on the dice rolls/rng which used to look like this:


becomes a normal distribution like so:


This second one CAN be calculated. But only if we're talking about you taking 25 hits or more in the first place.

This would just barely a bit to calculate %4hko with something like savage blow since it hits 6 times.

I doubt most of you who use 4 hits skills would want to train on something that takes you 6 skill uses to kill. So it's pointless to look at a normal distribution.

~~~~~~~~~


I'm still working on this problem. I'll let you guys know if I come up with anything.

After about 25 hits though, the uniform distribution on the dice rolls/rng which used to look like this:

 Spoiler

becomes a normal distribution like so:

 Spoiler

This second one CAN be calculated. But only if we're talking about you taking 25 hits or more in the first place.

This would just barely a bit to calculate %4hko with something like savage blow since it hits 6 times.

I doubt most of you who use 4 hits skills would want to train on something that takes you 6 skill uses to kill. So it's pointless to look at a normal distribution.

The problem with your approach is that it's not dynamic at all. After three hits, that square looks horribly disfigured. And after 100 hits, even though it looks a lot like a bell curve, it's still not exactly a bell curve. It's just a square wearing the bell curve over itself and you'll still be able to see the corners, if only slightly. So your approach should be a shape that can transform with by using the x hits variable, not a static one.

EDIT: Here's what I did.

 Spoiler

Key
max = maxHitPerBullet-minHitPerBullet
avg = averageHitPerBullet-minHitPerBullet
dpb = (monsterHP/numberOfHits)-minHitPerBullet
hits = Number of hits the attack does. Cannon does 4 at max level.
atkNum = The number of hits you've done before this. If this is my third Cannon, than this number would be 3.

If(dpb/avg<1)
=(dpb/avg)^(hits*atkNum)*(dpb/max)

If(dpb/avg>=1)
=1-(2-dpb/avg)^(hits*atkNum)*(dpb/max)

And here's what I did as listed in my spreadsheet. It's a little more complex because it all has to be in one line, and I used different variables than above because I'm ripping this from when I posted it earlier in my Corsair Calc thread.

 Spoiler

Key
hits = The number of hits the attack does. For example, Burst Fire is always 3.
attacks = The number of the attack on the monster. If you've hit the monster once already this is your second attack, so it would be 2.
b10 = monsterHP/(hits*attacks)
All references to damage are the min, max, and average damage for that skill, not from your damage range.

=IF(minDmg*hits*attacks<monsterHP; IF(maxDmg*hits*attacks>=monsterHP; IF((B10-minDmg)/(avgDmg-minDmg)<1; 1-(((B10-minDmg)/(avgDmg-minDmg))^(hits*attacks-1))*(B10-minDmg)/(maxDmg-minDmg); ((1-((B10-minDmg)/(avgDmg-minDmg)-1))^(hits*attacks-1))*(B10-minDmg)/(maxDmg-minDmg));0);1)

I'd like to go on record saying that the distribution of the sum of uniform distributions is not fun to work with

You can probably do it algebraically using multiple variable integrals of the p.d.f. (uniform distribution is P(x) = H(x) +(-1)H(x-1) ) so you end up with something like integral y = -inf to inf P(x)P(y) dy But just the fact that it's a piecewise function makes it annoying to work with.

Which, in 2 variables, just ends up being a triangle. P(x) = xH(x) - 2(x-1)H(x-1) + (x-2)H(x-2) But that limits you to finding 2hko probabilities. As a diagram, this would be like the diagonal area under a square, where the square has uniform height.

In the long run just running a few thousand simulations will probably get you close enough, and be a lot easier to write.

I actually did this sometime in the past and came up with this crazy formula in terms of the unit step function H(x) (which I actually didn't know about until now, but came up with my own name/silly symbol for. regardless I'll use H(x) in this post). I used the result I got to make this (which still has some sloppy arithmetic in it, but I haven't touched it in very long and don't plan to).

Generally how I went through it:

P(x) for a uniform distribution is H(x) - H(x-1) as you said. Call this P_1(x), where P_n(x) is the number of uniform distributions you're summing.

P_2(x), then, is just integral of P_1(t) from x-1 to x. You come up with (same as in your post):
P_2(x) = xH(x) - 2(x-1)H(x-1) + (x-2)H(x-2)

After doing this a few times I saw a pattern...
P_3(x) = 1/2x^2 H(x) - 3/2(x-1)^2 H(x-1) + 3/2(x-2)^2 H(x-2) - 1/2(x-3)^2 H(x-3)
P_4(x) = 1/6x^3 H(x) - 4/6(x-1)^3 H(x-1) + 6/6(x-2)^3 H(x-2) - 4/6(x-3)^3 H(x-3) + 1/6(x-4)^3 H(x-4)

And so, assuming the pattern holds, you come up with an expression in summation notation for any P_n(x). Integrating this gets P_n+1(x) so it works.

I actually worked this with a uniform distribution between variables a and b too, rather than with a unit distribution, which made it much more annoying to deal with. In hindsight the H(x) makes it so much easier.

The problem with your approach is that it's not dynamic at all. After three hits, that square looks horribly disfigured. And after 100 hits, even though it looks a lot like a bell curve, it's still not exactly a bell curve. It's just a square wearing the bell curve over itself and you'll still be able to see the corners, if only slightly. So your approach should be a shape that can transform with by using the x hits variable, not a static one.

Central Limit Theorem:

If n is greater than or equal to 25 (n being the amount of random numbers being used), then the distribution of random variables can be approximated using a normal distribution.

Sure it's an approximation, but it gets pretty close to the actual answer. This would be good to use, but I don't think our n's will come even close to being 25. 3hko's with cannon give n=12. even 5hko's give n=20. And not many people here are going to train on something that requires more than 5 hits to kill. So yeah, though it WOULD be applicable to use a normal curve as we do more hits... people in MS are more worried about the lower n's than the higher n's.

The problem with your approach is that it's not dynamic at all. After three hits, that square looks horribly disfigured. And after 100 hits, even though it looks a lot like a bell curve, it's still not exactly a bell curve. It's just a square wearing the bell curve over itself and you'll still be able to see the corners, if only slightly. So your approach should be a shape that can transform with by using the x hits variable, not a static one.

As x goes towards infinity, the curve goes towards a bell curve. Therefore, shouri is correct by stating that after n hits, where n is a positive integer, one can use the bell curve for an approximation which will yield an approximation as good as needed. (I'll not go into epsilon delta, unless someone want me to do so)

That's what I thought was a good way of doing it, but I'm pretty confident that there's an exact way of calculating this in less than O(log N) time.

Noah

That also disregards criticals, multiple damage formulas (grr BW), varying multipliers (aran/crusaders) etc.

When you stretch the uniform distribution with scale multipliers it all gets significantly more complicated.

Like for a 50% critical that deals double damage,
.5*(H(x - 1) - H(x - 2)) + .5*.5*(H(x - 2) - H(x - 4))
= .5 H(x-1) - .25H(x-2) - .25H(x-4)


If the min crit wasn't exactly equal to the max non-crit this would look uglier even.

That also disregards criticals, multiple damage formulas (grr BW), varying multipliers (aran/crusaders) etc.

When you stretch the uniform distribution with scale multipliers it all gets significantly more complicated.

Like for a 50% critical that deals double damage,
.5*(H(x - 1) - H(x - 2)) + .5*.5*(H(x - 2) - H(x - 4))
= .5 H(x-1) - .25H(x-2) - .25H(x-4)


If the min crit wasn't exactly equal to the max non-crit this would look uglier even.

I figured this too eventually (where the initial distribution is a choice between one set of endpoints or another, which works for criticals and for warrior animations but not both at once).

The general case just gets annoying to work with.

That's what I thought was a good way of doing it, but I'm pretty confident that there's an exact way of calculating this in less than O(log N) time.

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.

http://sidequest.awardspace.info/hits.html
link is broken

edit: i have created a formula on how to work this probability, will be posting a calculator for this soon.

By the way...

its quite easy to calculate

once you have done all the damage calculation and have your
max and minimum damage:

you can have 3 types of values:
worst case scenario = deal minimum damage for all hits
best case sceniaro = deal maximum damage for all hits
normal case scenario = deal average damage for all hits = (maxDamage + minDamage)/2

then find out the monster hp:

assuming that the monster is 9 hp
your max damage is 3
your min damage is 1
your average damage is 2 (maxDamage + minDamage) / 2 = (3+1)/2 = 2

then how many hits to ko monster would be:
maxDamage = 9/3 = 3 hits ko
minDamage = 9/1 = 9 hits ko
averageDamage = 9/2 = 4.5 hits ko

then you add in the probability:

what are the probability of having 3 hits maxDamage/minDamage?
(note: maxDamge would be same as minDamge)

This method doesn't actually work.

If your min damage is 1 and max damage is 3, your average damage is 2. By dividing average damage by 2 HP, you get that your average number of hits is 1.

Clearly this isn't the case - you have a 2/3 chance of 1, and a 1/3 chance of 2.

By the way...


This method doesn't actually work.

If your min damage is 1 and max damage is 3, your average damage is 2. By dividing average damage by 2 HP, you get that your average number of hits is 1.

Clearly this isn't the case - you have a 2/3 chance of 1, and a 1/3 chance of 2.

And when you use bigger numbers such as a range of 10000 to 20000 with a monster whose HP is 15000, it ends up being 50%. So this method only works with large ranges, and only if the monster has an HP in the exact center of your range. Doesn't work at all with crits.

Random crap I stumbled across while thinking about something else...

http://en.wikipedia.org/wiki/Convolution

Particularly using the Fourier transform is nice cause it makes it a simple product of the functions. (O(n) for a discrete function - just pointwise multiply)

iirc the FFT is O(n log n) which is not quite in Noah's O(log n) time but will get a solution. Or, because the function is a box, just use prior knowledge to determine the equivalent wavelet and directly compute the product one way. You could probably get O(log m) that way with a class that uses m identical attacks, since you are getting the same product multiple times (1+2 = 3+4 = 5+6, ... then 1+2+3+4, 5+6+7+8, etc.).