2010-11-27, 09:38 PM
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?)
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