Tuesday, February 21, 2017

A mathematician will tell you that computer cannot produce "real" random numbers, from a purely mathematical point of view. However algorithms exist that produce numbers that are so close to perfectly random that they are perfectly viable for even such demanding applications as cryptography. For games such random number generators are more than perfectly adequate.

The second big problem with random numbers is that human brains are so wired for pattern recognition that we see patterns even if there ain't any. A perfectly random sequence of heads and tails coin flips has more long sequences of one side coming up repeatedly than most people would expect. Studies have been performed where test persons were asked to identify sequences as random or not random, and it turned out that people are notoriously bad at that.

In the particular case of Magic the Gathering, an added factor is that some people have experience with physical cards. And most methods of shuffling do not produce a perfectly random sequence. Many people for example take all their lands and "riffle shuffle" them into the other cards. Even some subsequent regular shuffling will not produce a perfectly random sequence, but rather a higher dispersion of land cards in the deck than true randomness. As this is what players want, this is actually a minor form of cheating, but as there are few mathematicians in MtG tournaments, nobody complains.

Having said all that, one could expect that a computer game like Magic Duels has a reasonable random number generator, and that people complaining on forums about bad draws are just sore losers with a limited grasp of mathematics. However after playing thousands of games I am pretty much convinced that the random number generator in Magic Duels is garbage, and produces a statistically significant deviation from randomness, leading to noticeable "lumping" of cards.

A typical Magic deck has about 40% lands, 24 out of 60 cards. Randomness means that it is perfectly possible to draw a hand of 7 cards and find anything between 0 and 7 lands. However the quality of a good random number generator would result in the statistical probability of you drawing 3 lands being the highest, having 2 or 4 lands being less likely, having 1 or 5 lands being even less likely, 0 or 6 lands being very rare, and getting 7 lands being extremely rare.

If you compare that to the actual draws of Magic Duels, you'll quickly notice that less likely outcomes like 1 or 5 lands appear far more frequently than statistics would suggest. Even weirder, mathematics tells you that the statistical probability of drawing another land after your starting hand only depends on the number of remaining lands and cards. So if you have already 5 out of 7 cards being lands in your starting hand, the probability of drawing another land as your next draw is 19/53 or 36%. Curiously in Magic Duels that probability is somehow inverted, and if you drew 5 lands in your starting hand you are more likely than not to draw a 6th land as your next draw.

The particular "lumping" of cards in Magic Duels is also sometimes very visible in other cards than lands. While a Magic deck has usually 60 cards, unless you or your opponent have build their deck around special "milling" or card drawing engines, you probably will only see something like 20 out of the 60 cards in your deck. People put up to 4 copies of the same card in their deck precisely to assure that they have a good chance to see a specific card in that first third of the deck. Finding that card twice is a distinct probability, 3 times should be rare, and 4 times exotic. However in Magic Duels you see the same card 3 or 4 times early in the game far more often than statistically probable.

While I do think the Magic Duels would need a better random number generator, it is doubtful that we'll ever get one. The lumping of cards doesn't make the game unplayable. Especially not against the AI, where you can quickly quit and restart a game where the random number generator swamped you with lands. As a general rule I quit every game in which 7+ out of the first 10 cards are lands. Which statistically shouldn't happen all that often, but in reality it does. Hasbro just announced a new digital version of Magic the Gathering called Magic Digital Next, so hopefully the random number generator of that one is better. However Magic Duels is very player-friendly in limiting the number or legendary and rare cards you can have, making it far easier to achieve a full collection. Unless Magic Digital Next has the same mechanic, I would be loath to switch to a new game and lose all my existing card collection in favor of a game where each expansion would cost much more money.

As you correctly say, humans suck big time in detecting randomness.... so I wonder if you draw your conclusions from a table you filled while playing or you're going by memory. In this second case, you risk being off as well.

As for RNG.... well, games are known to be bad, in the sense that unless the programmers are aware of the problem, they probably stick to the simplest solution and not go for a full Mersenne twister.

Both, actually. I first developed a feeling that something was off from playing, then made a table with the number of lands in 100 starting hands. The combination of both convinced me that there was a real problem, even if somebody more thorough would maybe have tested more starting hands. Feel free to do that. :)

Can you post the breakdown of the 100 starting hands you recorded?

Did any of the 100 have 7 lands?

No, but 5 lands were over twice as frequent as statistically predicted. Now, where did I put that piece of paper?

Obviously the cards are not distributed at random but sorted into order then mixed using a shuffle-simulator to represent ripple-shuffles and deck manipulation. It isn't poor RNG it is a feature to simulate real world card mixing!
If you were Gevlon you would have put it down to match fixing because you haven't spent enough at the cash store, rather than just putting it down to a bias towards pattern recognition.
You should be see one land on a starting draw (with 24 land cards) about once every 8 deals and 5 land around once per 14 deals. The likelihood of you seeing five lands at twice the statistical prediction over 100 decks (14 times) is approximately 1%, well below the probability required to convince a particle physicist!

Nowadays scientists - including particle physicists, though they would probably have been more aware of the issue than others - are realising that many supposedly 'statistically significant' results are spurious. The big issue is that if you test exactly one thing exactly once, there's only 1% chance that a 1% probability result will show up. But we hardly ever do that. For example, Tobold also looked for decks with other numbers of land, eight possibilities in all. And he would probably have noticed other oddities, meaning he is implicitly testing for those.

So while I wouldn't rule out the possibility that decks are not well-randomised, a 1% result for 5 lands is far from strong evidence.

I hope you realise that real numbers not equal to mathematical expectations is not itself a sign of non-randomness, and you need repetitive experiments to prove non-randomness, where the sufficient number of experiments is a function of a number of outcomes (in your case, the number of outcomes is 8 if you record the number of lands in the starting hand and whole 11 if you record the number of lands in first 10 cards drawn).

@Gary Quinn,
Sorry. I worded that badly. I meant that the probability of the rare event not occurring was too low for it to be proof that RNG was bad, not that the probability of said event was low enough to dismiss the possibility of it being a chance occurrence.

Just to make sure I'm remembering my statistics right:

- chance of 5 lands in a draw of 7 cards from a 60-card deck with 24 lands, p = hypergeometric distribution with n=7 k=5 N=60 K=24 = 0.069335 (i.e. 1/14.4, which matches the 1 in 14 tries)

- with p=7%, the statistical average should be 7 in 100 draws, if you see the double (=14) the probability of this happening is binomial(100,14)*p^14*(1-p)^(100-14) = 0.0054308, a bit less than the 1% mentioned

Am I doing this right or I messed up?

@Helistar
Same numbers as me, although my quoted 1% was from the probability of 14 or more draws of 5 land cards in 100 deals (0.009175).