Re:Predictably Random
by OskarS on Tuesday August 13, 2019 @09:30AM
(#20685605)
Hubba bubba. This is maybe not the article to read if you want to learn how to implement randomness correctly. There's... many things wrong with it.
Of course randomA is terrible, you're modding it with 16! It's never going to have a period longer than 16 like that! Same with randomB, just with a slightly larger number. Both of these are just bog-standard linear congruential generators. LCGs are pretty bad for anything "serious", but for picking Tetris pieces they're fine, and they're easy to implent (or at least I thought they were, but then you see an article like this where one of them has period 16...). I don't immediately recognie randomC(), but it also looks terrible. Just shifting some bits around and adding a counter. At least it has some internal state so it it's not stupidly periodic.
I haven't read up on what's the issue with V8's Math.random(), but I would have to imagine it's superior to all these three. I'm also sure there's plenty of excellent randomness libraries (and plenty of terrible ones) on NPM.
Also, this kind of visual inspection will weed out truly garbage PRNGs, but it's not a good test in general. Testing for pseudo-randomness is hard, and best left to people who know what they are doing.
Also also: for Tetris, you shouldn't just pick pieces at random, that's not how Tetris works nowadays. Tetris works by putting all 7 pieces in a bag, and then pulling them out at random. When the bag is empty, you fill it again with the seven pieces and start over. More info here: [0]. If you're new to programming, implementing the 7-bag system properly is a good little challenge, you'll get to learn all about the Fisher-Yates shuffle [1].
Re:Predictably Random
by 60654 on Tuesday August 13, 2019 @10:06AM
(#20685940)
The third one looks like a LFSR [0]. I didn't recognize it at first because the factors used here are not the common ones that produce well known periods; not sure what period this one would have.
For what it's worth, LFSRs can be nice for generating random sequences with periods of predictable length - and they're cheap! They also recently got a bit of a publicity bump with the rediscovery of how Doom used one for the "death fade" transition, that randomly but exhaustively overpainted all screen pixels with blood red. [2]
But in general - yeah, there's a lot to consider with picking RNGs, not the least of which being context. For games Xorshift is often a good enough choice because it's fast, small, and the game environment is chaotic already (because of the unpredictable players) so there is rarely need for something much stronger.
Re:Predictably Random
by OskarS on Tuesday August 13, 2019 @10:32AM
(#20686183)
Fair enough, I was perhaps a bit dismissive of that one and should have looked closer. LFSR can certainly be perfectly acceptible PRNGs for this kind of game.
By the way, Doom's random number generator for the game mechanics... not so fantastic [0] :)
> you shouldn't just pick pieces at random, that's not how Tetris works nowadays.
It's a purely abstract game with endless possibilities for how it can be made. That's what makes it timeless. There's no reason you have to use bag randomizer in your own personal projects. That is, unless you feel some strange need to check off boxes to comply with what the current IP holders happen to prescribe at a particular moment in time.
In fact, there's an argument for using a memoryless randomizer: it maximizes variation, unpredictability, and increases challenge.
Re:Predictably Random
by OskarS on Tuesday August 13, 2019 @10:24AM
(#20686099)
You speak of Tetris like it's some abstract concept that has always existed and is like some eternal truth. It's not: it's a game that was created by one man, Alexey Pajitnov, who also just happen to be "the current IP holder" you dismiss so easily (he's the co-owner of the Tetris Company).
So no, it's not an "abstract game with endless possibilities". Tetris is Tetris, a concrete game made by a great game designer. It gets cloned and copied constantly, so much so that people forget that it was actually authored by a person. Comments like yours erase Pajitnov's authorship and ownership, which he has rightly earned.
Nobody talks of any other kind of media this way, we shouldn't do it about games either. When speaking of Harry Potter, no one thinks of JK Rowling as just "the current IP holder" (she's the author!), and no one considers fan fiction on the same level as the real thing.
The article states "when the game plays, the tetrominos are selected at random". When it comes to standard Tetris, as defined by the Tetris Company, this is incorrect. I was correcting the error. Obviously you can do it however you want, but that is how Tetris does it.
As for what's more fun, obviously opinions can differ. But as someone who plays a lot (A LOT) of Tetris, I personally vastly prefer the 7-bag system. It really opens up the game strategically, and it allows you to play much faster.
I agree that credit is due to the wonderfully creative game designer, Mr. Pajitnov. I don't see this as contradictory to my point.
> So no, it's not an "abstract game with endless possibilities". Tetris is Tetris, a concrete game
While protecting their IP in a court of law, The Tetris Company successfully argued that it does not exhibit scènes à faire because it is a purely abstract game.
> Moreover, Xio does not dispute that Tetris is a purely fanciful game, meaning it has no
grounding in the real world, unlike a video game simulating a karate match or a golf
game. Therefore, the analyses in Data East and Incredible Technologies are largely
inapplicable; the scènes à faire doctrine has little weight in instances such as this
because there are no expressive elements “standard, stock, or common” to a unique puzzle game that is divorced from any real world representation.
Re:Predictably Random
by FabHK on Tuesday August 13, 2019 @10:24AM
(#20686103)
Arguably, you're not playing (or implementing) modern Tetris then, but some variation.
> Modern versions of Tetris released after 2001 use a bag-style randomizer that guarantees players will never receive more than four S or Z pieces in a row. This is one of the "Indispensable Rules" enforced by the Tetris Guideline that all officially licensed Tetris games must follow.[9]
Re:Predictably Random
by remysharp on Tuesday August 13, 2019 @04:22PM
(#20689829)
Hey there \o. original author of said hubba article :)
Just wanted to offer some missing bits you might find interesting, specifically, the third function you don't recognise is the random function from the original Tetris on the NES. It comes from the article[0] that went through all the asm of the NES Tetris cartridge.
And yup, that first one is quite quite terrible for random - it came from some of the first results in StackOverflow intentionally looking for something that was overly simple and "bad" at random.
But really the article was about testing and visualising how your own random functions might be.
Re:Predictably Random
by soVeryTired on Tuesday August 13, 2019 @09:30AM
(#20685608)
RNGs are like crypto: don't roll your own! There's some really deep number theory behind many of them. Every RNG I've seen lets you control the seed, so I'm not sure what he gains by writing his own.
Re:Predictably Random
by FabHK on Tuesday August 13, 2019 @10:36AM
(#20686225)
The article is amateurish, and it neither reflects the range and complexity of issues surrounding PRNGs, nor does it offer any good advice (except maybe "don't just use the first PRNG you come across").
A better introduction is the PCG website (it's biased towards PCG, but a) that's not a bad choice for many use cases, and b) it raises and discusses many issues regarding PRNG choice).
Re:Predictably Random
by strenholme on Tuesday August 13, 2019 @09:40AM
(#20685696)
Which random number generator to use can be a heated discussion, with strong opinions. math.random() and rand() can have issues using poor random number generators like LCGs instead of good random number generators.
The default “good” random number generator is the “Mersenne Twister” (most of the time, the 32-bit MT19937 version). It generates numbers which look quite random while not being cryptographically strong (the problem with crypto-strong generators is that they tend to be slower, and can still cause legal issues in some jurisdictions). A lot of languages use this for the default random number generator.
Some people really like using xorshift generators; with the right parameters, xorshift can generate high quality numbers while being much simpler than MT19937. One version of this which some use is JKISS32; it’s small and makes good numbers.
Random number generators can be tested using a series of tests called “dieharder”; another test for RNGs is “bigcrush” which takes hours, sometimes days, to fully run. These tests make sure the random number generators are statistically random, using a large number of tests of the generator.
My favorite pseudo random number generator is a cryptographically strong one: RadioGatún[32]. It’s simple, fast, doesn’t require special seeding of its state (unlike MT19937), and allows the seed to be an arbitrary string instead of just being a number. It passes all dieharder tests, but I haven’t had a chance to test it with bigcrush yet. I have a GitHub repo with implementations of it I have done in various languages (C, Python2, Python3, Javascript, C++, etc.)
Re:Predictably Random
by edflsafoiewq on Tuesday August 13, 2019 @09:56AM
(#20685844)
I would not recommend MT. It fails many tests, that state is big, the code is complex, and it's not very fast. For non-crypto PRNGs, I'd reach for PCG or one of Vigna's generators.
Re:Predictably Random
by strenholme on Tuesday August 13, 2019 @10:11AM
(#20685984)
I tend to agree, but I need to point out that MT19937 doesn’t fail “many” tests. It fails, at most, two of the bigcrush tests: https://en.wikipedia.org/wiki/Talk:Mersenne_Twister and look for the “TestU01” discussion on that page.
The biggest problem with MT19937, besides its complexity and large state size, is that it needs to have its state properly seeded.
Like I said, it’s a heated debate which random number generator is the best one.
Re:Predictably Random
by edflsafoiewq on Tuesday August 13, 2019 @11:06AM
(#20686536)
You're right, I shouldn't have said many. But there are RNGs which are faster, smaller, and simpler and fail fewer tests, so I don't know why MT would ever be used. It could win in period I guess, if anyone could ever use that large a period.
It is a heated debate, but it should be easier to agree that some RNG is not the best one than to agree it is.
Re:Predictably Random
by FabHK on Tuesday August 13, 2019 @10:40AM
(#20686269)
It is surprisingly heated debate, and it's hard to extract good advice from experts (I've asked Art Owen, Monte Carlo expert at Stanford, for up-to-date advice (he recommended MT19937 some 15 years ago), and he was very hesitant to utter any strong recommendations...)
Having said that, I think most projects should move on from MT19937 by now, defaulting to a cryptographically secure PRNG, and allowing to switch to a faster one (such as PCG or xoroshiro) when desired.
Re:Predictably Random
by strenholme on Tuesday August 13, 2019 @10:54AM
(#20686413)
MT19937 is probably not the best PRNG out there, but the nice thing about it is that, for a long time, there was a pretty strong consensus among programmers that it was the PRNG to use. It’s a better choice than a simple LCG, which is what programmers tend to use if they’re not using MT.
There are a lot of crypto-strong RNGs out there (AES on OFB mode? Counter Mode? SHA-3 in SHAKE128 or SHAKE256? Salsa20 or ChaCha? Or, do what I do and use RadioGatún[32]), so not much standardization on that front.
With non crypto, we have in this thread already mentioned PCG ( http://www.pcg-random.org/ ), JKISS32, xoroshiro, and Vigna’s generators. There are others. Again, not much standardization.
Re:Predictably Random
by FabHK on Tuesday August 13, 2019 @11:32AM
(#20686792)
I thought the xoroshiros are basically Vigna's? Developed further from precursors.
But you're right, there's no successor anointed yet to MT19937, but it's about time. Wish some real expert in the field would publish an authoritative account (but opinionated enough to make real choices) that programming language devs could point to, and across the board implement:
* safe (ie, a cryptographically secure PRNG) <- default
* fast (if your application needs speed more than security against adversaries, such as Monte Carlo integration)
* others (if you really know what you're doing)
EDIT to add: it feels a bit like the old chestnut about IBM: nobody ever gets fired for choosing the Mersenne Twister...
The random number generator here is used quite often in projects and it looks pretty random. But if you look at the code you can see that it has four numbers that store state and its output can be entirely predicted from those four numbers that are consecutive outputs of the RNG.
Re:Predictably Random
by perspective1 on Tuesday August 13, 2019 @09:42AM
(#20685723)
Oh wow. At some point I've thrown up my hands and just used Pcg64 because people I trust but can't possibly verify recommended it. Your post reaffirms that that was the right decision (trusting others).
Re:Predictably Random
by willis936 on Tuesday August 13, 2019 @09:37AM
(#20685662)
Why not use RDRAND?
Also you can always choose well-established, arbitrarily complex psuedo random algorithms. If you want to guarantee low correlation you could use PRBS (whatever shift amount you need, 31 may be enough for most scenarios) with the same shift register values and seeds that are maximally equidistant.
Re:Predictably Random
by lvh on Tuesday August 13, 2019 @09:47AM
(#20685763)
Article mentions he wants to make the seed explicit so he can reproduce the same (randomly selected) environment.
You can use any stream cipher you want instead, of course, but in my experience for video games the problem isn’t “I need a random bit” (which AES CTR is very good at but MT or any PCG/LCG is really just as fit for purpose) but “I need to sample from this weird distribution”. Stuff goes wrong as soon as someone needs to do something as simple as sampling from a set of cardinality not exactly a power of two let alone something more complex.
Re:Predictably Random
by grayed-down on Tuesday August 13, 2019 @12:13PM
(#20687203)
Test and debate all you want, but if your application needs random data and it has access or intermittent access to the internet, use the Cesium isotope 137 :)
Re:Predictably Random
by woliveirajr on Tuesday August 13, 2019 @08:27AM
(#20685098)
TL;DR: random is hard because computers are deterministic; we use Pseudo-Random, and each function that generates pseudo-random must be tested to see how random the results are.
Of course randomA is terrible, you're modding it with 16! It's never going to have a period longer than 16 like that! Same with randomB, just with a slightly larger number. Both of these are just bog-standard linear congruential generators. LCGs are pretty bad for anything "serious", but for picking Tetris pieces they're fine, and they're easy to implent (or at least I thought they were, but then you see an article like this where one of them has period 16...). I don't immediately recognie randomC(), but it also looks terrible. Just shifting some bits around and adding a counter. At least it has some internal state so it it's not stupidly periodic.
I haven't read up on what's the issue with V8's Math.random(), but I would have to imagine it's superior to all these three. I'm also sure there's plenty of excellent randomness libraries (and plenty of terrible ones) on NPM.
Also, this kind of visual inspection will weed out truly garbage PRNGs, but it's not a good test in general. Testing for pseudo-randomness is hard, and best left to people who know what they are doing.
Also also: for Tetris, you shouldn't just pick pieces at random, that's not how Tetris works nowadays. Tetris works by putting all 7 pieces in a bag, and then pulling them out at random. When the bag is empty, you fill it again with the seven pieces and start over. More info here: [0]. If you're new to programming, implementing the 7-bag system properly is a good little challenge, you'll get to learn all about the Fisher-Yates shuffle [1].
[0]: https://tetris.fandom.com/wiki/Random_Generator
[1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
For what it's worth, LFSRs can be nice for generating random sequences with periods of predictable length - and they're cheap! They also recently got a bit of a publicity bump with the rediscovery of how Doom used one for the "death fade" transition, that randomly but exhaustively overpainted all screen pixels with blood red. [2]
[0] https://en.m.wikipedia.org/wiki/Linear-feedback_shift_regist...
[1] http://fabiensanglard.net/fizzlefade/index.php
But in general - yeah, there's a lot to consider with picking RNGs, not the least of which being context. For games Xorshift is often a good enough choice because it's fast, small, and the game environment is chaotic already (because of the unpredictable players) so there is rarely need for something much stronger.
By the way, Doom's random number generator for the game mechanics... not so fantastic [0] :)
[0] https://github.com/id-Software/DOOM/blob/master/linuxdoom-1....
It's a purely abstract game with endless possibilities for how it can be made. That's what makes it timeless. There's no reason you have to use bag randomizer in your own personal projects. That is, unless you feel some strange need to check off boxes to comply with what the current IP holders happen to prescribe at a particular moment in time.
In fact, there's an argument for using a memoryless randomizer: it maximizes variation, unpredictability, and increases challenge.
So no, it's not an "abstract game with endless possibilities". Tetris is Tetris, a concrete game made by a great game designer. It gets cloned and copied constantly, so much so that people forget that it was actually authored by a person. Comments like yours erase Pajitnov's authorship and ownership, which he has rightly earned.
Nobody talks of any other kind of media this way, we shouldn't do it about games either. When speaking of Harry Potter, no one thinks of JK Rowling as just "the current IP holder" (she's the author!), and no one considers fan fiction on the same level as the real thing.
The article states "when the game plays, the tetrominos are selected at random". When it comes to standard Tetris, as defined by the Tetris Company, this is incorrect. I was correcting the error. Obviously you can do it however you want, but that is how Tetris does it.
As for what's more fun, obviously opinions can differ. But as someone who plays a lot (A LOT) of Tetris, I personally vastly prefer the 7-bag system. It really opens up the game strategically, and it allows you to play much faster.
> So no, it's not an "abstract game with endless possibilities". Tetris is Tetris, a concrete game
While protecting their IP in a court of law, The Tetris Company successfully argued that it does not exhibit scènes à faire because it is a purely abstract game.
> Moreover, Xio does not dispute that Tetris is a purely fanciful game, meaning it has no grounding in the real world, unlike a video game simulating a karate match or a golf game. Therefore, the analyses in Data East and Incredible Technologies are largely inapplicable; the scènes à faire doctrine has little weight in instances such as this because there are no expressive elements “standard, stock, or common” to a unique puzzle game that is divorced from any real world representation.
> https://law.justia.com/cases/federal/district-courts/new-jer...
> Modern versions of Tetris released after 2001 use a bag-style randomizer that guarantees players will never receive more than four S or Z pieces in a row. This is one of the "Indispensable Rules" enforced by the Tetris Guideline that all officially licensed Tetris games must follow.[9]
https://en.wikipedia.org/wiki/Tetris#Infinite_gameplay_impos...
Just wanted to offer some missing bits you might find interesting, specifically, the third function you don't recognise is the random function from the original Tetris on the NES. It comes from the article[0] that went through all the asm of the NES Tetris cartridge.
And yup, that first one is quite quite terrible for random - it came from some of the first results in StackOverflow intentionally looking for something that was overly simple and "bad" at random.
But really the article was about testing and visualising how your own random functions might be.
[0]: https://meatfighter.com/nintendotetrisai/#Picking_Tetriminos
A better introduction is the PCG website (it's biased towards PCG, but a) that's not a bad choice for many use cases, and b) it raises and discusses many issues regarding PRNG choice).
http://www.pcg-random.org
EDIT to add: and FWIW, any serious PRNG of course allows seeding, and then the issue boils down to choosing a shared seed.
The default “good” random number generator is the “Mersenne Twister” (most of the time, the 32-bit MT19937 version). It generates numbers which look quite random while not being cryptographically strong (the problem with crypto-strong generators is that they tend to be slower, and can still cause legal issues in some jurisdictions). A lot of languages use this for the default random number generator.
Some people really like using xorshift generators; with the right parameters, xorshift can generate high quality numbers while being much simpler than MT19937. One version of this which some use is JKISS32; it’s small and makes good numbers.
Random number generators can be tested using a series of tests called “dieharder”; another test for RNGs is “bigcrush” which takes hours, sometimes days, to fully run. These tests make sure the random number generators are statistically random, using a large number of tests of the generator.
My favorite pseudo random number generator is a cryptographically strong one: RadioGatún[32]. It’s simple, fast, doesn’t require special seeding of its state (unlike MT19937), and allows the seed to be an arbitrary string instead of just being a number. It passes all dieharder tests, but I haven’t had a chance to test it with bigcrush yet. I have a GitHub repo with implementations of it I have done in various languages (C, Python2, Python3, Javascript, C++, etc.)
The biggest problem with MT19937, besides its complexity and large state size, is that it needs to have its state properly seeded.
Like I said, it’s a heated debate which random number generator is the best one.
It is a heated debate, but it should be easier to agree that some RNG is not the best one than to agree it is.
Having said that, I think most projects should move on from MT19937 by now, defaulting to a cryptographically secure PRNG, and allowing to switch to a faster one (such as PCG or xoroshiro) when desired.
There are a lot of crypto-strong RNGs out there (AES on OFB mode? Counter Mode? SHA-3 in SHAKE128 or SHAKE256? Salsa20 or ChaCha? Or, do what I do and use RadioGatún[32]), so not much standardization on that front.
With non crypto, we have in this thread already mentioned PCG ( http://www.pcg-random.org/ ), JKISS32, xoroshiro, and Vigna’s generators. There are others. Again, not much standardization.
But you're right, there's no successor anointed yet to MT19937, but it's about time. Wish some real expert in the field would publish an authoritative account (but opinionated enough to make real choices) that programming language devs could point to, and across the board implement:
* safe (ie, a cryptographically secure PRNG) <- default
* fast (if your application needs speed more than security against adversaries, such as Monte Carlo integration)
* others (if you really know what you're doing)
EDIT to add: it feels a bit like the old chestnut about IBM: nobody ever gets fired for choosing the Mersenne Twister...
I created a 'Random' service that lives for the length of the execution of the application.
This service has an instance of Random that persists with the object, and exposes simple methods with min/max parameters.
I register the service in a unity container, and then immediately resolve it, causing the Random type inside of the random service to instantiate.
Then anywhere I want to generate a random number, I inject that service.
This works because, as long as you persist a single instance of 'Random', two calls to 'Next' or 'NextDouble' won't result in the same number.
edit: It shows small-periods but otherwise it's not all that useful (see below).
The random number generator here is used quite often in projects and it looks pretty random. But if you look at the code you can see that it has four numbers that store state and its output can be entirely predicted from those four numbers that are consecutive outputs of the RNG.
Also you can always choose well-established, arbitrarily complex psuedo random algorithms. If you want to guarantee low correlation you could use PRBS (whatever shift amount you need, 31 may be enough for most scenarios) with the same shift register values and seeds that are maximally equidistant.
You can use any stream cipher you want instead, of course, but in my experience for video games the problem isn’t “I need a random bit” (which AES CTR is very good at but MT or any PCG/LCG is really just as fit for purpose) but “I need to sample from this weird distribution”. Stuff goes wrong as soon as someone needs to do something as simple as sampling from a set of cardinality not exactly a power of two let alone something more complex.
https://www.fourmilab.ch/hotbits/