Simulate dice rolls

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

elminster
Posts: 1560
Joined: Mon Feb 26, 2007 1:56 pm UTC
Location: London, UK, Dimensions 1 to 42.
Contact:

Simulate dice rolls

Postby elminster » Tue Apr 28, 2009 8:41 pm UTC

I'm working some source code for a game, doing repeated rolls for large numbers of dice is cpu time consuming; so I was wondering if there was a way to simulate it using less cpu time. It doesn't have to be as accurate, but anything reasonable would do.
I was thinking, use an approximation of a Gaussian distribution, the mean and standard deviations if the dice values to come up with a similar sort of thing. Problem is, I wouldn't know how to go about it.
The person here:http://www.protonfish.com/random.shtml suggests:

Code: Select all

function rnd_snd() {
  return (Math.random()*2-1)+(Math.random()*2-1)+(Math.random()*2-1);
}
function rnd(mean, stdev) {
  return Math.round(rnd_snd()*stdev+mean);
}
Although I've got no idea how to go about proving the quality of the values that would generate. Say for example, I was trying to get a random number for 20D6 (i.e. 20 six-sided dice rolls added together) how similar would something like that be to the theoretical ideal results and is there a better (Ideally using as little resources as possible) way to do it?
Image

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Simulate dice rolls

Postby quintopia » Tue Apr 28, 2009 10:36 pm UTC

For enough dice, the approximation to the normal distribution is reasonable. I have found on the internet at one point a way to compute random numbers from a standard normal using only uniform random variables, but I can't find it right now. Just google it for a while.

User avatar
evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Simulate dice rolls

Postby evilbeanfiend » Tue Apr 28, 2009 10:46 pm UTC

i have to say this sounds like premature optimization to me, is your prng really your bottleneck? have you profiled it properly?
in ur beanz makin u eveel

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Simulate dice rolls

Postby NathanielJ » Wed Apr 29, 2009 12:05 am UTC

quintopia wrote:For enough dice, the approximation to the normal distribution is reasonable. I have found on the internet at one point a way to compute random numbers from a standard normal using only uniform random variables, but I can't find it right now. Just google it for a while.


Actually, the method used in the original post uses one form of this. If you sum a whole bunch of uniform random variables, it starts to look normal. The code in the OP doesn't truly find values from a normal, but rather sums 3 uniform random variables and pretends that the result is normal.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Simulate dice rolls

Postby quintopia » Wed Apr 29, 2009 12:37 am UTC

I could have sworn the method I saw got as precise as the underlying data types with only a constant number of uniform random numbers. I found something involving building from exponentials. Is that how it's done?

EDIT: Found the note: http://www.taygeta.com/random/gaussian.html

tehtmi
Posts: 8
Joined: Sun Jan 04, 2009 1:04 am UTC

Re: Simulate dice rolls

Postby tehtmi » Wed Apr 29, 2009 12:53 am UTC

For the method of adding three uniform random variables (mentioned by the OP), here is an illustration of how good of an approximation to the normal you get:

http://www.johndcook.com/blog/2009/02/12/sums-of-uniform-random-values/

If all you are worried about is minimizing the number of calls to your psuedo-random number generator, you could do something like this:

Code: Select all

function roll(int dice, int sides) {
  r = random_integer(sides ** dice); // a number in {0,...,sides ** dice - 1}
  sum = 0;
  while(r > 0) {
    sum += r % sides;
    r  /= sides;
  }
  return sum + dice;
}


...just be sure not to overflow with (sides ** dice).

elminster
Posts: 1560
Joined: Mon Feb 26, 2007 1:56 pm UTC
Location: London, UK, Dimensions 1 to 42.
Contact:

Re: Simulate dice rolls

Postby elminster » Wed Apr 29, 2009 3:32 am UTC

Well the problem was that the original coder done it in such a way that a certain monster would have 15000d4 health points, so 15000 calls loops inside it (I'll probably change this to 150d400 or a very basic formulae for the time being). This would even lag the intel Q9400 based server it's running on (A high powered cpu). That particular monster is a more unique case (Rarely comes into the game), but the current dice function is used by quite a few things.

I did actually run a profiler on it (VTune) and it does indeed show it up as one of the most time consuming functions. So I was looking for a way to preserve the numbers generated but using less resources. The other methods probably use up more resources compared to a low number of throws, but I was looking for something more efficient for the higher numbers.
The current loop is:

Code: Select all

for (i = 1; i <= _throw; i++)
      ret += (rand() % range) + 1;
_throw being number of throws, range being the number of sides, ret being the returned value, rand being the random number generator. It's basically looping for the number of throws and accumulating each value, which would between 1 and the number of sides.

I didn't put this in the coding forum because it's more about the maths. I could implement or find the code for any mathematical function, but I don't know the maths involved nor how to calculate the accuracy of the results (Mathematically proving I mean, since just generating numbers only gives a certain amount of accuracy)
Image

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Re: Simulate dice rolls

Postby GreedyAlgorithm » Wed Apr 29, 2009 3:11 pm UTC

Box-Muller transform. Pseudo-code:

Code: Select all

roll(dice, sides)
  mean = (sides+1)/2.0;
  variance = (sides+1)*(2*sides+1)/6.0 - mean*mean;
  mean /= dice;
  variance /= dice;
  sum = floor(normalboxmuller(mean,variance) + 0.5); //add the 0.5 so that e.g. values from 34.5 to 35.5 are counted as 35
  return sum;

normalboxmuller(mean, variance)
  X = random(); //uniform (0,1]
  Y = random();
  N = sqrt(-2 * ln(X)) * cos(2 * pi * Y);
  N = N * sqrt(variance) + mean;
  return N;


You'll want to truncate roll, and maybe only use it if dice>10 or something. You can get slightly more accurate by changing the "+ 0.5" bit to depend on how far into the tail of the distribution you are, but it's really not worth it. This'll be quite accurate as long as you don't call it for 2d10 or something similarly small.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Simulate dice rolls

Postby Yakk » Wed Apr 29, 2009 4:38 pm UTC

Hmm. A fast XdY function could be fun.

Here is an attempt:
Use a binomial distribution trick to calculate the number of X dice with Y faces that land on 1.
Then eliminate that many dice from your pool. Do the same for the number of X' dice with Y-1 faces that land on 1 -- this is the number of 2s you get.
Repeat until you eat all of the faces (ie, when you have X'''''..''' dice with 1 face, all of them land on 1, so it is guaranteed to terminate).

Now you can precalculate the exact binomial distributions and store them in a table of dimension X x Y x Y.

If the largest dice you use are d20s, and you use them in clumps of 100 dice, that's a table with 40000 entries, each of them a probability of (X dice with Y sides) having (exactly Q dice landing on a 1).

For a given XdY roll, you break X down into chunks of 100. Do a RNG. Accumulate up the table until you hit the threshold. Repeat for each face of the die.

This gives you mathematically perfect results in O(Y) time for up to 100 dice being rolled.

For beyond 100 dice... you could just scale the result (so 15000d4 is 150 * 100d4 ) naively, or you could do a double-scaling of both magnitude and variance 15000d4 = {[(100d4 - 100*2.5)*SD_scale_factor] + 100*2.5} * 150. Then fuzzy it with a random +/- (SD_scale_factor * 150)/2 factor thrown on top (so you don't get discreet pumps every SD_scale_factor * 150 units).

And for lower amounts (like 1d4), you just roll 1d4.

In C++, I'd implement this as a die roll description object. Ie, die( 4 ) would be a 1d4, unrolled.

Calling .roll() would do work.

die(4)^100 might be 100d4 (the interior term rolled 100 times, and added).
die(4)+50 would be 1d4+50.
die(4)*50 would be 50*1d4.

( 2*die(4)+die(8)+2 )^10 is 10d4 *2 + 10d8 + 20.

The object would have a collection of (die size) (die count) and (multiplier), and a constant factor (or the d1) term.

^ number scales the die count of the term (and the constant term).
* and / scales the multipliers (and the constant term).
+ adds two sets of terms.

.roll() then runs something like the above, doing different things for low die-totals than huge die totals, in order to generate a reasonably fast result.

If I was really crazy, I'd extend it to support (1d4)d6. (not that tricky, but probably not worth it).

The best part would be that the 'using' code would now look more natural, and I could change how dice are rolled willy-nilly without ever touching client code every again (by modifying how .roll() works).

But I like coding this kind of thing. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
LaserGuy
Posts: 4585
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: Simulate dice rolls

Postby LaserGuy » Wed Apr 29, 2009 4:52 pm UTC

If you're using a relatively friendly language, it probably has a gaussian random number generator as well as a uniform generator. Then all you need to do is calculate the mean and variance for NdK dice, and throw those values into the gaussian RNG algorithm. This should give for one calculation any arbitrarily large number of dice. You will need to set some threshold (4 dice is probably okay) for the point where you'll need to calculate each roll individually again.

The variance on 15000d4 is pretty small, by the way. For all practical purposes, this monster will have 37500 health.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests