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)

Write it in APL.

I don't think there's anything that can magically transform that into a simple continuous probability distribution that can be solved by summing some derivatives. Plus you would also need to factor in weapon and armor modifiers at some point.

But there might be, but I don't know enough about probability to say so.

Let's say there isn't. In that case, transform the recurrence into an iterative process. Since and A and B are constants at the time of invocation, each step isn't dependent upon the previous. This is ideal for parallelization. Split the work out across all of the cores you have available, and you should be able to achieve near linear scaling.

If that's still not enough, your recurrence relation looks simple enough to be run on GPUs, you'd just need to convert it to an iterative algorithm, and bam, throw it at a DX11/GL4-capable GPU with a couple of thousand shader cores, stream the results for each branch into a texture. Consider OpenCL, it's fairly simple to use (it's just C99 with some vector SIMD intrinsics).

And then of course, you'd need to do your reduction step where you sum each computed branch, which could either be done on CPU or GPU.

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.

>>4

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

err, please disregard that typo at the beginning of the code.

Could just average?
Eg A+B /2 = C
See how many hits Each get (/Who dies)

Secondary(?) (/Who lives doing max damage)
       &     (/Who lives doing min damage)

...Pretty basic / should be quick though..

also...
Max Vs Opponent min -> Check guaranteed loss
Min Vs Opponent max -> Check guaranteed win?

ooc.math.statistics

I have a feeling that if you take the expected amount of damage on a give move (if they choose their attacks randomly, just take the average of the damage amounts of all attacks), and then assume that they deal this expected amount of damage each turn, and reduce it do a problem of two opponents with health, both only executing a single attack dealing the expected damage, and then observe who dies first, I think that will yield the most probably outcome, but I'm not sure. It would take a proof to verify that.

Just run the fight a couple of times and then average it, should be fast enough.

>>8
Go away, you're worse than lisp people.

...Wait, Both do between A & B?
You could just compare health??

>>11
ooc.web.apologetics

>>11
#include <ooc/io/io.h>
#include <ooc/util/ArrayStack.h>

int main(void) {
  var stack local = new(ArrayStack(), 4);

  Stack$push(stack, "bro?");
  Stack$push(stack, "mad ");
  Stack$push(stack, "you ");
  Stack$push(stack, "Why ");

  foreach(char * str, stack) {
    fputs(str, stdout);
  } foreach_end;

  putchar('\n');

  return 0;
}

/* GRUNNUR - EOF */

I suppport all /prog/riders who suggest using average (a+b)/2