From The Source - Roll20 RNG Testing

UPDATE: Roll20 now uses QuantumRoll to generate "truly random" dice rolls. Read more on the wiki: <a href="https://wiki.roll20.net/QuantumRoll" rel="nofollow">https://wiki.roll20.net/QuantumRoll</a> Since day 1 we've had threads come up about the randomness of the dice. We finally decided to put the RNG to the test. With some nodejs magic I hooked up the RNG that Roll20 uses to feed data into dieharder , a suite of tests to measure the strength of a RNG algorithm. Over a long weekend I left the Roll20 RNG and a benchmark RNG (AES_OFB) run through the complete suite of tests. After generating over 64.7 TRILLION random numbers from the two algorithms the results are in! But wait ... you don't think you can simply look at a big statistical report without any prior knowledge do you? Of course not! you need to read P-Values and the Null Hypothesis before delving into the arcane mysteries of the dieharder reports. Ok, that was an invigorating read wasn't it?! Now on to the results: AES_OFB - The benchmark / gold-standard RNG built into dieharder Roll20 RNG - The cryptographically secure pure JS RNG used in Roll20 <a href="https://gist.github.com/edalquist/4757300" rel="nofollow">https://gist.github.com/edalquist/4757300</a> WAIT!!! That report says the Roll20 RNG is WEAK!!!!! It must be generating terrible numbers and breaking all my games! (you didn't read that page turner about P-Values and the Null Hypothesis did you). Ok, fine the TL;DR; of that big wall of text is this: We can't prove that a RNG is good We can prove than a RNG is bad There is a catch, since a good RNG is RANDOM sometimes it might appear bad but actually be good So we run each test with a lot of data a lot of times and measure the statistical distribution of the result using some math that is over my head and end up with the P-Value P-Values very close either bound (1 or 0) are suspect and flagged as WEAK in the test suite So yes Roll20's RNG has a few WEAK tests, AES_OFB does as well and after running through the same set of tests multiple times for both RNGs we get 1-3 WEAK tests for each on each run but the tests that are flagged as weak vary. Using the result of this test suite we are even more confident in the Roll20 RNG than we were to start with, all of the analysis we have done shows the RNG to generate evenly distributed numbers and the dieharder tests reinforce these results. I personally GM games on Roll20 regularly and while we have seen streaks of numbers or things that seem crazy we really have to remember that we saw that stuff with physical dice too. For any of you that are still lucky enough to play in person I'd like to request that you write down all of your rolls for the night. Every time any die is rolled all night write down the result on one long piece of paper and see if any streaks/patterns show up :)

Just a little bit more for those interested in the guts of RNG in Roll20: We don't use JavaScript's Math.random(), the important details of its behavior are undefined in the JS spec and as a result it behaves differently on different OS/Browser combos. We do use a cryptographically secure RNG implemented 100% in JavaScript A high-quality server-side entropy source is used to seed each browser-side RNG, ensuring people get different RNG sequences The RNG accounts for modulo bias which is really important for applications like Roll20 that want a constrained random number <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias" rel="nofollow">http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias</a>

Soooooooo.... you say you rolled a 'few' times and it came up with random numbers? tsss. dicey. verrry.... dicey. But Ok, i hope i have good streaks all the time. Or my players will have em.... or not.... and.... euhm... yes... it keeps nagging... are you sure that 64 trillion times is enough? Grinn... i predict the weather more accurate then i can predict these dice. :) thanks for explaining. now i can't sleep... :)

Akimotos said: &nbsp;are you sure that 64 trillion times is enough? Nope that's why they ran it an additional 728 Billion, 282 Million, 847 Thousand, and 280 more times. :P (aka&nbsp;728,282,847,280 in addition to the 64 Trillion) Thank you for posting this Eric! it is more than a bit over my head, but I appreciate the work done to ensure the system is solid.

Entrails?

Yes, but when will you create an RNG test that says your RNG gen is good enough? Good job guys, look forward to those bug fixes (the few weaknesses)

I'm sorry Eric, you may pull one over on everyone else who doesn't understand the&nbsp;mathematical&nbsp;concepts behind RNG analysis. But you and I know you're not telling people the whole truth by leaving out any discussion of the Mydicehateme Principal, developed in the late 70's by Wolfgang Mydicehateme, and later confirmed by Dr. Effthat Dissisbullcrap of MIT. You can find more information on Wikipedia. Expose the truth. This math is a fraud on all Roll20 users.

David, I think Eric pointed out that RNGs in general will show up with a few 'weak' areas and that during testing those 'weak' areas change from test to test. The thing to take away from this is that a weak area is only weak it if is weak across multiple test sequences. Of course, I am not a coder and if I am incorrect I am sure Eric will correct me. - Gauss

*laughs* - Gauss

David C. said: Yes, but when will you create an RNG test that says your RNG gen is good enough? Good job guys, look forward to those bug fixes (the few weaknesses) So your first point isn't actually possible as far as I can tell. As for the second ... I'm guessing you didn't complete the assigned reading from the original post :)

Melvin McSnatch said: I'm sorry Eric, you may pull one over on everyone else who doesn't understand the&nbsp;mathematical&nbsp;concepts behind RNG analysis. But you and I know you're not telling people the whole truth by leaving out any discussion of the Mydicehateme Principal, developed in the late 70's by Wolfgang Mydicehateme, and later confirmed by Dr. Effthat Dissisbullcrap of MIT. You can find more information on Wikipedia. Expose the truth. This math is a fraud on all Roll20 users. Hah! Everyone knows that Dr.&nbsp;Dissisbullcrap was&nbsp;unceremoniously&nbsp;kicked out of MIT for an illicit affair with a Dodecahedron and an&nbsp;Icosahedron. After that shameful event I'm not sure how anyone would be caught dead citing that joker's work!&nbsp;

I skipped the reading because I attempted to write an RNG tester myself a couple years back, and read Knuth instead. No, I'm not kidding, and yes, you really should just use dieharder. First, yay for nerds being nerdy about randomness! Those test results are spectacular. In fact, those results are so good, I'm guessing a TRNG (clock skew, atmospheric noise, radioactive decay, take your pick) would perform worse (if only slightly). I would like to know how exactly the server-side seed is generated. Do you guys use <a href="http://www.random.org" rel="nofollow">www.random.org</a> 's atmospheric noise, or the common /dev/random noise you find in most computers? How often is that seed generated? Do you know if your seeds have a uniform distribution or a normal curve? Theoretically, none of this should matter, but the seed is as important as the generator. The next step for me is to run my dice through an RNG test; I stopped using online die rollers because they're too good statistically. My group has seen far too many sessions where the GM gets 4 crits across an encounter, and the players rarely roll above a 5 (on a d20). I'd rather a die that had a 7% chance of rolling 15 and a 3% chance of rolling a 20 than a die that was guaranteed to roll all sides evenly.

Well you'll just have to trust that it is a very good source of entropy from a well tested RNG with a uniform distribution which meshes well with our RNG's desired seed pattern. Every time a user loads the Roll20 app new seed data is generated and fed into the RNG as well as as much entropy as we can gather from the user's browser. Running dice through a test would be interesting but considering a simple run of dieharder using the defaults requires over 323 billion random numbers it would be rather hard to test a physical source. Even the Dice-O-Matic &nbsp;can only generate 1.33 million rolls a day which would require 666.2 years to run through the full suite of tests.

David B. said: I'm guessing a TRNG (clock skew, atmospheric noise, radioactive decay, take your pick) would perform worse (if only slightly).&nbsp; This is impossible. A true random number generator is going to produce truly random values; any electronic RNG is going to be psudo- random.&nbsp;

Eric D. said: David C. said: Yes, but when will you create an RNG test that says your RNG gen is good enough? Good job guys, look forward to those bug fixes (the few weaknesses) So your first point isn't actually possible as far as I can tell. As for the second ... I'm guessing you didn't complete the assigned reading from the original post :) The first one is more of a joke, hence the cross out, because it's fallacy in its own right. And I understand that the test may show up strong sometimes and weak other times, but there still always room for improvement.&nbsp; I have no idea how complex the code is you have, so I don't really ever expect it to get updated as it works fine.&nbsp; Dice are as inconclusive as anything else , but I do look forward to that weighted dice RNG But really, there is no perfect RNG.

Okay, my brain ran off screaming for the hills after trying to read the article on P values and only returned after promises of mindless killing on the Xbox for most of this weekend. Good job on being through though! It's always interesting to see how stuff works in the background.

Troy W. said: Okay, my brain ran off screaming for the hills after trying to read the article on P values and only returned after promises of mindless killing on the Xbox for most of this weekend. Good job on being through though! It's always interesting to see how stuff works in the background. Oh you have my sympathies. I have a CS background and while that include some statistics it does not include nearly enough for that article to be an "easy" read. I think I probably went through it a few dozen times to make sure I really understood what was going on.

EDIT BY EricD: Lets keep the flaming to a minimum please

The best place to brush up on this stuff is the classic: The Art of Computer Programming Vol 2 : Semi-Numerical Algorithms by Donald Knuth. The section on RNGs is comprehensive and enlightening. Your brain may still turn to jelly though, depends on your current SAN and the luck of the roll.

Yeah "fixing" the RNG algorithm is something for groups of people with PhD's in lots of arcane math and computer science fields. We're simply using a well known cryptographic RNG algorithm and the tests were done to verify we didn't screw up our implementation of said well known algorithm. As awesome as all the Roll20 devs are writing a from scratch RNG is probably out of our area of expertise :)

Ryan B. said: David C. said: Yes, but when will you create an RNG test that says your RNG gen is good enough? Good job guys, look forward to those bug fixes (the few weaknesses) EDIT BY EricD: Lets keep the flaming to a minimum please Well, you actually can make really superb Random Number Generators and as Eric pointed out, you need math wizards for it, which I expected them to be, since expectations are a great thing to have.&nbsp; EDIT BY EricD: Lets keep the flaming to a minimum please

Ennera said: David B. said: I'm guessing a TRNG (clock skew, atmospheric noise, radioactive decay, take your pick) would perform worse (if only slightly).&nbsp; This is impossible. A true random number generator is going to produce truly random values; any electronic RNG is going to be psudo-random.&nbsp; TRNGs are often electronic, too. You should check out <a href="http://www.random.org" rel="nofollow">www.random.org</a> . Or the processor Intel made that included a TRNG. Did you mean software RNG? There are software RNGs that interact with hard drives, network traffic, interrupts, .... in order to collect entropy, and make some pretty respectable random numbers. Either way, a cryptographic PRNG is unpredictable, which almost always means uniformly distributed. TRNGs, on the other hand, often have a normal distribution. Unless I'm mistaken, that detail alone means that there really isn't a whole lot to be categorically said about TRNGs vs. PRNGs. Random numbers are a pretty cool topic; there's a whole lot more to it than you'd think.

Eric D. said: Well you'll just have to trust that it is a very good source of entropy from a well tested RNG with a uniform distribution which meshes well with our RNG's desired seed pattern. Every time a user loads the Roll20 app new seed data is generated and fed into the RNG as well as as much entropy as we can gather from the user's browser. Running dice through a test would be interesting but considering a simple run of dieharder using the defaults requires over 323 billion random numbers it would be rather hard to test a physical source. Even the Dice-O-Matic &nbsp;can only generate 1.33 million rolls a day which would require 666.2 years to run through the full suite of tests. Yeahno, there was never any possibility of a full, proper dieharder test. I was thinking maybe some of the tests Knuth outlined, or possibly diehard, if I could get a hold of it (and run it). Either way, I need a rig that accomodates d20s first. Preferably unpainted ones like GameScience sells.