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.
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.