Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
There is a math problem that has been troubling me for awhile now... Here's the thing. Those of you who have played roleplaying games such as Dungeons and Dragons will recognize a lot of terms in this thread:
1 dice with 6 sides is hereby called 1d6, just as one dice with 10 sides is hereby called 1d10. So one dice with S sides is called 1dS.
If you roll N dice with S sides each, this is hereby called ANdS. Example:
If you roll 7 dice with 12 sides each (N = 7, S = 12) this is called 7d12.
The average of 1dS is not that hard to calculate, it's just (S+1)/2. The average for 1d6 is (6+1/)2 = 3,5. The average of NdS is not very hard to calculate either, it's just N*(S+1)/2, the average of 5d4 is 5*(4+1)/2.
Here is the problem: Let's say that on a roleplaying game, like Neverwinter Nights, or whatever game that is dice-based, you attack an enemy with a weapon that does a total of NdA damage. The average damage would be N*(S+1)/2. However, this enemy has a certain damage reduction, R. My question is, what is the average of the outcome when you attack an enemy, who has damage reduction R, with a weapon that does NdS damage?
The average is NOT N*(S+1/2) - R. What you must do is subtract R from every possible outcome of N*(S+1/2) and divide it with the number of possible outcomes. If an outcome becomes negative then change that outcome to 0, since you can't possibly do negative damage on an enemy.
If someone could perhaps code a program that calculates the average of N*(S+1/2) - R, where you can input values for N, S and R, that would be great.
I hope that you understood what I talked about here, just ask me if you want me to be clearer on something.
Isn't the second parenthesis supposed to be before the division?
Randil wrote:
What you must do is subtract R from every possible outcome of N*(S+1/2)
I don't quite understand this. Do you mean to subtract R from every possible average of NdS (what you wrote, I think) or from every possible result of NdS? I'm inclined to think that you meant every possible result, but please correct me if I'm wrong. In any case, there are S^N possible results when you roll N dice with S sides, so that could get quite complicated to program. Well, maybe not with loops.
That sort of thing requires arbitrary depth recursive looping which is only possible in C++ through templates (which needs a recompile) and in scripting languages through an eval statement. And it's too late in the evening for me to be doing things like that. But rest assured, it is really simple and who knows, I may find the motivation to write up a really quick perl script for it tomorrow morning.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Dacicus wrote:
Randil wrote:
The average is NOT N*(S+1/2) - R.
Isn't the second parenthesis supposed to be before the division?
Yes, you are right, it should be "The average is NOT N*(S+1)/2 - R." Thanks for pointing that out.
Dacicus wrote:
Randil wrote:
What you must do is subtract R from every possible outcome of N*(S+1/2)
I don't quite understand this. Do you mean to subtract R from every possible average of NdS (what you wrote, I think) or from every possible result of NdS? I'm inclined to think that you meant every possible result, but please correct me if I'm wrong. In any case, there are S^N possible results when you roll N dice with S sides, so that could get quite complicated to program. Well, maybe not with loops.
What I meant was every possible result of NdS. For example, here is the average of 1d6:
(1+2+3+4+5+6)/6 = 21/6 = 3,5
And here is the average of 1d6 with a damage reduction of 4:
(0+0+0+0+1+2)/6 = 3/6 = 0,5
You subtract the damage reduction (in this case 4) from every possible result of 1d6. That's why 1,2,3 and 4 deals 0 damage, as you can see in the equation. Only when you get 5 or 6 on the dice you will deal damage, if you roll 5 the damage will be 1 (5-4), and if you roll 6 it will be 2 (6-4). The same thing goes for NdS, you must subtract the damage reduction from every possible result of the outcome and divide ot with the possible number of outcomes. I hope this cleared things up a little.
And it would be really awesome if someone could come up with a program that calculates this stuff, but don't feel any pressure on you, it's not like I force you to do it or anything.
N*((S+1)/2 - (S - R) / S * R - R / S * (1+R) / 2)
assuming 1 <= R <= S, whole numbers
explanation:
(S - R) / S =
probability that S - R > 0
so multiply that by reduction
R / S = probability that S - R <= 0
(1+R)/2 = average reduction if bounded by 0
this can probably simplified a little, and if you redfine it so the problem of dice is 0 to S instead of 1 to S that might simplify it more too
edit: simplified version n * (r - s) * (r - s - 1) / (2 * s)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Yaaaaay! :)
Thanks a bunch flagitious, this problem has been bugging me for quite a while. And the equation was a lot simpler than I had thought, and that's good. Even I could code a program now that calculates this now.
Does damage reduction occur to each individual die or to the summation of the dice? If the later, neither of the above formulas worked. I used the simple test case of N=2, R=2, S=6 and got 3.333333 when the average should have been 5.0.
I take it that neither of us knows enough about D&D to know off the bat which one, eh?
If somebody tries to come up with a formula for that situation (I've been thinking about it, but since I'm at work I've only got so much free mind-processor time) there's a special case to watch out for. If R <= N, the answer would simply be N*(S+1)/2-R because no damage will ever become negative (thus we don't have to worry about the initial problem in the first place.) (It's possible that the formula will take this into account if it's structured the way I think it is, though)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Actually, the formula N*(S+1)/2-R isn't correct. The reason for this is that you have to subtract R from every possible outcome (the result of the outcome) of NdS. To try to make things clearer, let's calculate the average of 1d8 with a damage reduction of 5:
The average of 1d8 is: (1+2+3+4+5+6+7+8)/8 = 4,5
The sum 1+2+3+4+5+6+7+8 represent all the possible outcomes (the results of the outcomes) of 1d8. With a damage reduction of 5 we will have to subtract 5 from each and every term. But since you can't inflict negative damage, all negative terms are changed to 0. This gives us:
(0+0+0+0+0+1+2+3)/8 = 6/8 = 0,75
As you can see, every term has been subtracted from every term because the damage reduction affect every possible outcome. There is still 8 possible outcomes, that's why we still divide the sum with 8.
With NdS you would have to add together every possible outcome, and then divide it with the number of possible outcomes.
I know this is quite confusing, sometimes I even confuse myself with this, but I hope you understand what I mean.
I never said it was a complete solution. I said it worked specifically for the R <= N situation.
Nothing you've said has really been confusing. The issue was that Flagitious assumed that the damage reduction was subtracted from each individual die instead of from the total damage, but this assumption might be mistaken.
Assuming, of course, that damage reduction is subtracted from damage (not individual dice) then an incomplete formula would be...
N * (S + 1) / 2 - R + choose(R, N + 1) / S^N
"choose" is a function that's defined as:
choose(n, r) = n! / (r! * (n-r!))
This will work for values of N > 1 and R <= N + S. For values of R bigger than N+S something needs to be subtracted. Subtracting "N * choose(R - S, N + 1) / S^N" seems to work approximately for some values of N, but I'm not sure if there's just a lot of rounding errors or it's simply wrong.
(This is all being compared to the output of a simple brute-force program that adds up all the outcomes and divides by the total number of outcomes. But, you wanted a program and not just a formula, right? Can you compile/run Java programs?)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Gigafrost wrote:
But, you wanted a program and not just a formula, right? Can you compile/run Java programs?
Yes, I'd like a program that could calculate this, be it a Java- or C++ program or whatever, as long as it can do it. And no, I can't compile Java programs. The only programming skills I have are basic C++ knowledge, nothing advanced. But if I got an easy equation I could probably compile a program that does the calculations.
Oh, and sorry about misunderstanding your previous post, Gigafrost. By the way, have you played a lot of D&D before? Because normally when I talk to people about this they're mostly "what the crap is going on in that guy's head???" you know. Well, I'm just glad you know what I'm talking about. :)
And just for fun, a friend of mine has done a lot of dice-calculations for roleplaying games such as D&D, like what the average is of 4d6 if you take away the dice with the lowest outcome. If anyone's interested I could post these here sometime.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
itstoearly wrote:
shouldnt it just be (S+1-R)/2?
No, the (S+1)/2 is the average of 1dS and the R is the damage reduction, and the equation means "average damage" - "damage reduction", which is (S+1)/2 - R.
Yes, I'd like a program that could calculate this, be it a Java- or C++ program or whatever, as long as it can do it. And no, I can't compile Java programs. The only programming skills I have are basic C++ knowledge, nothing advanced. But if I got an easy equation I could probably compile a program that does the calculations.
I'm not sure I can do more than post the code to my program, though. It'd be the code that simply brute-forces the solution (in other words, it'll be fine as long as N doesn't get very big.) A formula would be nice, yes. I was thinking of playing around with the formula a bit more.
Randil wrote:
Oh, and sorry about misunderstanding your previous post, Gigafrost. By the way, have you played a lot of D&D before? Because normally when I talk to people about this they're mostly "what the crap is going on in that guy's head???" you know. Well, I'm just glad you know what I'm talking about. :)
The only D&D I've ever played was a few old AD&D computer games (specifically the Dragonlance trilogy.) However, all my brothers play it and I've picked up a bit of the simpler terminology (but very few rules.)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Gigafrost wrote:
I'm not sure I can do more than post the code to my program, though. It'd be the code that simply brute-forces the solution (in other words, it'll be fine as long as N doesn't get very big.)
It'll be just fine if you'd post your programcode, preferebly in C++ code, that's the language I'm most familiar with. And I would really appreciate it if you came up with a simple mathematic formula, that would be awesome.
I don't know everything about statistics, but I feel confident when I say there isn't a single formula to do this. In general, the way to solve these sorts of things is to examine the probability distribution. The expected value for nDs with damage reduction r would be:
Sum[0*P(x); x:n->r] + Sum[(x-r)*P(x); x:r->n*s]
Where P(x) is the probability of rolling an x. The problem is that the probability function changes if you change n or s. For example, P(x) for 1D6 is a horizontal line, because the probabilities of getting any of 1, 2, 3, 4, 5, or 6 are all the same. P(x) for 2D6 is a positively sloped line from 2 to 7, and a negatively sloped line from 7 to 12. As you increase the number of dice, P(x) slowly converges to a "normal" probability density curve.
I don't really know the best way to calculate these values that you want, but this is what I would do:
For nDs, there are s^n possible outcomes, and the number of ways to get m is the coefficient of x^m in the generating function (x + x^2 + ... + x^s)^n. I don't know of any simple way to find such a coefficient, but there is a recursive formula given by:
a(<0,<0)=0
a(0,0)=1
a(n,k) = Sum[a(n-1, k-j); j:0->s-1]
Where a(n,k) is the coefficient of the x^k in (x + x^2 + ... + x^s)^n. Thus, P(m) = a(n,m)/s^n. Hopefully you or someone else can use this information to write a reasonably efficient computer program to calculate the values you need.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
I know that there is a simple formula for calculating the average of 1dS with a damage reduction of R, I could post it here if you'd like, I have written it down on some paper that should be somewhere in my room i think.
Thanks for taking the time to solve this, xebra. I think I'll let someone who's good at programming write a program for this though :)
Well, I can't really post the code in C++ because I can't remember the details of how to program in C++, but I guess I'll just post the Java code. The algorithm isn't particularly efficient either; I just threw it together to test formulas. I suppose the advantage of that is that it should be easy to understand and convert to C++ on your own.
public class Dice {
public static void main(String[] args) {
int n = 3;
int s = 6;
int r = 4;
int[] dice = new int[n];
for(int i = 0; i < dice.length; i++)
dice[i] = 1;
int sum = 0;
int count = 0;
do {
sum += count(dice, r);
count++;
dice = next(dice, s);
} while(!done(dice));
double average = (double)sum / count;
System.out.println(average);
}
public static int count(int[] arr, int r) {
int sum = 0;
for(int i = 0; i < arr.length; i++)
sum += arr[i];
if (sum <= r)
return 0;
return sum - r;
}
public static int[] next(int[] arr, int s) {
for(int i = 0; i < arr.length; i++) {
arr[i]++;
if (arr[i] <= s)
return arr;
arr[i] = 1;
}
return arr;
}
public static boolean done(int[] arr) {
for(int i = 0; i < arr.length; i++) {
if (arr[i] != 1)
return false;
}
return true;
}
}
Now, I'm not going to leave you completely in the dark as to how to translate the code. Lemme see, here's some important notes that should help you a lot...
- All Java programs are in classes, but this code doesn't need to be in a class when in C++. That means that when you copy the functions over you don't need the "public static" parts of the function names and you don't need to put them into classes.
- "public static void main(String[] args)" is the default entry point into a Java program, much like "void main()" is for C++. This can be changed without consequence because I never used args.
- "arr.length" is the length of the array; you could simply pass "n" as a parameter into the functions that use it and use "n" instead of "arr.length"
- "System.out.println()" is just standard output (like printf or cout).
- "int[] dice = new int[n];" creates an array of "n" integers. I don't recall if this can be done as easily in C++.
As you can see, the code is not particularly complex\special, is short (brute force methods can be that way sometimes), but gets the job done. It can also be sped up but for small enough N it's fast enough.
Also, if Xebra is right and there isn't a single formula to calculate this, I suppose at least you could take advantage of the R <= N+S and R <= N formulas to create something that works for a lot of cases.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Okay, thanks a lot for posting the code Gigafrost. Is there a program that I can download for this programming-language? I mean, so I just have to copy-paste the code to that program.
I'll give this some more thinking to, but that is, strictly mathematicly, since I'm no good at programming. What you and xebra have come up with has sure helped out a lot.
Last night I wrote a program to do it in C++ which just used recursion to do it. However it has a fairly low limit to how many dice can be rolled because of the way I sum up the numbers. I beleive it only does up to 10d6 fine.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
I think that up to 10d6 will be just fine, BoltR, thanks a lot for taking the time to do that program. Could you post the program here? Or at least the code?
