Random Fail


One of my common software interview questions involves the creation of a game board. Part of the problem includes the generation of random numbers. If the candidate is writing in C/C++, the typical code I see looks something like this:

srand(seed); // one time seeding of generator
// later on ...
r = (rand() % 6) + 1; // throw the dice

Plenty of people have discussed the drawbacks of rand(), but the interview problem is not focused on the random number generation itself, so I consider the code above reasonable. Recently I had a candidate use JavaScript as their language of choice. The candidate wrote:

r = Math.Floor((Math.Random() * 5) + 1); // [1...6] ?

I’m not a JavaScript expert, but I noticed a couple things right away. First, there appears to be no way to seed the generator, so it’s not reproducible. Second, Math.Random() returns a float in the range [0.0 to 1.0). In other words, the code above will never return the number 6 because Random() never generates a 1.0! Even if Random() returned values in the range [0.0 to 1.0] there would still be a big problem. Random() is a uniform generator, so it only returns precisely 1.0 on very rare occasions. Hence the distribution of numbers will look something like this, which is clearly not random:

Takeaway: getting random numbers correct is a non-trivial problem. A lot of information available on the Internet about generating random numbers is plan wrong. Beware. Test your generators to ensure that they are both random and uniform. If I was writing C++ code today that needed to throw a d6, it would look like this:

#include <random>
std::mt19937 mt(seed); // generation engine
std::uniform_int_distribution<int> ud(1,6); // distribution engine
// later on ...
r = ud(mt); // [1...6], uniformly distributed

For a hilarious 30 min excursion into the pitfalls of C/C++ rand(), see Stephan’s talk: rand Considered Harmful. You’ll never use rand() again.

Advertisements
This entry was posted in C++, Computers and Internet, Game Programming. Bookmark the permalink.

One Response to Random Fail

  1. Zach Z says:

    http://www.cigital.com/papers/download/developer_gambling.php

    One of the first online real money poker websites in the late 90s screwed up their RNG and shuffling algorithm. What should have been 52! possibilities for the deck was limited down to 86 million by a buggy shuffle algorithm and by seeding the RNG based on milliseconds since midnight (there are only ~86mil ms in a day). This was further reduced to just 200,000 possibilities for a hand dealt at a certain time. When the exploiters got their cards, they merely had to search through the 200,000 possible deck orders to find the right one and know every card in play.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s