Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
July 25, 2014
arrowPress Releases
July 25, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Simulating a loaded dice in a constant time
Simulating a loaded dice in a constant time
April 9, 2012 | By Jaewon Jung

April 9, 2012 | By Jaewon Jung
Comments
    3 comments
More:



[In this reprinted #altdevblogaday in-depth piece, Crytek's technical lead Jaewon Jung explains how to simulate loaded dice using the alias method algorithm, and shares his C++ implementation.]

A fair dice can be easily simulated with rand() function(or C++11 std::uniform_int_distribution) and integer modulo arithmetic. Then how about a loaded dice (a dice with a non-uniform probability for each face)?

No sweat. Just partition a normalized range of 0.0 to 1.0 according to each probability and bin the result of a random function to a corresponding subrange. But the search will require O(n) time complexity(here, n is the number of dice faces).

Can we do better? Sure. One can do a binary search or similar, then one can get a result of rolling a loaded dice within O(logn) time complexity. How about a constant time complexity? Can we achieve that?

Surprisingly (to me, at least), it's possible. There is an algorithm called 'alias method' which guarantees O(1) generation cost once an initialization step(i.e. preprocessing) of O(n) has been done.

This algorithm is from a paper called "A Linear Algorithm For Generating Random Numbers With a Given Distribution" by Michael Vose.


Original probability distribution(top) and aliased one(bottom)

Let's suppose a dice with four faces, each of which has a probability of 1/2, 1/3, 1/12 and 1/12. The probability distribution can be visualized as the top diagram above. The gist of the alias method is to transform the diagram to something like the bottom one. The essential point is that each column in the bottom diagram has at most two items.

By simulating a fair dice to select a column and then flipping a biased coin, which matches to the probability distribution of in the column, to select between the two, one can get the result. A new item added to the original one in that column is called an alias of it, so the name of the algorithm. Quite neat, isn't it?

I learned this algorithm from this excellent (though, rather long) article, Darts, Dice, and Coins: Sampling from a Discrete Distribution. So I highly recommend reading it for more kind & thorough explanation of the matter. Especially, you can check there how the alias table can be generated in a linear time.

The author of the article also provides a Java implementation of it here. Here is my C++ implementation, which is a basic porting of the Java implementation.

[This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]


Related Jobs

Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

DevOps Engineer
Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

Animation Programmer
Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

Server/Backend Programmer
Cloud Imperium Games
Cloud Imperium Games — Austin, Texas, United States
[07.25.14]

Lead Online Engineer










Comments


Jerome Humbert
profile image
Nice and neat trick indeed, thanks for pointing it out!
Note that simulating a fair dice accurately is not as simple as it seems, as the rand() + modulo approach induces biases. However as long as you're not targeting a scientific application - and I guess most reader here won't - this is probably accurate enough.
Probabilities do are tricky :)

Martin Brenner
profile image
Neat! But if random number generation is expensive, I suggest using only one throw, multiplying the result by the number of columns and then use the integer part to select the column and the fractional part to select inside the column.

Jerome Humbert
profile image
Yes, if you assume that you have a (P)RNG which generates uniformly-distributed numbers in [0;1] and produces floating-point values. But then you will face some bias problems because of the variable precision of floats (see http://www.gamasutra.com/view/news/167402/Indepth_Intermediate_fl
oatingpoint_precision.php). Again that depends on the "quality of randomness" you expect.
However I guess your suggestion would be interesting if using fixed-point values and modulo instead of fractional part. Or was it what you meant in the first place?
Good idea anyway.


none
 
Comment: