PCG32: The Perfect PRNG for Roguelikes (2018) | Hacker News Reader

PCG32: The Perfect PRNG for Roguelikes (2018)

steveasleep.com

62 pointshenning38 comments

Hi, I wrote this. I'm very surprised it made the front page and I'm a bit embarrassed. People pointing out you can just hash the seed for different "streams" are completely correct, and in video games, people generally don't care about whether two PRNGs are correlated.

I originally found PCG32 because I needed to implement a pure-Swift, cross-platform PRNG for a game jam so my game would run on Linux as well as Mac. For that purpose, it was great.

The problem this seems to be solving, which is that the seeded random number used to generate the level is mixed with the seeded random number used to affect combat.

It just seems trivial to solve though... or maybe I'm getting something wrong... but the solution seems to be to use the seeded random number to generate the level, and then copy the the last output of the random number to seed a new random number controlling combat.

That is, the random number generating the level is immutable with respect to the combat random number?

What am I missing?

I also don't understand, i solved (what i think is) the same problem by having a master rng whose output seeded individual rng, one for map generation, one for enemy ai, one for loot, etc...

This depends on what RNG you are using. If the master and the secondary RNGs use the same algorithm without extra internal states (e.g. splitmix or LCG), you will be generating the same stream over and over with small shifts. The end result may not be obvious in your use case, but can be a catastrophe for statistical simulation or the implementation of dropout. PCG32 is a proper solution. Xorshiro provides another solution by using one simple function to advance the internal state by 2^64 iterations.

BTW, xoroshiro should not be used. See the last section of this:

https://lemire.me/blog/2017/09/08/the-xorshift128-random-num...

I was aware of that blog post as well as the counter argument by the xoroshiro author against PCG. I am not studying RNG and can't say which is more correct. To me, I use xoroshiro mainly because PCG64 is complex to implement. My applications do not need extreme randomness so far.

You're right, it's trivial, and I was dramatically overthinking it when I wrote this article. I expect my blog traffic to be about zero, so sometimes things end up half-baked.

How is "stream" not just half of the seed? This is a property of every PRNG with large enough seed.

Hi, I wrote this post and I've come to agree with you. That's all. :-)

The difference is when you're using many PRNG instances in parallel for SIMD, or threaded, or distributed applications, randomly seeded PRNGs might land close to each other in the sequence and end up correlated with each other, but if you ensure each one has a unique stream that's guaranteed not to happen.

The choice is not "randomly seeded" vs "streams".

If you have a 64 bit seed + 64 bit stream, then it's trivially the same as a 128 bit seed. Just use the top 64 bits of the 128 bit seed as the "stream id".

Partitioning the seed into "seed + ID" only protects you from using the exact same seed for multiple generators, those unique seeds can still begin close to each other in the sequence and overlap their outputs as they step through it. With proper streams every generator has a different sequence so no matter how the seeds are generated, or even if the seeds are the same, they won't overlap each other at any point. For a game it probably doesn't matter, but for more statistically demanding applications it's a nice property to have.

I'm very confused by what you're saying. It seems you're saying that knowing the state of stream 1 teaches me some information about stream 2, specifically that it's guaranteed not to overlap outputs to the first stream. Why is that desirable?

Yeah, I guess you really just need a jump function and then streams are just partitioning the space by whatever distance.

Yes, it works, if you can jump 2^64 iterations quickly. This is how xoroshiro achieves multiple streams. The PCG32 or the xoroshiro method guarantees independent streams. Using high bits in seeds doesn't have the guaranteed behavior. When you have many streams, stream collisions may become an issue.

Right? I'd also be concerned about hash collisions causing one to accidentally generate the same level twice. Seems better to use something like ChaCha; plenty fast and a much large seed space.

To give you a sense of how tiny and simple this excellent pseudorandom number generator is, here is a stand-alone implementation of PCG32 in Go:

  package pcg32

  type Src [2]uint64

  func New(bits1, bits2 uint64) *Src {
      return &Src{bits1, bits2 | 1}
  }

  func (s *Src) Uint32() uint32 {
      var (
          x = s[0]
          y = uint32(x >> 59)
          z = uint32((x>>18 ^ x) >> 27)
      )
      s[0] = s[1] + x*6364136223846793005
      return z>>y | z<<(-y&31)
  }

  func (s *Src) LessThan(n uint32) uint32 {
      for min := -n % n; ; {
          r := s.Uint32()
          if r >= min {
              return r % n
          }
      }
  }

And here's a threadsafe C++ one in <30 lines of meaningful code:

https://github.com/VHRanger/pcg.h/blob/master/pcg.h

I predict that prng will totally fail the DieHard tests.

Does it need to pass them? A stronger algorithm wouldn't hurt, but it's not being used for cryptography or scientific simulations. It's just for games.

With the goal of having sharable seeds, the smaller space could be considered beneficial. The right tool for the job is more important. Even an 8-bit LFSR is good for certain tasks, like randomizing particle effects for an NES game.

PCG is a top-quality pseudorandom number generator, suitable for all non-crypto prng applications

Here are the DIEHARDER results: https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-ra...

Not quite "all prng applications."

As TapamN points out it is not cryptographically secure and can be broken. https://hal.inria.fr/hal-02700791/

But it's probably fine for non-crytographic uses (and indeed is widely used for such).

[parent comment has now added "non-crypto" to the original quote so that "all prng applications" is now moot]

Usually people say CSPRNG if its secure for crypto applications. Just saying PRNG kind of implies its not cryptographically secure

Fair enough.

> It's just for games.

http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont...

https://pellsson.github.io/

Of course, nobody is in danger because your game's random state can be deduced.

But it can disrupt online play quite a bit. Just imagine what this can mean for tournaments.

That's true. I did think about mentioning this possibility, but decided not to.

Another good example of predicting RNG, after a large amount of gameplay, for a non-turn-based game:

https://www.youtube.com/watch?v=1hs451PfFzQ

I think in certain Pokemon games, people figured out how to predict and manipulate random encounters based on an animation in the load screen.

And you'd be wrong

Here: https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-ra...

Ah, I missed that there was a data-dependent rotation applied in the output. So it's a lcg plus xorshift plus ddr. Still weaker than I'd like, but if it passes DieHard etc then it passes.

Yeah, that pseudorandom rotation is what makes PCG novel

I'll read the paper.

I could very well be wrong, I haven't checked yet. That said, I have done a bit of work with these sort of things.

You can get the same result by hashing seed+level_id+some_counter, you don't really need a prng.

The _advance function in this prng is also way too weak, purely linear with a tiny bit of output mixing. Replacing self.state with the (64-bit) result of the xorshifts would help a lot.

Are you claiming that PCG is a bad pseudorandom number generator? If so, you are mistaken

Yes, I predict it will fail most of the DieHard tests.

I like your murmur work, but you're getting it wrong today

Getting it wrong is part of the job.

Agreed. No one should hold it against you

But we have to be careful about claiming that a generator is unreliable. PRNGs are very susceptible to rumor and uncertainty and doubt, because almost nobody understands them

Reply on news.ycombinator.com