+- Southperry.net (https://www.southperry.net)
+-- Forum: Maplestory (https://www.southperry.net/forumdisplay.php?fid=15)
+--- Forum: Game Mechanics (https://www.southperry.net/forumdisplay.php?fid=33)
+--- Thread: Expected Hits/Kill [mathy thread] (/showthread.php?tid=33371)
Expected Hits/Kill [mathy thread] - Russt - 2010-11-27
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
Expected Hits/Kill [mathy thread] - Fiel - 2010-11-27
With PsycoPy I can do 5m HP in 1 second.
C2D E6400 @ 3.0 GHz.
Expected Hits/Kill [mathy thread] - Noah - 2010-11-27
Now do it with a damage range based on a function f(x)!
Noah
Expected Hits/Kill [mathy thread] - Russt - 2010-11-27
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.
Expected Hits/Kill [mathy thread] - XTOTHEL - 2010-11-27
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.
Expected Hits/Kill [mathy thread] - Russt - 2010-11-27
Yeah, that's assuming you deal the same damage over and over to that mob.
![[Image: random_number.png]](http://imgs.xkcd.com/comics/random_number.png)
The fact that each roll is independent makes a difference.
Expected Hits/Kill [mathy thread] - Stereo - 2010-11-27
Russt Wrote: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().
Expected Hits/Kill [mathy thread] - shouri - 2010-11-28
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.
Expected Hits/Kill [mathy thread] - Russt - 2010-11-28
Well, yeah. That method works. But it's either way inefficient or somewhat inaccurate (due to scaling everything down).
Stereo Wrote: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.
Expected Hits/Kill [mathy thread] - shouri - 2010-11-28
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.
Expected Hits/Kill [mathy thread] - Stereo - 2010-11-28
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)
Expected Hits/Kill [mathy thread] - Russt - 2010-11-28
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.