Hard Light Productions Forums

Modding, Mission Design, and Coding => FS2 Open Coding - The Source Code Project (SCP) => Topic started by: jg18 on March 24, 2021, 01:19:57 am

Title: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: jg18 on March 24, 2021, 01:19:57 am
The rand() function from cstdlib/stdlib.h is used heavily in FSO and even in FRED, but it has two serious issues:

1. Its behavior is implementation-defined. This is particularly problematic for multiplayer, where players need to be kept in sync.
2. Its output doesn't even remotely resemble true randomness.

A good alternative is the Mersenne Twister (https://en.wikipedia.org/wiki/Mersenne_Twister), which since C++11 is in the C++ standard library as std::mt19937.

As proof of rand()'s implementation-defined behavior, here's a C++ program I wrote:
Code: [Select]
#include <cstdlib>
#include <iostream>
#include <random>

int main() {
    constexpr unsigned int seed = 1234567890;
    srand(seed);

    std::cout << "RAND_MAX: " << RAND_MAX << std::endl; // maximum value rand() can produce
    std::cout << "with seed " << seed << " rand() returns:  ";
    for (int i = 0; i < 10; ++i) {
        std::cout << rand() << " ";
    }
    std::cout << "..." << std::endl << std::endl;

    std::mt19937 mt;
    mt.seed(seed);

    std::cout << "mt19937 min value: " << std::mt19937::min() << " max value: " << std::mt19937::max() << std::endl;
    std::cout << "with seed " << seed << " mt19937 returns: ";
    for (int i = 0; i < 10; ++i) {
        std::cout << mt() << " ";
    }
    std::cout << "..." << std::endl;

    return 0;
}

The output on Windows (MSVC 2019 16.8.3):
Code: [Select]
RAND_MAX: 32767
with seed 1234567890 rand() returns:  1178 3658 9904 19467 9096 19670 28241 27551 24744 17441 ...

mt19937 min value: 0 max value: 4294967295
with seed 1234567890 mt19937 returns: 2657703298 1462474751 2541004134 640082991 3816866956 998313779 3829628193 1854614443 1965237353 3628085564 ...

And on Ubuntu 20.04:
Code: [Select]
RAND_MAX: 2147483647
with seed 1234567890 rand() returns:  1727406014 657320857 2087271152 332581333 1147476310 1208088455 121233336 1334120027 2004824482 1990688704 ...

mt19937 min value: 0 max value: 4294967295
with seed 1234567890 mt19937 returns: 2657703298 1462474751 2541004134 640082991 3816866956 998313779 3829628193 1854614443 1965237353 3628085564 ...


To perform statistical tests of RNG quality, I used PractRand on Ubuntu, using the same RNG seed I used in the code above.

Since the high-order bit of values from rand() is 0 (2147483647 == 0x7fffffff), I have to use every other byte of rand()'s output to get data that has any chance of passing PractRand, but even that doesn't help:
Code: [Select]
RNG_test using PractRand version 0.94
RNG = RNG_stdin, seed = unknown
test set = core, folding = standard(unknown format)

rng=RNG_stdin, seed=unknown
length= 256 megabytes (2^28 bytes), time= 3.2 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+1,13-2,T)                  R= +27.3  p =  1.6e-13    FAIL
  [Low1/8]BCFN(2+0,13-4,T)          R= +64.8  p =  2.9e-28    FAIL !!!
  [Low1/8]BCFN(2+2,13-5,T)          R= +97.2  p =  3.2e-38    FAIL !!!
  [Low1/8]BCFN(2+3,13-5,T)          R= +47.8  p =  7.0e-19    FAIL !
  [Low1/8]BCFN(2+4,13-5,T)          R= +20.8  p =  2.4e-8   very suspicious
  [Low1/8]DC6-9x1Bytes-1            R=+376.8  p =  6.4e-253   FAIL !!!!!!
  [Low1/8]BRank(12):1K(1)           R=+238.9  p~=  6.1e-73    FAIL !!!!
  [Low1/32]BRank(12):512(1)         R=+238.9  p~=  6.1e-73    FAIL !!!!
  ...and 205 test result(s) without anomalies

The results with std::mt19937 using all bytes of its generated numbers:
Code: [Select]
RNG_test using PractRand version 0.94
RNG = RNG_stdin, seed = unknown
test set = core, folding = standard(unknown format)

rng=RNG_stdin, seed=unknown
length= 256 megabytes (2^28 bytes), time= 3.6 seconds
  no anomalies in 213 test result(s)

rng=RNG_stdin, seed=unknown
length= 512 megabytes (2^29 bytes), time= 7.3 seconds
  no anomalies in 229 test result(s)

rng=RNG_stdin, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 14.4 seconds
  no anomalies in 248 test result(s)

rng=RNG_stdin, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 27.8 seconds
  no anomalies in 266 test result(s)

rng=RNG_stdin, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 53.0 seconds
  no anomalies in 282 test result(s)

rng=RNG_stdin, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 107 seconds
  no anomalies in 299 test result(s)

For a bit on how Mersenne Twister makes for a strong RNG for games, see this Gamasutra article (https://www.gamasutra.com/view/news/320213/How_classic_games_make_smart_use_of_random_number_generation.php) (scroll to the section on Pokemon).

Thoughts?

EDIT: Here are PractRand results for MT up to 64 GB, using the same seed as before, with PractRand configured to evaluate the input as 32-bit values:
Code: [Select]
RNG_test using PractRand version 0.94
RNG = RNG_stdin32, seed = unknown
test set = core, folding = standard (32 bit)

rng=RNG_stdin32, seed=unknown
length= 256 megabytes (2^28 bytes), time= 2.7 seconds
  no anomalies in 165 test result(s)

rng=RNG_stdin32, seed=unknown
length= 512 megabytes (2^29 bytes), time= 5.3 seconds
  no anomalies in 178 test result(s)

rng=RNG_stdin32, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 10.4 seconds
  no anomalies in 192 test result(s)

rng=RNG_stdin32, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 20.2 seconds
  no anomalies in 204 test result(s)

rng=RNG_stdin32, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 39.4 seconds
  no anomalies in 216 test result(s)

rng=RNG_stdin32, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 78.6 seconds
  no anomalies in 229 test result(s)

rng=RNG_stdin32, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 155 seconds
  no anomalies in 240 test result(s)

rng=RNG_stdin32, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 305 seconds
  no anomalies in 251 test result(s)

rng=RNG_stdin32, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 654 seconds
  no anomalies in 263 test result(s)
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: The E on March 24, 2021, 08:13:23 am
As far as I am concerned, this is a simple decision. We have a need for consistent cross-platform behaviour, and if this is something that doesn't follow that, we should fix it.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: Phantom Hoover on March 24, 2021, 10:09:46 am
2. Its output doesn't even remotely resemble true randomness.

In principle this is what FSO's static_rand functions are for, but they're based on doing some dumb twiddling with a static array obtained directly from rand() and so are tragically unfit for purpose.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: Phantom Hoover on March 24, 2021, 10:13:09 am
https://github.com/scp-fs2open/fs2open.github.com/blob/master/freespace2/freespace.cpp#L904

Yeah the current RNG system is totally unfit for purpose on multiplayer, agree that it should be replaced with an MT rand instead.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: Goober5000 on March 25, 2021, 07:30:29 pm
As far as I am concerned, this is a simple decision. We have a need for consistent cross-platform behaviour, and if this is something that doesn't follow that, we should fix it.

Agreed.  We have fixed rand on two (https://www.hard-light.net/forums/index.php?topic=91576.0) previous (https://www.hard-light.net/forums/index.php?topic=57880.0) occasions after all.


A good alternative is the Mersenne Twister (https://en.wikipedia.org/wiki/Mersenne_Twister), which since C++11 is in the C++ standard library as std::mt19937.

This sounds like a good idea, but I would also be interested in your opinion on the xorshift1024* generators described here (https://en.wikipedia.org/wiki/Xorshift#xorshift.2A) and here (http://xorshift.di.unimi.it/) (to resume where the previous thread left off).
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: jg18 on March 25, 2021, 11:52:52 pm
A good alternative is the Mersenne Twister (https://en.wikipedia.org/wiki/Mersenne_Twister), which since C++11 is in the C++ standard library as std::mt19937.

This sounds like a good idea, but I would also be interested in your opinion on the xorshift1024* generators described here (https://en.wikipedia.org/wiki/Xorshift#xorshift.2A) and here (http://xorshift.di.unimi.it/) (to resume where the previous thread left off).
Thanks for sharing, but I don't see any references to xorshift1024* in the second page you linked.

Unfortunately, it doesn't strike me as a good alternative, given that I can't find references to its use in games (as opposed to MT, see the Gamasutra article I linked to in the OP), am not aware of a standard implementation we could use, its output is 64-bit values (hard to work with and implying more expensive operations than we'd want), and it still fails statistical tests (https://www.sciencedirect.com/science/article/abs/pii/S0377042718306265?via%3Dihub).

Mind you, MT will fail statistical tests if you give the test a large enough sample (a gigantic period won't save you), but IIRC that's like hundreds of GB, way more than we'd care about, and MT is still clearly many orders of magnitude better than what we have now.

That said, I'll make sure that my experimental branch on this doesn't tie us to MT. I intend to make it compatible with any engine that implements the functions expected for engines in the <random> header (e.g., operator()(), discard(), min(), max(), etc.)

Speaking of discard() (https://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/), given the MT's mindbogglingly huge period, perhaps a SEXP to jump ahead in the RNG sequence would be useful? That would likely be a lot easier for FREDders to work with than re-seeding.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: Colonol Dekker on March 26, 2021, 02:20:12 am
I love lurking on these threads to see how you guys keep Freespace looking shiny, and add new and interesting features to the engine.

But coding is not my kung fu and I am unable to process your input.   All I'll say is you guys keep doing this stuff and Freespace will never die.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: Goober5000 on March 26, 2021, 12:00:40 pm
Thanks for sharing, but I don't see any references to xorshift1024* in the second page you linked.

It's called xoroshiro1024* on that page.  It's an xorshift-based RNG and the name stands for XOR/rotate/shift/rotate.

Quote
Quote
Unfortunately, it doesn't strike me as a good alternative, given that I can't find references to its use in games (as opposed to MT, see the Gamasutra article I linked to in the OP), am not aware of a standard implementation we could use, its output is 64-bit values (hard to work with and implying more expensive operations than we'd want), and it still fails statistical tests (https://www.sciencedirect.com/science/article/abs/pii/S0377042718306265?via%3Dihub).

Mind you, MT will fail statistical tests if you give the test a large enough sample (a gigantic period won't save you), but IIRC that's like hundreds of GB, way more than we'd care about, and MT is still clearly many orders of magnitude better than what we have now.

The main reason I was interested in xorshift was that it allegedly passed all the tests in BigCrush whereas MT failed at least one of them.  But if it takes hundreds of GB of numbers for the failure to be evident, then that's not worth quibbling about.

Reading the abstract for the linked article, I'm uncertain as to its applicability:


I'm not sure why you would want to take the 32 lowest-order bits in reverse order.


Quote
Speaking of discard() (https://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/), given the MT's mindbogglingly huge period, perhaps a SEXP to jump ahead in the RNG sequence would be useful? That would likely be a lot easier for FREDders to work with than re-seeding.

It's certainly an option, but how exactly would it be easier for FREDders?
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: jg18 on March 26, 2021, 08:35:44 pm
Thanks for sharing, but I don't see any references to xorshift1024* in the second page you linked.

It's called xoroshiro1024* on that page.  It's an xorshift-based RNG and the name stands for XOR/rotate/shift/rotate.
Okay.

Unfortunately, it doesn't strike me as a good alternative, given that I can't find references to its use in games (as opposed to MT, see the Gamasutra article I linked to in the OP), am not aware of a standard implementation we could use, its output is 64-bit values (hard to work with and implying more expensive operations than we'd want), and it still fails statistical tests (https://www.sciencedirect.com/science/article/abs/pii/S0377042718306265?via%3Dihub).

Mind you, MT will fail statistical tests if you give the test a large enough sample (a gigantic period won't save you), but IIRC that's like hundreds of GB, way more than we'd care about, and MT is still clearly many orders of magnitude better than what we have now.

The main reason I was interested in xorshift was that it allegedly passed all the tests in BigCrush whereas MT failed at least one of them.  But if it takes hundreds of GB of numbers for the failure to be evident, then that's not worth quibbling about.
I re-tested MT using the same seed as before up to 64 GB (results appended to OP) and PractRand is still fooled. If, after generating over 17 billion values, PractRand doesn't suspect a thing, then I'd say it's good enough for our purposes. I've worked a fair bit with PractRand and have found it to be pretty sensitive.

Here's an example (https://www.johndcook.com/blog/2017/08/14/testing-rngs-with-practrand/) of (64-bit) MT failing with PractRand after 512 GB.

Reading the abstract for the linked article, I'm uncertain as to its applicability:

  • "Unlike their unscrambled counterparts, [Vigna's scrambled generators] pass Big Crush when interleaving blocks of 32 bits for each 64-bit word"
  • "We report that these scrambled generators systematically fail Big Crush when taking the 32 lowest-order bits in reverse order from each 64-bit word."

I'm not sure why you would want to take the 32 lowest-order bits in reverse order.
Fair point with respect to our needs. I think the authors' point was that you can still find non-randomness in these RNGs' output.

In any case, AFAIK my other concerns about xorshift1024* from before still stand, and MT addresses all of them.

Speaking of discard() (https://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/), given the MT's mindbogglingly huge period, perhaps a SEXP to jump ahead in the RNG sequence would be useful? That would likely be a lot easier for FREDders to work with than re-seeding.

It's certainly an option, but how exactly would it be easier for FREDders?
I guess it depends on whether the FREDder is looking to get predictable behavior, which of course you get if you select the same seed every time. My FREDding experience is limited to a simple mission back in 2012, so I wouldn't really know what RNG-related functionality would be of use. I was just putting an idea out there.

Speaking of putting ideas out there, PR is up (https://github.com/scp-fs2open/fs2open.github.com/pull/3332). There are a bunch of things to discuss as part of the review. I also fixed a few bugs and spotted a few potential bugs along the way, but since addressing them may affect gameplay, we should definitely talk about them on the PR page.

I tested this (albeit not the latest revision) by playing "A Lion at the Door" from FS2 main campaign and seemed ok, no crashes and nothing obviously amiss.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: 0rph3u5 on March 31, 2021, 09:28:45 am
I guess it depends on whether the FREDder is looking to get predictable behavior, which of course you get if you select the same seed every time. My FREDding experience is limited to a simple mission back in 2012, so I wouldn't really know what RNG-related functionality would be of use.

There are four main uses to from randomisation I can think of on the top of my head:

- To inject variance into replaying a mission (e.g. using randomisation to change the starting position of the player, see SerRes The Spirit of Ptah, Mission 5 or the FS-Blue version of As Lighting Falls).
- To inject variance into repeating events (see the send-random-message SEXP or building the same mechanism with a nested event).
- To cover the most obvious artifice of some of a mission's events (e.g. randomized delay to arrival of follow up wings/waves or message responding to events)
- For bulk task that require some variation (e.g. randomizing the integrety of subsystems and turrets on a ship that is suposed to be damaged at the start of the mission)

EDIT: I highly recommend to take a look behind the curtain of the SerRes-campaigns - Mobius likes to inject a lot of minor variations into his missions via randomisation.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: 0rph3u5 on March 31, 2021, 10:12:57 am
Sry for the double post

As for additional features, I don't see (yet) in the current rand and rand-multipe operaters in FRED but would be nice to have:

1) to have an option to enable an inherent protection against the chase that if an event using a rand-multiple operation is called multiple times that it doesn't return same number in repetition.

E.g. In Vega Must Burn I have a mission during which a Hammer of Light-propaganda broadcast is supposed to play as long as a ship broadcasting it is in the mission - it is meant to be a distraction as an element of psychological warfare). At present I do it with randomized variable and nested whens for each value the variable can be (it is easier to check it's function that way rather than using send-random-message. Ideally, no message should repeat back to back (it randomizes from 1-34; additional values of 0 calling up a debug message and 35 as value to stop of the event from sending a second message) but it still happens.



2) to have an option that numbers cannot repeat if an event using rand-multipe is called multiple times (bascially replacing rolling dice with drawing cards)

E.g. Also in Vega Must Burn I have a mission for which the cargo strings of 24 ships are randomized in such a way that of three possible strings, a group of 4 ships always as at least 1 of each cargo string (so any combination of ABCA, ABCB, ABCC) but also each string doesn't exist more than 8 times across all 24 ships. At present that requires a complex group of events using multiple variables that need to execute/repeat in tightly controlled sequence.



I can, of course, create both in FRED as is using control variables, nested whens and a tighly controlled sequence for the events to happen (milisecond intervalls have made this much easier) - but if that kind of functionality could be put into the a new version of the randomisation operations it would be really cool.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: karajorma on March 31, 2021, 07:49:10 pm
While I like the idea of both of the features you mention, neither of them are random. In a random function that has played one message, the likelihood that the exact same message is played the next time MUST be the same as the chance of any individual other message being played. For the first one, couldn't you just use an argument list of message names, rand-multiple-of, and invalidate-argument?
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: General Battuta on March 31, 2021, 11:03:10 pm
Mersenne Twister? I barely know 'er!!!!!
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: General Battuta on March 31, 2021, 11:05:30 pm
While I like the idea of both of the features you mention, neither of them are random. In a random function that has played one message, the likelihood that the exact same message is played the next time MUST be the same as the chance of any individual other message being played. For the first one, couldn't you just use an argument list of message names, rand-multiple-of, and invalidate-argument?

Yeah this is the correct solution for "draw cards from a deck", just invalidate arguments when you don't want them to go back into the deck.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: 0rph3u5 on April 01, 2021, 04:19:29 am
While I like the idea of both of the features you mention, neither of them are random. In a random function that has played one message, the likelihood that the exact same message is played the next time MUST be the same as the chance of any individual other message being played.

I know they are not strictly random, but I was wondering - due to my lack of knowledge of the programming side of this - if these could be implimented along with the change in how random numbers are generated. As I said, I can do both and have done both - just wondering if there is a way to make it simpler. If there is none than I am okay with that.

I am happy to privately give you, and jr18, a look into the missions from Vega Must Burn and discuss what I am doing there behind closed doors - I am back on the HLP discord at the moment, so my privacy settings shouldn't keep both of you from contacting me.

Quote
For the first one, couldn't you just use an argument list of message names, rand-multiple-of, and invalidate-argument?

In this particular case it build it so because I wanted to be able to circumvent the "shuffle" and test the messages individually - that's why I am not using the arguments list here. What you are suggesting I've also used to randomize cargo strings when there is no or few additional considerations.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: karajorma on April 01, 2021, 08:23:22 am
Ah, fair enough. If you've been watching the containers thread, you'll know that jg18 and I are working together on another system that would give you the ability to do what you want. A list of message names would allow you to test things sequentially and with a minor change make that random.

To be honest, I really think you should take a look at it either way as I suspect you'd be one of the first FREDders to start using containers once you realise all the fantastic tricks they'll make easier/possible.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: jg18 on May 04, 2021, 08:36:14 pm
:bump:

The RNG upgrade was just merged and will appear in the next nightly build.

Since the game is now more "random", I'll be curious to see if that has any effect on player experience. Nothing seemed obviously amiss when I played "A Lion at the Door" from FS2 main campaign on Medium difficulty.

Special thanks to everyone who helped out with the PR review. :)
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: 0rph3u5 on May 05, 2021, 04:46:16 am
Nice.  Getting ready for testing...

(https://memecreator.org/static/images/memes/5307114.jpg)
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: Phantom Hoover on May 06, 2021, 03:35:10 am
I strongly doubt this will have any noticeable effect on gameplay, as the previous rand() implementation was already totally different (and indeed returned 32-bit numbers rather than 16-bit ones) on Linux and Mac, and nobody ever saw anything different.
Title: Re: Time to ditch rand() for a better RNG. How about Mersenne Twister?
Post by: 0rph3u5 on May 06, 2021, 03:24:34 pm
When I trust the RNG to basically make entire navigation focussed missions for me, I better test it regardless.  ;)