PDA

View Full Version : Randomization



Shaqattaq
03-28-2014, 10:07 AM
by Alan Comer

Hi! My name is Alan Comer, and I am here today to talk about randomness . I have worked on many TCGs over the last 10+ years — Magic Online, Kaijudo, and Pokémon are the biggest. Every time, randomness becomes a hot topic of discussion. It happens inside the companies, as well as on the forums. I have been called on many times to explain what really happens, and why. I would like to start with the basics so that everybody is on the same footing.

http://hextcg.com/randomization/

Commoble
03-28-2014, 10:30 AM
Great, informative article! The world would be a better place if more people understood randomness and statistics.

mudkip
03-28-2014, 11:01 AM
I have run 1,000,000 numbers
http://blogs.discovermagazine.com/sciencenotfiction/files/2010/11/dr-evil.jpg

funktion
03-28-2014, 11:14 AM
Great Article


We try to get as close to true random as possible because getting 100% of the way there is extremely painful.

There was just something with that sentence that had me giggling a bit. It's a follow up to Zeno's paradox, the real reason you can never reach the finish line is that it would be extremely painful... kinda like... certain unmentionables...

Nekosluagh
03-28-2014, 11:37 AM
Hopefully, this article finally brings an end to all the posts about the randomness of the shuffling. Still doesn't do anything about posts about having a mulligan, but it's better than nothing.

Yoss
03-28-2014, 11:38 AM
Excellent article, thanks!

Kami
03-28-2014, 11:56 AM
That was one of the most interesting articles I've read thus far from you guys. :)

I love the behind the scenes developer mindset commentary.

darkwonders
03-28-2014, 12:31 PM
Hopefully, this article finally brings an end to all the posts about the randomness of the shuffling. Still doesn't do anything about posts about having a mulligan, but it's better than nothing.

But if it does, then they'll think something is wrong with the PRNG!

seashell
03-28-2014, 12:33 PM
Awesome article! Very interesting.

dwebber88
03-28-2014, 12:36 PM
I hope you realize there is hardware out there that generates True random numbers (TRNG). Why not use that hardware? Why go for the substitute software PRNG?

Yoss
03-28-2014, 12:53 PM
I hope you realize there is hardware out there that generates True random numbers (TRNG). Why not use that hardware? Why go for the substitute software PRNG?

Perhaps it's a cost issue?

Showsni
03-28-2014, 01:15 PM
I wonder what efforts are made to obfuscate (if that's the right word) the PRNG and seeding methods.

I play a fair amount of Pokémon, having competed at the international level, and it's well known in the community that the PRNG is a Mersenne Twister seeded by the time and date the game is switched on and advanced by several known steps in game. The net result is that people have created programmes which will tell you exactly what steps to take to catch/breed exactly the Pokémon you want. Stuff like "To breed a perfect Torchic, set your game to this time and date, wait exactly this long between resetting the game and pushing continue, and listen to your Chatots chattering exactly this number of times, then pick up the egg." With programmes like that obtaining flawless Pokémon is fairly easy, and thus it becomes a necessity to have them in the competitive scene (because everyone else will have). Luckily you can't really do the same thing with the Battle RNG, because your opponents would see you and report it.

I'd imagine if a user knew enough about how the Hex PRNG worked they might be able to deduce things like where in the deck a shuffled in card would end up, if they knew the seed and advances. But I suppose that this will all be worked out server side, so it's probably fine.

dwebber88
03-28-2014, 05:57 PM
Doesn't really matter if its serverside or not. if it gets predictable at some point, its broken. TRNG can't be broken if used properly.

Edit: I'd like to hear from the CZE staff why they didn't choose for TRNG, and if they are still planning on using some of the available hardware for it.

Xenavire
03-29-2014, 05:49 AM
Doesn't really matter if its serverside or not. if it gets predictable at some point, its broken. TRNG can't be broken if used properly.

Edit: I'd like to hear from the CZE staff why they didn't choose for TRNG, and if they are still planning on using some of the available hardware for it.

I think Alan mentioned that right in the article - the speed at which the numbers get reported back. Correct me if I am wrong, but TRNG would take longer to generate numbers, right? I can't imagine they would have ignored TRNG completely if this wasn't the case.

The other reason they may want PRNG is because of boosters - they want to similuate real life printing runs, but that might be possible with PRNG. If so, then it would be their best option, and TRNG would be a horrible replacement.

Those are my ideas off the top of my head. And I think if they are doing the seeding serverside, it should be more or less impossible to manipulate (latency, client lag, etc).

AlanComer
03-30-2014, 10:43 AM
TRNGs are interesting. Once upon a time, they would have been prohibitive from both a cost, and a throughput perspective. (They didn't generate them fast enough.) Modern TRNGs do not have this problem. They do still have a different ugly side effect: When they fail, how do you know?

The reality though, is it boils down to 2 needs. The 1st: How many times do you riffle shuffle your deck. There is research out there for 52 card decks that most people take to say 7 times is correct. (I doesn't actually report that, it say that total variation distance is 0.334, I leave it up to the reader to do further research if that interests them). As a human, you can keep shuffling more times, and that variance will go down. It never really goes to 0. Do you worry about this, or do you just call it good enough at some point? The same is true for us. At some point, we need to say something is good enough, because you can never really get perfect. We are significantly better than humans doing 7 riffle shuffle.

The 2nd need, is that I can never recreate what happened with a TRNG. With a PRNG, I can keep the seed and the input stream, and run the game through the stored inputs. This will create an exact recreation server side of what the rules engine did. (Yes, our code is 100% deterministic). This means, when the game crashes, I can see it happen, which makes debugging WAY easier.

darkwonders
03-30-2014, 08:00 PM
The 2nd need, is that I can never recreate what happened with a TRNG. With a PRNG, I can keep the seed and the input stream, and run the game through the stored inputs. This will create an exact recreation server side of what the rules engine did. (Yes, our code is 100% deterministic). This means, when the game crashes, I can see it happen, which makes debugging WAY easier.

So you're taking the easy way out, eh? :p

mach
03-30-2014, 08:03 PM
The 2nd need, is that I can never recreate what happened with a TRNG. With a PRNG, I can keep the seed and the input stream, and run the game through the stored inputs. This will create an exact recreation server side of what the rules engine did. (Yes, our code is 100% deterministic). This means, when the game crashes, I can see it happen, which makes debugging WAY easier.

That's not true. You can log everything generated by the TRNG and then feed that data back in to recreate what happened.

Kroan
03-31-2014, 04:05 AM
Doesn't really matter if its serverside or not. if it gets predictable at some point, its broken. TRNG can't be broken if used properly. Yes it does. If it's client side you can reproduce the steps to get a certain result and therefor you can predict the outcome of a random generator. You can't do that if this is generated on the server.

AlanComer
03-31-2014, 09:13 AM
That's not true. You can log everything generated by the TRNG and then feed that data back in to recreate what happened.

Mach is right here. The fact is, a TRNG is so far beyond overkill that I never actually think that deep about it. Logging every random number is doable, and not even that big of a deal. Everything I need is on the server

Mejis
03-31-2014, 08:17 PM
How many times do you riffle shuffle your deck. There is research out there for 52 card decks that most people take to say 7 times is correct.

I prefer to do 8 perfect out-faros...

[not sure if any fellow magic geeks lurking on these forums]

EDIT: awesome article by the way Alan. Had no idea about PRNG and TRNGs, fascinating stuff.

Dr.Blasterface
04-01-2014, 07:58 AM
I hope you realize there is hardware out there that generates True random numbers (TRNG). Why not use that hardware? Why go for the substitute software PRNG?

Because while they produce true random numbers, they produce true random numbers slowly. Most are too slow to be used as a source of random numbers for normal desktop usage. For a multi-user server implementation? Not feasible.

Most of the time, TRNG is used 1) when the volume of random number is low (e.g., cryptographic nonse or key generation) or 2) as a seed of a PRNG. 2) is good enough for applications that need much more random-like inputs (e.g., Monte Carlo simulations) than a video game.

Zomnivore
04-02-2014, 06:39 PM
Hopefully, this article finally brings an end to all the posts about the randomness of the shuffling. Still doesn't do anything about posts about having a mulligan, but it's better than nothing.

If the beta client is using the finished shuffler then maybe.

I however have noticed bunching. A lot of it.

Tinfoil
04-04-2014, 01:45 PM
Help me understand something (maybe I am committing some version of the gamblers fallacy, but please explain).

Does the RNG simulate the whole deck or just the next draw(s)?

If each draw is independent of the last draw, wouldn´t it make clusters of the same type of card more likely if the starting conditions (starting hand) is a little skewed?

Barkam
04-10-2014, 01:05 PM
Gambler's fallacy

Onky thing it needs to take into account is the cards that are no longer in the deck.

tautologico
04-17-2014, 07:50 AM
This was interesting (just read it today). I just have a few small nits to pick. The first is misuse of the word "theory". In common use, most people use "theory" when they really mean "hypothesis". A theory is not tentative and uncertain like an hypothesis, it's just the opposite: for something to be called a theory it must be backed by strong evidence or mathematical proof.

This is not a big deal in everyday conversation, but it causes problems when people use the same sense to discuss science, like "this is just a theory". Also here when you discuss statistics. While it's correct that you can't be 100% sure about conclusions reached via statistics (or any kind of inductive reasoning), the "Theory of Statistics" is something else entirely. Usually stats people call "theory of statistics" exactly the part that is quite certain about it: the mathematical underpinnings of the subject. So the name "theory of statistics" has nothing to do with uncertainty, just as "theory of numbers" has nothing uncertain in it.

About testing: did you use any of the well-known test suites for the RNG, like the DIEHARD tests by Marsaglia?

About TRNGs in the comments, it's a common misconception that people have that they somehow need "true randomness". This is rarely true, and very rarely justifies the costs. Any sequence that "looks" statistically random is good enough for most purposes. Sources of "true" randomness may not even be "truly" random, depending on your conception of randomness (which is hard to define, to begin with) and whether the universe is ultimately deterministic or not. TRNGs may have a host of other problems, including the distribution of generated numbers, bias, difficulty of reproducibility and verification etc. That's why while most people in the internet seem to think a physical source of randomness is better, most applications (>90%) use and will probably continue using software PRNGs.

Werlix
04-17-2014, 01:35 PM
Help me understand something (maybe I am committing some version of the gamblers fallacy, but please explain).

Does the RNG simulate the whole deck or just the next draw(s)?

If each draw is independent of the last draw, wouldn´t it make clusters of the same type of card more likely if the starting conditions (starting hand) is a little skewed?

It couldn't shuffle before each draw as this would break the concept of a card game. Eg when they release cards that let us peek at the top card of your deck etc.

However, both your cases are equally as "random". Neither would produce more or less "clumping" than the other.

Werlix
04-17-2014, 01:37 PM
If the beta client is using the finished shuffler then maybe.

I however have noticed bunching. A lot of it.

What is it going to take to convince you? A post from the employee at Hex in charge of this exact thing explaining the methodology, assuring you that it's ok and has been tested... isn't enough?

Yoss
06-18-2014, 06:14 PM
Out of curiosity, how many possible states does the pRNG produce? If it is (for example) 2^64 from a 64 bit computer algorithm, it might not cover the N! possible outcomes from a deck of N cards when N gets "large" (and factorials blow up very quickly).

For example, 2^64 is roughly 2E19 while 40! is roughly 8E47 and 60! is roughly 8E81.

I will freely admit that I am no expert on this subject. I am seeking understanding.

Chemosh
06-20-2014, 05:43 PM
Great article... But there's is a huge assumption made with some statements that I have heard others say before...

And this is a situation where this comes into play: in a draft I run a 40 card deck with low-mid costs and 1-2 high cost. I include 17 resources which covers the needs of the decks thresholds and costs on a decent curve. My first hand is 5 resources 1 low cost and 1 mid cost... Not the best but they are cards that can get me a big advantage as long as I draw any of the other non resource cards in the deck..(oversimplifying here).. However I know that 5/17 resources so odds should be in favor of non resource cards.... I draw resources for the next 3 a card on 4th and another resource 5th... At this point I'm overrun...OK bad hand next game...OK this time slightly better 4 resource 3 card... Next 3. Draws resources putting me well behind yet again.

Now this happening twice isn't impossible... But this happens all the time.... To the same individual...

yes if you look at it from macro perspective it may fall into your margins... But it seems odd that a individual can get the same results so often( I have seen 14 resources in top 20 cards more then I care to count.). So perhaps the micro level needs some examination rather then use a macro perspective for everything?

Quasari
06-22-2014, 05:35 PM
Out of curiosity, how many possible states does the pRNG produce? If it is (for example) 2^64 from a 64 bit computer algorithm, it might not cover the N! possible outcomes from a deck of N cards when N gets "large" (and factorials blow up very quickly).

For example, 2^64 is roughly 2E19 while 40! is roughly 8E47 and 60! is roughly 8E81.

I will freely admit that I am no expert on this subject. I am seeking understanding.

The number of states doesn't matter as we'll never have a deck larger than 2^64 cards. The only thing that matters is that each state has an equal chance of happening across a large sample. If they are using the shuffle method I think they are, the only number of states they need is equal to the size of the deck.

Yoss
06-22-2014, 09:40 PM
I was debating in my mind whether they'd only need >60 states or >60!. Reasoning being that states pulled sequentially from pRNG like in Fisher Yates are not necessarily independent. If not independent, then the number of states matters because you have to consider sequences not just single pulls. If you instead are re-seeding every pull then you have to worry about the seed itself. Does that make any sense?

Makizushi
06-22-2014, 11:16 PM
Just wanted to say thanks for sharing an interesting article/behind-the-scenes look, as well as for sparking a cool debate. I'm listening and learning :)

Glae
06-26-2014, 02:10 PM
Quick question. Does the game actually fully shuffle the deck between making changes in the deck editor and playing a constructed game?

If I use Shards of Fate or Adaptable Infusion Device after making edits, I very frequently get all shards in order. IE: 10 shards of Sapphire followed by 10 shards of Diamond. This doesn't seem like a display feature (alphabetical sort or something) as it doesn't always occur. But its frequent enough after making deck changes that I notice it. Is this just like Babe Ruth when I'm remembering hits but forgetting misses?

Yoss
06-26-2014, 03:33 PM
The UI display order means nothing; the deck order is only stored on the server side. (Gone are the days when you could use SoF and AID to spy out what shards are on the way.)

Glae
06-27-2014, 12:25 PM
Hmm. I'll have to pay closer attention then. I thought it just frequently did this, rather than 100%.

Edit: ah. It seems like SoF and AID display them differently. It isn't that its in order 50% of the time, its 100% of the time with one of them.