D&D-ish Probability/Algorithm Problem

[markgritter]

Suppose you're playing D&D and have a house-rule spell that does 100 attacks, each performing 1 point of damage to a random live enemy. (Suggested name: Schmendrick's Death From Papercuts.) So, if you are facing exactly one opponent it performs 100 hit points of damage to him; if you are facing 100 enemies each will get, on average, one point of

Comments

[greykev]

in a truly average/random system I'm not sure it matters when the individual points fall on an opponent, if they stop receiving them at point of death. either more go to the high HP creatures early, or more will go once the lessers fall, in the end you're allocating damage by hit point totals, if I understand your scenario correctly.

so, um? for fewer than 100 opponents, take lowest hit point value and multiply by number of enemies. if result is <100 apply damage evenly, eliminate lowest HP opponent(s) repeat using adjusted HP totals until all 100 points have been doled out. if result on subsequent checks is greater than remaining damage divide remaining damage points evenly to remaining opponents, with highest HP total receiving any excess damage.

Melf the wizard faces 3 kobolds (HP 7) 2 bug bears (HP 23) and a firbolg (HP 45) He casts the spell: the lowest HP(7) x 6 opponents = 42 damage divided equally, 58 points of damage remaining. Kobolds are eliminated, bug bears (HP 23-7=16) firbolg (HP 45-7=38) 16 X 3 = 48 <58 16 points

[greykev]

all of which assumes we know the HP totals of the opponents. If that's unknown, or the process cannot tell when an opponent is dead, I'm at a loss.

[markgritter]

That's not really what I asked for--- in the original description of the spell there is some probability that one or more of the kobolds survive. If you imaging rolling a D6 for each 1-point attack it is possible that we roll fewer than a total of 21 1's, 2's, or 3's. (Not likely, but possible.)

If we modify your example a bit it is easy to calculate it exactly. If we have 1 kobold with 7 hit points and 5 epic kobolds with 100 hit points then the spell will never kill an epic kobold (except maybe on the very last attack, which we can ignore.) In this case we just have a binomial distribution: how likely is it that we will roll a 1 fewer than 7 times? That works out to about 0.13%.

Unfortunately I don't see a simple way of handling death, which breaks the binomial distribution. If one 7-point kobold dies the others are more likely to get hit.

[hgfalling]

Can you do this? Suppose you have a lookup table of cumulative binomial distributions for, say, p=1/n for n in whatever range you're interested in. That shouldn't be too costly.

for each monster randomly selected:
pick a random #.
find amt of dmg from cumbinomdist(n=totalspelldmgleft,p=1/monsters_left)
if amt >= monster_hp:
totalspelldmgleft -= monster_hp, monster is dead
else
totalspelldmgleft -= amt, monster takes amt dmg
check for totalspelldmgleft being 0, break in that case.

if after you finish, there's still totalspelldmgleft, then go back and repeat as necessary (re-randomize the remaining monster list).

This looks like it would usually be O(monsters) to me, but I might be wrong.

[markgritter]

Here's an algorithm I believe to be correct, using the same sort of idea as hgfalling... but I can't convince myself his results in the same distribution.

1. M = smaller of remaining spell damage, or minimum of monsters' hit points
2. Pick a live target at random from the T targets remaining
4. Pick a random amount of damage D from the cumulative binomial distribution with p = 1/T and N = M. (Restrict to damage > 0.) In the case M=1 the damage is necessarily 1.
5. Decrease monster hit points by D and check for death (or for new minimum)
6. Decrease remaining spell damage by D.
7. Go back to step 1 if spell damage > 0.

I think it is probably necessary to restrict the binomial distribution to the maximum that can kill a monster, rather than the maximum spell damage left. But, I may be wrong on that...

This algorithm is still obviously O( damage ) but its average running time might be better. The analysis looks complex.

interesting

[greatestofnates]

I don't think it matters if you assign more damage to the monster than it can take if you keep track of overflow damage to apply later. Also, I don't think it is necessary to choose each target randomly.

For a simpler case: 2 monsters at 2 hp each and the papercuts do 3 damage.

Clearly each monster has a 1 in 2 chance of being the sole survivor.

My algorithm.
1. Order remaining monsters from n..1, set Overflow = 0.
2. Pick a random number in range 1 to cuts^n to determine amount of damage (D) done:
in the example:
1 = 3 pts
2,3,4 = 2 pts
5-7 = 1 pt
8 = 0 pts
3. Apply damage to Monster, check for death (remove monster from list if it dies).
4. Reduce cuts by amount of damage dealt.
5. If damage was greater than monster hp add excess damage to Overflow
6. n = n - 1
6a. End if cuts + Overflow == 0
7. If n < 1 or cuts < 1, set cuts = Overflow and start at #1