5D6 drop the lowest two (math ?)

[der_kluge]

Would this be easier if I slapped together a program to try to do this, and iterated through it a million times?

 

[der_kluge]

Here is my code (yes, I'm a crusty old C programmer...):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>

typedef struct {
time_t time;
unsigned short millitm;
short timezone;
short dstflag;
} time_b ;

const int SIDES=6 ;
const int NUMDICE=4 ;

comp (const void *i, const void *j)
{
return *(int *)i - *(int *)j ;
}

void main(void)
{
int dice[NUMDICE] ;
int i, total, final_total=0, stime ;
long ltime, z ;
time_b ft ;
float average, final_average ;

for (z=0; z<=1000000; z++)
{
ltime = time(NULL) ;
stime = (unsigned) ltime/2 ;
(void)ftime(&ft) ;
srand((int) ft.millitm + stime) ;

for (i=0; i<=NUMDICE-1; i++)
{
dice = (rand() % SIDES) +1 ;
}

qsort(dice, NUMDICE, sizeof(int), comp) ;

total=0 ;
average=0 ;
for (i=NUMDICE-3; i<=NUMDICE-1; i++)
{
total+=dice ;
}

average = (float) total/(NUMDICE-1) ;

final_total+=total ;
final_average = (float) final_total/z ;
}

printf("final total = %d\n", final_total) ;
printf("final average = %f\n", final_average) ;
}

My result = final total = 12258902
final average = 12.258902


that is 4d6, drop the lowest one; keep the best 3.

(changing the value of NUMDICE (above) to 5)
which is 5d6, dropping the lowest two, keeping the best 3 is:

first run
final total = 13402253
final average = 13.402253

second run
final total = 13406922
final average = 13.406922

And just for fun:
3d6
final total = 10512603
final average = 10.512603

I might play around with it some more. See if I can implement "re-roll 1s" into it. That would be interesting to see...

 

[der_kluge]

And in case anyone cares:

3d6+1d8; keep the best 3.

final average = 13.144652

Any other cooky combinations anyone wants me to try?
I'm going to put the "re-roll ones" logic in it next, and I made it so that it takes parameters, so I can just feed it stuff at the command-line so I don't have to recompile it all the time.

 

[ichabod]

Okay,

I have a spreadsheet which works for up to 9d6. From that I extracted a symbolic function which works for any number of dice, keeping any number, with any number of sides as long as they have the same number of sides. Unfortunately, I cannot figure out how to make one of these nice graphics of the function to post it. In any case, the formula is so complicated that it would take a rather large graphic to understand it. I have included a MS word doc with the equation as a MS Equation 3.0 object. If this is not adequate, perhaps some enlightened soul can make a graphic out of it, or tell me how to do so in Word or Mathcad.

First of all, I am confident the spreadsheet is correct, but I have not tried to test my symbolization of it. Second of all, it is a bunch of summations, but it's not as bad as it looks. Finally, I came up with some kludges to make it work symbolicaly, but perhaps someone with a more theoretical math background can clean it up.

What the equation does is run through all possible sorted combinations of the kept dice that add up to the specified value, and figures out the number of combinations that result in that sorted set of kept dice, sums them all up, and divides by total possible combinations. Where the trick comes in is that figuring out the number of combinations requires a multinomial coefficient, but the inputs to the multinomial coefficient depend on how many and which values on the kept dice are equal to each other. That's what the c_j's calculate.

To represent this, I kludged up the functions represented by circle plus and circle times. Circle plus returns a 1 if the two values are equal, and a 0 if they aren't. Circle times returns a 1 if they aren't equal, and a 0 if they are (it's the negation of circle plus, and is included to clean up the main function a bit). Perhaps there is some better way to represent this mathmatically, but if there is I don't know it.

die kluge, I have a python module that will calculate the exact probability distribution (including mean, median, and standard deviation) of just about any combination of dice you could think of, using brute force. For a reasonable number of dice, it's quite fast. If you (or someone else) wants it, let me know.

 

[LazarusLong42]

Ichabod:

I'm going to look over your solution later, and see if (1) I can make it work, and (2) if I can make the symbolics a bit easier

Edit:

What the equation does is run through all possible sorted combinations of the kept dice that add up to the specified value, and figures out the number of combinations that result in that sorted set of kept dice, sums them all up, and divides by total possible combinations. Where the trick comes in is that figuring out the number of combinations requires a multinomial coefficient, but the inputs to the multinomial coefficient depend on how many and which values on the kept dice are equal to each other. That's what the c_j's calculate.

Heh... I needed to read further than skimming. What you've done is to define, mathematically, a brute-force algorithm for determining the correct result. Which is, I'll admit, pretty clever... but that's not what we're trying to do. We want to do this without all the iterations; theoretically, per die we should be able to boil things down to half the number of iterations or less (so, for 10 dice, 1/1024 = 1/2^10 or less iterations than running things for every possible roll).

I think we all can do this via brute force, though

 

[ichabod]

Would you be willing to post the spreadsheet as well? I've been trying to deduce symbolic representations from patterns in the combinatorics, but couldn't find a pattern in anything dropping more than one die.

Sure, spreadsheet is attached. I tested the idea on easy to check things, like 3d3 drop 1, and 4d6 drop 1. I'm going out tonight to celebrate 13 years without a cig, but now that I have the python code finished I can check the whole thing. I'll also try to program in the formula, and test it, but I may get distracted. In any case, I think I forgot to mention that the formula depends on treating 0^0 as 1. It could be rewritten without that assumption, but it would make the formula even messier.

The spreadsheet is set up only for keeping 3d6 and rolling up to 9d6. Enter the number of dice into '# of dice', and it should give you the whole distribution. The patterns in the combinatorics took me a long time to figure out, but I finally realized that once you're dropping more than one die, you have to start summing multinomials.

In the spreadsheet, all the sorted three die combinations are on the left. Then there are four collumns showing calculating the possible combinations for the four possible was the three dice could be equal: all 3 equal, top 2 equal, low 2 equal, and none equal. These are taken using an offset on the tables to the far right, where the summing of multinomials is done. Then the 'Combos' collumn figures out which equality situation actually exists, and then gets the correct number of combinations. The chart with the distributions sums up all the combos with the correct number is the 'Total' collumn.

 

[ichabod]

Heh... I needed to read further than skimming. What you've done is to define, mathematically, a brute-force algorithm for determining the correct result.

No! What I did is a step back from brute force. The dice you keep are done brute force, but the dice you drop are done with the summing of multinomials. For example, with 9d6 drop 6, you have 10,077,696 combinations, but you are only brute forcing through 56 of the combinations of the kept dice. Admittedly, this is not useful if you are keeping a lot of dice and dropping few, but it certainly a step towards what you are looking for. Now, if someone can figure out a non-brute force way to determine how many of each multinomial is required, you have a completely non-brute force way to do it.

 

[dylanarena]

Hello folks,

I'm happy to have come across this thread. I'm writing a package for the open-source statistical programming language/environment called "R" that calculates things people want to know about dice rolls, and this was a great first function for me.

Nathan, I built the function based on your analysis, so thank you very much!
And then I extended it so that it also calculates the probabilities of each possible outcome (e.g., P{roll 5d6, drop 2, and get a 15}). I was able to skirt brute force: it generates all possible combinations--but *not* all possible orderings (e.g., {1,1,2} but not {1,2,1} or {2,1,1})--of the kept dice, and then calculates how many permutations there are of each combination (but doesn't generate them).

Anyway, the details are in the function, which is in the package, which will be up on the CRAN website in a few weeks and will (since it's open-source) be available for further inspection. I'm fishing for more dice probability questions folks want answered, though: I'll post another thread asking about that right now. I just wanted to stop in here and thank you all (Nathan and all the folks who helped tweak the final algorithm).


Cheers,
Dylan

 

[Celebrim]

Thank God for math nerds.

All good technology doth proceed from them. The scientists feed on the products of the math nerds. The engineers feed on the products of the scientists. And everyone else lives well because of them.

Threads like this warm my heart. No band of D&D sword swingers is more heroic.

 

[dcollins]

Nathan, I built the function based on your analysis, so thank you very much!

I do hope you test your software against a brute-force method (please).