About deck shuffling(please read before applying criticism)

[Br0kenSkies]

So, I've been using Xmage for just over a year now, and I've asked around over the past year and I know for a fact that I'm not alone on this:
The RNG/Deck Hashing system, the way the program shuffles the decks, is skewed. I don't notice it much when I play EDH because it's a singleton format, but on any other format in 1v1 games it's VERY noticeable. 100% RNG isn't fully representative of actual deck shuffling, therefore if you have no IRL playgroup nor the money to freely buy cards(like me, it's why I use this thing so much), it becomes frustratingly difficult to properly playtest a deck before you decide to buy the cards. From the people I've talked to on the servers about this, I've heard everything from it being a minor inconvenience to them to people noticing that their paper decks literally become unable to get off the ground on Xmage. Example, I have a Standard deck, Servo Tribal, aggro, fast, very low curve and 22 land, it should run just fine in paper, but on Xmage? I either get way too many land or too few, and rarely do I get a reasonable amount of land in my opening hands.

If you've read all this, thanks, and I hope the devs can do something about this.

[escplan9]

There's nothing to be done. This discussion has come up before with people blaming the shuffler (not just with XMage, but with MTGO, and any other online game with RNG shuffling). It makes no logical sense. The claim would be that the randomization in the code is forcing certain scenarios:

1) Too many lands throughout a game
2) Too few lands throughout a game
3) Too many lands in the opening 7
4) Too few lands in the opening 7
5) Your opponents are not getting mana screwed or flooded though.

So you would be claiming the code is giving many or too few lands to you, but not your opponent. You can't have all those be true and say there's a problem with the shuffler.

If you want the actual evidence, the randomization is extremely simple and the code is open-source, so you can see for yourself:

https://github.com/magefree/mage/blob/1 ... brary.java

With this being the main section to look at:

Code: Select all

public void shuffle() {
        UUID[] shuffled = library.toArray(new UUID[0]);
        for (int n = shuffled.length - 1; n > 0; n--) {
            int r = RandomUtil.nextInt(n);
            UUID temp = shuffled[n];
            shuffled[n] = shuffled[r];
            shuffled[r] = temp;
        }
        library.clear();
        library.addAll(Arrays.asList(shuffled));
}

If you can argue that code above is flawed to produce the mana flood / mana screw scenarios, then we have something to discuss. It wouldn't even be enough to claim the java RandomUtil library does not produce adequate randomization since you are claiming something very specific - that there is logic in the code which is making it so you are more likely to be mana flooded and screwed each game. From the code above, there is no such logic regarding lands or non-lands whatsoever.

The real explanation for what you're seeing and claiming is a mixture of a few things:
1) Confirmation Bias - you remember the times where you were mana flooded or mana screwed and forget all the times you weren't.
2) Playing online means you do not have control over shuffling your deck, which leads people to want to blame something other than random chance that they have sequences where they are mana flooded or mana screwed.
3) Playing online also means the games go by quicker since you no longer have to take the time to be shuffling your cards, it is done instantaneously. This has many other related effects - with the games going by quicker, and you playing more games, you see a lot more opening hands per hour than in typical paper magic.
4) Along with the above - by random chance alone you will sometimes have games where you are mana screwed or flooded. Even multiple times in a row. And again, from playing so many more hands per hour you are likely to see this mathematically improbable situation occur more often.

See this for another discussion on the issue:
https://www.reddit.com/r/XMage/comments ... your_deck/

[Arcanist]

I hope it is OK for me to post here. I don't play XMage, but I was browsing the forum out of curiosity, and I thought I would contribute my 2 cents.

With this being the main section to look at:

Code: Select all

public void shuffle() {
        UUID[] shuffled = library.toArray(new UUID[0]);
        for (int n = shuffled.length - 1; n > 0; n--) {
            int r = RandomUtil.nextInt(n);
            UUID temp = shuffled[n];
            shuffled[n] = shuffled[r];
            shuffled[r] = temp;
        }
        library.clear();
        library.addAll(Arrays.asList(shuffled));
}

If you can argue that code above is flawed to produce the mana flood / mana screw scenarios, then we have something to discuss.

I am not the OP, but I can make that argument. This code is definitely flawed. Whoever copied the Fisher-Yates algorithm made a crucial mistake: r should be set to RandomUtil.nextInt(n+1) instead of RandomUtil.nextInt(n). I could give you a mathematical explanation, but here is a simpler way to prove that this code is incorrect:

• The section of the Wikipedia article describing the modern implementation of the Fisher-Yates algorithm clearly states that r should be set to a random integer j such that 0 <= j <= i (with i = n in your case);
  
• The Javadoc for Random.nextInt() -- RandomUtil.nextInt() simply forwards the call to this function -- shows that it returns a random number between 0 (inclusive) and n (exclusive). So right now, your algorithm sets r to a random integer j such that 0 <= j <= n - 1.

This may not seem like a big deal, but it is! It means that the current implementation is unable to generate all the possible deck permutations, and thus it is biased. But that is not the only issue...

It wouldn't even be enough to claim the java RandomUtil library does not produce adequate randomization since you are claiming something very specific - that there is logic in the code which is making it so you are more likely to be mana flooded and screwed each game.

I think you vastly underestimate the amount of randomness required to shuffle a deck. The Random class simply does not produce enough of it for a correct shuffle. If you read the Javadoc for the Random class, you will find out that it uses a 48-bit seed. Can you guess how many cards you can correctly shuffle with that?

| Open

16 cards! Only 16!

If you try to shuffle a deck larger than this, there are deck permutations you will never be able to generate. Given the sizes involved, I would not be surprised if this issue turned out to be the main source of bias.

To properly shuffle a deck of cards for a game like Magic, you need to use a cryptographically strong RNG. In Java, this means replacing the Random class with SecureRandom. A 35-byte seed should be enough to properly shuffle a deck for both limited and constructed play.

[Aurum]

Thanks for your in depth explanation, we will look into this.

Issue 1428, created december 2015, covers this as well.
https://github.com/magefree/mage/issues/1428

[Arcanist]

Thanks for your in depth explanation, we will look into this.

Issue 1428, created december 2015, covers this as well.
https://github.com/magefree/mage/issues/1428

No problem. Happy to help. Fixing the Fisher-Yates shuffle should be easy. It is a simple one line change.

Thanks for the link to the issue. It looks like the concerns were more focused on possible cheating due to the small state space associated with a 48-bit seed. My point is that this is not the only issue: There are simply some shuffles that XMage will never be able to generate. The main concern raised in the issue is the fact that SecureRandom can take a while to initialize if the entropy pool is exhausted.

That is true but there are various techniques to solve that:

• You could have a separate program read from an entropy source (e.g. /dev/random), and write the result to disk. The XMage server could then generate a random seed by reading from that file. This would guarantee that the server never blocks when trying to initialize SecureRandom. Among other advantages, you could run tests on that data to make sure its randomness is acceptable. You could also reuse those files multiple times if you have enough of them;
• Another solution is to ask clients to read from their entropy source and send the data to the server. You would have to run checks to make sure that the data is random enough, and probably mix multiple sources together to prevent poisoning, but this would work as well. The advantage of this approach is that it scales with the number of players just like the need for randomness.

I could go on, but I will stop there.

[Hintelijente]

Somewhat related...
The randomization of the packs is not the same than in mtgo or real life, is this possible to fix?

[escplan9]

I think the issue with the packs is we don't have all the possible prints available (forget the term, but it's something more specific than X rares, commons, uncommons, etc). MTGO is by Wizards and of course the paper version is as well so they have access to that information.