6 ms·

> A unit test could have caught this I've always wondered the best way to write tests for "This event should happen x% of the time." Obviously we could re-run

by SamBam 4y ago

> A unit test could have caught this I've always wondered the best way to write tests for "This event should happen x% of the time." Obviously we could re-run the test 100 times and see if it happened close to x%, but not only is that inefficient, how close is "close"? You'll get a bell curve (or similar), and most of the time you'll be close to x but sometimes you'll be legitimately far away from x and your test will fail. You could start from a known seed, but then are you really testing the percentages, or just checking that the RNG gives you the same output for the same seed, which you already know?

hashkb 4y ago
You can mock the RNG. You don’t need to test/prove it’s random, you need to test your code which is not random.
- hinkley 4y ago
  unit tests are notoriously bad about testing n>2. I just ran into a problem with sorting recently that was caused by buggy comparators, but it didn't bubble up to the tests until the runtime switched to a different sort implementation. Most of the tests were doing n=2 so it was not visible under the old runtime version but was under the new one. This has been broken in production for months if not years. If the test had used n=5 I'm pretty sure the old tests would fail as well.
delecti 4y ago
You would probably not test "happens x% of the time", but rather that for a given set of inputs, passing in 0.1, 0.2, 0.3, etc, let you have the expected outcomes across the distribution. So you're testing that you can achieve each outcome across the spectrum with a pre-selected "random" number.
jerf 4y ago
In the similar situations I've run, what I've often done is: 1. Start with a known seed. 2. Run a single test run like what you say, and verify this run by hand. 3. Freeze the test in this state, that is, assert you get that exact result every time on the given seed. What this creates is not what I would strictly speaking call a "unit test", but it does sort of pin the algorithm to your examined and verified output. In this case, a human would quite likely have caught this problem on a decent test set. Obviously, there are other pathologies that would slip right by a human; the human being careful only raises the bar for such pathologies, it doesn't completely eliminate them. But at least freezing it solves the problem where a change you did not realize would be a change slips by unnoticed and this function suddenly has a completely different outcome. This has worked for me, in the sense it has caught a couple of bugs that would have had non-trivial customer implications. But I've never worked on an MMORPG or anything else where randomness was intrinsic to my problem; it has always been incidental, like, is my password generation algorithm correct and does this sample of my data look like what I expect, not the core of my system.
pkhuong 4y ago
> I've always wondered the best way to write tests for "This event should happen x% of the time." I use https://github.com/pkhuong/csm/blob/master/csm.py https://github.com/pkhuong/csm/blob/master/csm.py to set a known false alarm rate (e.g., one in a billion) and test that some event happens with probability in a range [lo, hi], with lo < expected < hi (e.g., expected +/- 0.01). The statistical test will run more iteration as needed. If that's too slow, you can either widen the range (most effective), or increase the expected rate of false alarms (not as effective, because the number of iteration scales logarithmically wrt false alarms).
OkayPhysicist 4y ago
I'm not a fan of the set-seed solution. In the past, when I've tested PRNG implementations (Erlang used to not have the ability to have multiple, independently seeded RNGs), my approach was to decide on an acceptable rate of false negatives, and design my test around that. I figured I'd run the test suite no more than 10,000 times, and I wanted a 1/1,000,000 chance of ever seeing a false negative. I can't remember the exact math I used at the time (I had to crack open a stats textbook), but ultimately it boiled down to generating a bunch of (seed, number of values previously pulled based on that seed, value) tuples, running a linear regression against them, and defining a maximum acceptable R^2 value based on my 10^-30 acceptable probability of a false fail. When the RNG is not the thing being tested, mocking the RNG to do a sampled sweep through the RNG's output range is typically the correct move.
perlgeek 4y ago
This is pretty hard to black-box test. What would have helped in this case: * Test that all players can be selected by the algorithm at all * Test that the totals of the weights is the same as the RNG max range
- hinkley 4y ago
  Scatter plots are good when you can't exhaustively test.
TheRealPomax 4y ago
100? Let's make that 100,000 instead, and then you check the resulting distribution. It's a unit test, not an integration test: this will run very quickly. Even on 1999 hardware.

by SamBam 4y ago

hashkb 4y ago

You can mock the RNG. You don’t need to test/prove it’s random, you need to test your code which is not random.

hinkley 4y ago
unit tests are notoriously bad about testing n>2. I just ran into a problem with sorting recently that was caused by buggy comparators, but it didn't bubble up to the tests until the runtime switched to a different sort implementation. Most of the tests were doing n=2 so it was not visible under the old runtime version but was under the new one. This has been broken in production for months if not years. If the test had used n=5 I'm pretty sure the old tests would fail as well.

delecti 4y ago

You would probably not test "happens x% of the time", but rather that for a given set of inputs, passing in 0.1, 0.2, 0.3, etc, let you have the expected outcomes across the distribution. So you're testing that you can achieve each outcome across the spectrum with a pre-selected "random" number.

jerf 4y ago

In the similar situations I've run, what I've often done is: 1. Start with a known seed. 2. Run a single test run like what you say, and verify this run by hand. 3. Freeze the test in this state, that is, assert you get that exact result every time on the given seed. What this creates is not what I would strictly speaking call a "unit test", but it does sort of pin the algorithm to your examined and verified output. In this case, a human would quite likely have caught this problem on a decent test set. Obviously, there are other pathologies that would slip right by a human; the human being careful only raises the bar for such pathologies, it doesn't completely eliminate them. But at least freezing it solves the problem where a change you did not realize would be a change slips by unnoticed and this function suddenly has a completely different outcome. This has worked for me, in the sense it has caught a couple of bugs that would have had non-trivial customer implications. But I've never worked on an MMORPG or anything else where randomness was intrinsic to my problem; it has always been incidental, like, is my password generation algorithm correct and does this sample of my data look like what I expect, not the core of my system.

pkhuong 4y ago

> I've always wondered the best way to write tests for "This event should happen x% of the time." I use https://github.com/pkhuong/csm/blob/master/csm.py https://github.com/pkhuong/csm/blob/master/csm.py to set a known false alarm rate (e.g., one in a billion) and test that some event happens with probability in a range [lo, hi], with lo < expected < hi (e.g., expected +/- 0.01). The statistical test will run more iteration as needed. If that's too slow, you can either widen the range (most effective), or increase the expected rate of false alarms (not as effective, because the number of iteration scales logarithmically wrt false alarms).

OkayPhysicist 4y ago

I'm not a fan of the set-seed solution. In the past, when I've tested PRNG implementations (Erlang used to not have the ability to have multiple, independently seeded RNGs), my approach was to decide on an acceptable rate of false negatives, and design my test around that. I figured I'd run the test suite no more than 10,000 times, and I wanted a 1/1,000,000 chance of ever seeing a false negative. I can't remember the exact math I used at the time (I had to crack open a stats textbook), but ultimately it boiled down to generating a bunch of (seed, number of values previously pulled based on that seed, value) tuples, running a linear regression against them, and defining a maximum acceptable R^2 value based on my 10^-30 acceptable probability of a false fail. When the RNG is not the thing being tested, mocking the RNG to do a sampled sweep through the RNG's output range is typically the correct move.

perlgeek 4y ago

This is pretty hard to black-box test. What would have helped in this case: * Test that all players can be selected by the algorithm at all * Test that the totals of the weights is the same as the RNG max range

hinkley 4y ago
Scatter plots are good when you can't exhaustively test.

TheRealPomax 4y ago

100? Let's make that 100,000 instead, and then you check the resulting distribution. It's a unit test, not an integration test: this will run very quickly. Even on 1999 hardware.