Hacker News new | past | comments | ask | show | jobs | submit login

"After consulting with several other Rioters, our team settled on developing a new PRNG implementation based on XOR-SHIFT."

I wonder why?






The xorshift family is one of the top two RNGs in the modern day (the other being PCG). Unfortunately, "choosing the ideal member of the family" is nontrivial if you're trying to eke out every bit of performance.

The problem with the xorshift family is that it doesn't implement the nice auto-scaling (and thus auto-testing) that PCG has. Re-parameterizing it means inventing whole new numbers from scratch and hoping you plug them in correctly. Xorshift also has a rare-but-severe "stuck near zero" problem.

The problem with the PCG family is that its trusted way of scaling (nobody likes the `_k` variants) relies on 128-bit multiplication (a modern member of the family at least reduces that to a mixed 128x64 multiply), which remains notably slow, unlike xorshift which only uses small integers.

(But I must emphasize: all RNGs from other families either have worse variants of these problems, or give up on performance entirely. These concerns should be used only to select your preferred tradeoff between the two, there is no excuse for ever using any other RNG family unless you need cryptographic security)


"It’s simple, fast, and has a great distribution, which means it’s more than good enough for gameplay."

Its distribution is not flawless, but I would agree that it's good enough for gameplay.


This! We don't use it for mission-critical crypto or the like. It's there to figure out whether a bot goes left or right. Given the enormous complexity of the League game state and input surface area, it likely won't be a concern unless someone devises a way to exploit it for RNG manipulation (this seems unlikely.)

The reason we didn't use crand was just code ergonomics. C-style rand has global state (by default) and we wanted our own interface to be explicit in the code so you knew when you were using a gameplay-impacting random number.


Likely performance. You can do xor and shift operations essentially for free on a modern pipelined CPU.

Other techniques, such as linear congruential generators, require multiplication and division.


Besides the other answers, could also be that they wanted to make sure they had their hands on a fully deterministic implementation across different hardware/software stacks (like Windows and OS X).

As a sidenote on a project the size of LoL, the time, size and cost of implementing a PRNG based on a known one is a rounding error.


underscores



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: