BYOND RNG

[tacolizard]

So with https://github.com/tgstation/tgstation/pull/30087 on the way, I decided to start considering coding a new RNG system, to be hopefully more random than BYOND's inbuilt RNG. After all, we could use a variety of pseudorandom data for generating seeds, such as messages sent over radio, ahelps/adminpms, mob positions, admin notes, crafted items, etc. However, according to Remie:


Now before I go and commit on working on this RNG project, I want people to really give me solid evidence that BYOND's RNG is "bad". I've heard it said many times, but I would really like some examples/explanations of how limited it is.



I'm not advocating rebuilding RNG from scratch, just combing player generated data with BYOND's rand()

[TribeOfBeavers]

What is BYONDs built in RNG based on?

[tacolizard]

What is BYONDs built in RNG based on?

~~it's based on system data, though I don't think anyone knows exactly what.~~ I think it is known to be rather time-dependent, so the biggest issue is with trying to generate a bunch of random values very quickly, although our code doesn't really do that

[Qbopper]

my response is

what would the benefit of a new RNG system be

even if byond's RNG isn't totally random, why is it such a big deal that we need a new system

[kevinz000]

my response is

what would the benefit of a new RNG system be

even if byond's RNG isn't totally random, why is it such a big deal that we need a new system

yeah ok what do we need this stuff for..?
combat rng?

[Steelpoint]

Viro is the main system I can think of that would benefit from a RNG rework.

[Remie Richards]

Byond (supposedly) uses the base C implementation of rand(), which varies upon platform
glibc (GCC, most popular c compiler iirc) uses a Linear Congruential Generator

GCC uses the constants 1103515245, 12345 and 2^31 -1, meaning the random number produced is seed2 = 1103515245 * seed1 + 12345 % 2^31 -1

When the very first RNG number is produced, seed1 is the world.time value at that time (which is a value in deciseconds (1/10 of seconds))
seed2 is your pseudo random number, which will then be used as the seed1 for the next number
at any point however you can call random_seed(some_seed) to change the value of seed1

As with all seeded pseudo random number generators, this means that if the events play out in the exact same order, then you will get the exact same sequence of numbers.

Here's some C# code where I've (attempted) to implement byond's rand() using GCC's constants for an LCG
http://rextester.com/AGRFG97976

Running this (without changing the seed I chose, 42) will get you:

5 rand() calls (0,1) //rand() with no args in DM means "give me a value between 0 and 1", though as you'll see in the C# code the max is actually the highest possible 32 bit integer value
Next Seed: 1,250497E+09 Normalised: 0,5823079 //(You get commas here because Rextester is german, and europeans do it that way for some reason (I know they're german because during testing I got 'unendlich' which is german for infinity))
Next Seed: 7,669473E+08 Normalised: 0,3571377
Next Seed: 6,20245E+08 Normalised: 0,2888241
Next Seed: 9,851494E+08 Normalised: 0,458746
Next Seed: 4,482785E+08 Normalised: 0,208746

5 rand(1, 10) calls //I don't trust the numbers in this section much, as I hate normalising numbers to begin with, but it's still an ok-ish example.
Next Seed: 1,250497E+09 Normalised: 8
Next Seed: 7,669473E+08 Normalised: 8 //~byond rng~
Next Seed: 6,20245E+08 Normalised: 2
Next Seed: 9,851494E+08 Normalised: 1
Next Seed: 4,482785E+08 Normalised: 8 //too many 8s

A fun seed to try is 45, which for rand(1,10) TRULY summons byond rng by producing 8,8,4,8,8 (Which is how we end up with WIZARD, WIZARD, TRAITOR, WIZARD, WIZARD, WIZARD, WIZARD...)
If you feel like it, try and find a seed which produces the same number 5 times)

As you can see, the dreaded "Byond rng" has produced the same number 3 times out of 5, but that's just what you get with a simple PRNG like LCGs.
I haven't tested if these are the exact numbers byond produces, but it's a decent enough example of an LCG.
I hope this helps you with understanding (P)RNGs, if you REALLY want to go on this (imo unnecessary) venture, I would look into implementing a mersene twister

Also sorry if parts of this are a bit scatter brained, I wrote this in one go over a lunch break.

[pubby]

Here's some C# code where I've (attempted) to implement byond's rand() using GCC's constants for an LCG
http://rextester.com/AGRFG97976

Using floats makes this wrong, wrong, wrong, wrong. You need to use unsigned integers with the correct bit count.

Random sequences are always going to have strings of consecutive repetition. That is what true randomness is. Often times people expect randomness to always change the result, but that is just foolish humans being foolish humans.

LCG is good enough. Unless you plot it in multiple dimensions and look at the planes, you won't be able to tell it's not perfect randomness. A more likely source of error in the implementation is using modulo to crop the results. Modulo biases towards factors of RAND_MAX. And speaking of RAND_MAX, it's only 32767 on Windows. BYOND might not handle it correctly.

Of course, there may also be seed fuckery going on. I would look into the seed before ever touching the RNG engine itself.

[Remie Richards]

I'm well aware floats are wrong, but Byond only has floats in DM land, though in actuality rand() only returns a float when it's in no-arg territory, so I should have used two different vars (float + int) rather than cramming them both in a float for the rand() function itself.

I never said random sequences having repetition isn't random, where are you getting that from?

I'm well aware LCG is good enough, it's my entire argument??

Lastly, this is an example, I'm well aware it's not amazing by any standards (I wrote it over a lunch break, as I said) but that's not necessary to get the point across.

tl;dr not relevant.

[pubby]

My first paragraph was in response to you, but the rest were in response to the thread in general.

[Remie Richards]

If that's the case, is it not actually:
me,
thread,
me,
thread

Given you start talking about modulo cropping results.

[tacolizard]

So your post appears to say that there IS in fact a problem with BYOND RNG, yet you also say it's fine. Why?

[Remie Richards]

I said nothing of the sort, I merely showcased an issue with all prngs, there is no such thing as a real rng

[XDTM]

I just know that playing viro for a long period i always had the impression that the RNG got "stuck" on a certain set of results, which shifted very slowly over time. Effectively this meant that to get the full set of symptoms i wanted i had to take a break of 5-10 minutes for the set to change so i could get the last few.

[oranges]

you are imagining things