Name: Anonymous 2011-08-06 2:09
Say two people (RPG characters) are fighting each other and take turns attacking, starting with fighter 1. Both fighters have a certain number of hitpoints and both fighters do between A and B damage with each attack, randomly uniformly distributed.
How do I efficiently calculate the probability that fighter 1 wins?
If I do it recursively via
P(h1, h2) := probability fighter 1 will win when fighter 1 has h1 hitpoints, fighter 2 has h2 hitpoints, and it's fighter 1's turn
= 1 - 1/(B-A+1) * (P(h2-A, h1) + ... + P(h2-B, h1))
it works but obviously takes forever due to the zillions of recursive calls. If I set up an array to store all previously computed probabilities and search that before doing a recursive call, it's faster but still not really good.
Any other ideas?
(This is but the first small step toward my long-term goal of writing a program to play a full game of Dragon Warrior start-to-finish completely unaided)
How do I efficiently calculate the probability that fighter 1 wins?
If I do it recursively via
P(h1, h2) := probability fighter 1 will win when fighter 1 has h1 hitpoints, fighter 2 has h2 hitpoints, and it's fighter 1's turn
= 1 - 1/(B-A+1) * (P(h2-A, h1) + ... + P(h2-B, h1))
it works but obviously takes forever due to the zillions of recursive calls. If I set up an array to store all previously computed probabilities and search that before doing a recursive call, it's faster but still not really good.
Any other ideas?
(This is but the first small step toward my long-term goal of writing a program to play a full game of Dragon Warrior start-to-finish completely unaided)