LuaRandomGenerator seems to have some monotonic effect with seed

[H8UL]

LuaRandomGenerator seems weirdly monotonic:

Seed 100:

Code: Select all

c global.g.re_seed(100); game.print(global.g(1, 1000)); game.print(global.g(1, 1000))

Result: 11, 329

Seed 350:

Code: Select all

c global.g.re_seed(350); game.print(global.g(1, 1000)); game.print(global.g(1, 1000))

Result: 11, 368


Seed 355:

Code: Select all

c global.g.re_seed(355); game.print(global.g(1, 1000)); game.print(global.g(1, 1000))

Result: 12, 383

I could go on.

Numbers change in some roughly linear pattern. You get a similar effect as you explore other seeds and other ranges of numbers, so I didn't just get lucky.

Why is that? Taking a wild guess, map generation uses the seed to change starting location in some scaled fashion (viewtopic.php?t=31083), so maybe LuaRandomGenerator is designed around that. But I would figure that for general use the random number sequence to have some non-trivial relationship with the seed.

Do we need two LuaRandomGenerators, one with this behaviour for compatibility, one with more general purpose behaviour?

For now, I'm using my own RNG to work around this behaviour, but I ran into a strange Lua bug (viewtopic.php?f=7&t=70571) which made me revisit my choice. Hence this post

Edits: I've edited all my posts here for clarity

[Qon]

You get a similar effect as you explore other seeds.

What effect are you talking about? You just gave me some random numbers and say "Look at these random number! Help!"

What do you want me to do about it? If you don't want them then get new ones.

viewtopic.php?f=23&t=70060&p=425888&hilit=seed#p425879

[Klonan]

For now, I'm using my own RNG to work around this behaviour

There are 4,294,967,296 choices of seed, why is it a problem if values close together have similar sequences?

Is it really a dealbreaker that seed 100 and seed 350 give a similar initial output?

[H8UL]

For now, I'm using my own RNG to work around this behaviour

There are 4,294,967,296 choices of seed, why is it a problem if values close together have similar sequences?

Is it really a dealbreaker that seed 100 and seed 350 give a similar initial output?

It's more that it is highly unusual, and I want to understand it, which is why I raised it in "Modding discussion", and not as a bug report (but yes, in my case, it is a deal-breaker, because I must maintain multiple RNG, and seeding them from one master RNG compounds any artifacts like this).

If you take something really old-school and basic, like linear congruential generator, then it doesn't have this effect.

You get a similar effect as you explore other seeds.

What effect are you talking about? You just gave me some random numbers and say "Look at these random number! Help!"

What do you want me to do about it? If you don't want them then get new ones.

viewtopic.php?f=23&t=70060&p=425888&hilit=seed#p425879

That link you provide is helpful, but it suggests the issue only affects low seeds, but as I said, it affects seeds at any range. If you understand random number generators, you'll know my post wasn't anything like "Look at these random number! Help!" but a set of examples as per the title of the post. Absolutely nobody would expect a seed to have this sort of monotonic effect (sequential seeds can be correlated in trivial PRNG implementations, but in my experience even the notorious C rand() is non-monotonic)

[H8UL]

For now, I'm using my own RNG to work around this behaviour

There are 4,294,967,296 choices of seed, why is it a problem if values close together have similar sequences?

Is it really a dealbreaker that seed 100 and seed 350 give a similar initial output?

Also, it's worth saying, that if close together values in 4,294,967,296 have similar sequences, then effectively we have much less than 4,294,967,296 interesting seeds.

[Klonan]

Also, it's worth saying, that if close together values in 4,294,967,296 have similar sequences, then effectively we have much less than 4,294,967,296 interesting seeds.

That doesn't answer my question, why is not having 4 billion unique and interesting seeds such a negative that you need to implement your own RNG?

[posila]

For reason unknown to me, the generator is initialized as following:

Code: Select all

RandomGenerator::RandomGenerator(uint32_t seed)
  : seed1(seed > DEFAULT_SEED ? seed : DEFAULT_SEED)
  , seed2(seed > DEFAULT_SEED ? seed : DEFAULT_SEED)
  , seed3(seed > DEFAULT_SEED ? seed : DEFAULT_SEED)
{}

where DEFAULT_SEED = 341; so seeds 0 to 341 result in the same sequence and then sequences should be somewhat unique. I don't know why it's like this, and don't care enough about this to investigate it; just dumping bit of inside knowledge.

Computation of the next number in the sequence

Code: Select all

  uint32_t b = (((seed1 << 13) ^ seed1) >> 19);
  seed1 = static_cast<uint32_t>(((seed1 & 4294967294) << 12) ^ b);
  b = (((seed2 << 2) ^ seed2) >> 25);
  seed2 = static_cast<uint32_t>(((seed2 & 4294967288) << 4) ^ b);
  b = (((seed3 << 3) ^ seed3) >> 11);
  seed3 = static_cast<uint32_t>(((seed3 & 4294967280) << 17) ^ b);
  return (seed1 ^ seed2 ^ seed3);

[H8UL]

Also, it's worth saying, that if close together values in 4,294,967,296 have similar sequences, then effectively we have much less than 4,294,967,296 interesting seeds.

That doesn't answer my question, why is not having 4 billion unique and interesting seeds such a negative that you need to implement your own RNG?

The seed issue is not ideal when needing multiple RNG (the birthday problem) but it suggests there may be broader issues, and makes me question whether it would be too specialized for my purposes (which is why I want to understand it). Also, I actually wrote it when I needed an RNG at the data stage (and will do in future). So I had it anyway.

Turning the question on its head.

Why does Factorio's Random Number Generator have this behaviour, when trivial algorithms from the 1970s can give the full 4 billion discontinuous seed space? Why do something different?

This is not a judgement question, there may be good reasons. I want to understand it. Factorio mindset

[H8UL]

For reason unknown to me, the generator is initialized as following:

Code: Select all

RandomGenerator::RandomGenerator(uint32_t seed)
  : seed1(seed > DEFAULT_SEED ? seed : DEFAULT_SEED)
  , seed2(seed > DEFAULT_SEED ? seed : DEFAULT_SEED)
  , seed3(seed > DEFAULT_SEED ? seed : DEFAULT_SEED)
{}

where DEFAULT_SEED = 341; so seeds 0 to 341 result in the same sequence and then sequences should be somewhat unique. I don't know why it's like this, and don't care enough about this to investigate it; just dumping bit of inside knowledge.

Computation of the next number in the sequence

Code: Select all

  uint32_t b = (((seed1 << 13) ^ seed1) >> 19);
  seed1 = static_cast<uint32_t>(((seed1 & 4294967294) << 12) ^ b);
  b = (((seed2 << 2) ^ seed2) >> 25);
  seed2 = static_cast<uint32_t>(((seed2 & 4294967288) << 4) ^ b);
  b = (((seed3 << 3) ^ seed3) >> 11);
  seed3 = static_cast<uint32_t>(((seed3 & 4294967280) << 17) ^ b);
  return (seed1 ^ seed2 ^ seed3);

That's very useful to know, for when I am testing, thanks!

Perhaps it has this minimum because the algorithm fails below 341?

[orzelek]

Code above seems to be Tausworthe generator from GNU science library.
I can't find any info on google why it would treat seeds like that though

[H8UL]

Code above seems to be Tausworthe generator from GNU science library.
I can't find any info on google why it would treat seeds like that though

You are absolutely spot on, it even has the classic parameters.

That's a perfectly good choice of RNG in itself, but the original paper doesn't specify a seeding strategy. Normally you'd use something really simple but discontinuous to set the initial state. Something like what my RNG does is common enough; use a linear congruential generator to convert a single seed into the required discontinuous values. In this case, three seeds. And you can see that is done with the Tausworthe implementation here:

https://github.com/spotify/linux/blob/m ... random32.c

It uses LCG to make the initial state.

Whereas, Factorio's implementation uses the single seed to set the three initial state values. So not only continuous but equal.

This strategy is valid as far as Tausworthe is specified, since a particular sequence will still have good statistical properties. But it has bad properties when comparing seeds. In other words, the more sequences you use in parallel, the more likely you are to find this is a problem, e.g. see something like the birthday problem.

So that's what we've got, a good RNG but with flawed seeding strategy. It explains everything we observe. Easily fixed, though it would impact existing map seeds, so maybe not worth it.

If you use one LuaRandomGenerator in a mod, it's good enough. If you use parallel generators as I do, things might correlate in an undesirable way. In practice it might be fine, and life is too short to worry about statistical properties. But for me writing an RNG was fun, and let's be honest, there's something awesome about knowing your procedurally generated map has a truly huge and diverse space of possibilities