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.]
2 MIN READ
Simulating a loaded dice in a constant time
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.