A metal slime appears! Command?

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)

You could get approximate solutions by rounding the health amounts to discrete values, and then using dynamic programming to fill out a table in n squared time (n would depend on how fine the discretization was). The trick is to do the computation for a particular h1 and h2 once, and then refer to that result when needed in the future, rather recalculating it with other, identical function calls.

Here's a simplified example, for calculating h(a, b) when:

h(n, 1) = 1
h(1, n) = 1
h(n1, n2) = h(n1, n2 - 1) + h(n1 - 1, n2)


Let M be an (a x b) matrix.

M[i,j] = h(i,j)

for(i = 1..a) {
  M[i, 1] = 1;
  M[1, i] = 1;
}

for(i = 2..a) {
  for(j = 2..b) {
    M[i,j] = M[i,j - 1] + M[i - 1,j];
  }
}

return M[a,b];

So that could work out. If you've never seen this before, it is usually easier to visualize it if you can see M as a grid of values. You can look up Dynamic Programming if you'd like to see more about it.

You could also probably make up some function of the their healths and possible attacks, that might not be totally accurate, but could be a good enough guess, and get a better run time.