I always laughed at folks complaining about the shuffler on arena simply because randomizing an array is trivial to implement. It seems unlikely they screwed that up.
I believe the only thing it does is shuffle your deck twice and try to give you the better starting hand of the two.
I know of people who have written things like online casino games (in unregulated jurisdictions) where the shuffle was deliberately skewed in order to achieve certain configurable winning percentages from the games. ie it's not done by accident but design.
That said people do sometimes unintentionally write something like this (terrible and also buggy) algo
for idx in size(deck):
new_spot = int(random() * size(deck))
swap(deck[idx], deck[new_spot])
...which won't give an even distribution of all possible outcomes. If shuffling, look up a real algo (like Fisher-Yates for instance) and implement that. Or better yet, use a library implementation.
The theory I’ve always heard about why the shuffler might be biased is that they’re trying to reduce land flood/screw. Drawing too few or too many lands is a commonly cited cause of frustration with players and if you’re reasonably assuming Arena wants to do all the usual monetised-game things of increasing playtime and MAU whatnot, this conclusion seems one of the first people come to.
Yes, but a frustrated player is more likely to buy event entries, aka gems, to draft more, and blame the poor randomization on bad luck, rather than intentional screw, because that is what you do at real life events. It's an insidious dopamine loop strategy, but it absolutely works.
Right. The subtle difference being that because you only sample from position i to n you only ever exchange each card exactly once. In my algo you sample from 0 to n-1 so a card exchanged in a previous round can be exchanged again. This generalises into cards early in the shuffle being exchanged more than later cards, which changes the distribution of possible outcomes.
Nerd sidenote: Because generating random numbers tends to be expensive, I had an idea once where you generate the full permutation with only a single random sample. Basically you could use something which fully enumerates a space like Gray codes[1] (you want one with a closed form solution which can arbitrarily you the nth code) then you generate one random number, multiply by the number of combinations, look up that code and decode that into the sequence of cards. I never actually got around to implementing it, but I suspect if your code lookup was fast it would be much faster than Fisher-Yates.
The use case was if you wanted to make a Monte Carlo algorithm to evaluate strategies in a card game for instance.
I've wondered about the same thing of generating a permutation with a minimum number of samples. I'm not sure how Gray codes helps you here, and the multiplication sounds wrong since many outputs aren't reachable from any input.
The idea is just a closed form solution that gets you from a number in 1...nPermutations to a single specific permutation. I was using Gray codes as an example of a sequence that exhausts all permutations with a closed form that gets you to a specific point in the sequence.
Might not work - as I say I never actually got around to implementing it.
You’ll find that the number of ways to shuffle a card pack (52!) is about 8 × 10⁶⁷, so even if your RNG returns 64 bits, you can’t use a single call.
Also, you’ll have to make sure you pick each permutation is picked with equal probability. random() % factorial(52) likely won’t work because your RNG won’t return integers in a range k × 52! for some k > 1 (https://stackoverflow.com/questions/10984974/why-do-people-s...)
I wrote that code for fun 15-20 years ago (code definitely lost in the mists of time).
You can think of it as rolling one random number up to n!, then use x%n to pick the first element and then x/n to pick the next (n-1) elements (so the next step is then to pick the second element with (x/n)%(n-1) and use (x/n)/(n-1) for the remaining (n-2) elements).
Though as a sibling comment points out, since you need a random number up to n!, even 64 bits of randomness only get you so far (I think up to 20, but didn't check my math).
The n-2 bit is unnecessary and misleading because we've already established that an index can be swapped with itself.
for i in [0..n-1]
swap(a[i], a[rand in [i..n-1])
where rand in [I..n-1] coud be implemented as i + (rand() % (n-i))
essentially start with your finger at 0, pick a card from the unpicked set which is everything on and after your finger, swap that card with your finger, move your finger up one card
For those interested, I wrote a small article on the various was of writing incorrect Fisher-Yates [0]. The post also covers generating single cycle permutations.
Fisher-Yates is pretty obvious but weirdly subtle in some ways. For someone not paying attention, it would be easy to get wrong, as the grandparent response points out.
Interestingly the method used to deal bridge hands for top tournaments doesn’t shuffle at all, it generates a random number between 1 and 52!/(13!^4) and maps that number to a corresponding deal of the cards.
> If shuffling, look up a real algo (like Fisher-Yates for instance) and implement that. Or better yet, use a library implementation.
If using a library implementation, you do still need to validate that it's using a proper algorithm. And that it doesn't change to something else during an update. Which probably requires you to understand the algorithm, and looking at wikipedia, it's a handful of lines of code to do it right and know that it doesn't change because it's your code. Maybe not worth the time to inspect and reinspect from a library.
The amount of land in your starting hand often determines the game's outcome in Magic. This is not seen as "fun" by many players. Why play a supposedly skill-based game if RNG is so strong?
So it's quite possible that the online Magic game manipulates the deck. Keeps players engaged more so they make more money. Pretty standard these days; Candy Crush famously does this too. Looks random, but very much isn't.
If you have a perfect shuffle, something like 10-15% of MTG hands are basically unplayable, and another 10-20% have no realistic chance of winning (eg too slow, not resilient, etc.). The exact fractions depend on the deck and your opponent.
The game mitigates this with a mulligan rule, where you can get another hand with one less card if you want. That way, you can get rid of a bad hand, but it costs a card each time. Commonly, magic players overvalue the card, and don't mulligan hands that they should, but it is also possible (and common) to just lose games to luck even if you do everything right - top MTG pros only have ~65-70% win rates against random people.
MTG arena apparently also does an internal free mulligan for you (to make the game more fun) - it draws 2 hands initially and gives you the one with the better mix of cards.
Shuffling an array is surprisingly easy to screw up because the "easy obvious" way (for each index in array swap with a random index in the array) doesn't work but superficially will look like it does.
I've definitely done this before, though mainly in non-critical situations (eg: shuffling a bunch of product images to display on a screen in store) where I didn't care too much if it wasn't TRUE shuffling.
Is there a name for this approach/any info on why it doesn't work?
This feels like it should work from a clear induction argument.
Base case: n=1. Obvious.
Inductive step: n>1. The nth element swaps to itself w/ prob 1/n, and to any other element w/ prob 1/n. By induction the other elements have been uniformly shuffled. Any of those elements is swapped to the nth place w/ prob 1/n.
If your n-1 elements are uniformly shuffled, swapping with them would undo that. So to preserve the uniformity invariant, you have not to touch elements that were already shuffled, which leads you to Fisher–Yates.
Info why it doesn't work: the smallest array for which it fails has 3 elements. When you start with a sorted array, iterate through each element and move it to one of the 3 positions with equal probability, there are 3³ = 27 possible move sequences, each with probability 1/27, but only 3! = 6 possible outcomes (permutations of the array). Because 6 doesn't divide 27, there must be some outcomes that are generated by more move sequences than others and hence occur more often.
An easy argument why it cannot work: consider an array with 3 elements, [a,b,c]. “Shuffling” it could look as follows.
Step 1. Swap a, c -> [c,b,a]
Step 2. Swap b, c -> [b,c,a]
Step 3. Swap a, a -> [b,c,a]
What is the probability that we do exactly these steps? At each step, we have 3 choices, so (1/3) * (1/3) * (1/3) = 1/27. What is the probability that we end up with [b,c,a] ? You might think 1/27 as well, but that is not quite true – it is possible, that we choose different steps, but end up with the same result. For example, we can do [a,b,c]->[b,a,c]->[b,c,a]->[b,c,a]. But the probability will always be a multiple of 1/27 – it is just 1/27 times the number of possible paths that leads to [b,c,a].
Now, what should the probability be? There are exactly 6 ways to shuffle [a,b,c] (this is the number of permutations, 3! = 3 * 2 * 1 = 6). So we want to get [b,c,a] with a probability of 1/6. But 1/6 is not a multiple of 1/27 ! (You can see that by looking at the equation 1/6 = x/27, which is the same as x = 27 / 6 = 4.5 .)
The same argument works for any length n > 2, as n*n is not divisible by n-1, but n! is.
Its a problem that's trivial if you are allowed to allocate an array/list that's the same size as the input but tricky if you have to do the operation in place (unless you already know the fisher yates algorithm).
There's probably a bunch of other examples of this kind, (easy out of place, tricky in place) but non come to mind atm.
Worth pointing out the shuffle twice thing is only for Best of 1 to reduce the variance so it is similar to Best of 3. It’s strictly a casual format though.
You need a suitable non-null hypothesis to start with, too.
Suppose we're talking about a regular deck of cards, and someone says "the shuffler gives the first player too many hearts". That requires a different test to debunk/support it than the hypothesis "the shuffler gives the third player too many aces".
In other words, any claim that the shuffle is not random needs to include a testable assertion about the direction of bias it has, and allows you to make predictions about the next card with better than random accuracy.
The null hypothesis is that the cards are drawn from a uniform distribution, and if we only consider land/nonland as categories, it should be pretty straightforward to determine the probability of a sequence of draws under this distribution. Essentially it comes out to a weighted coin toss each time.
Pretty long and haven’t read it all, but worried about a sort of survivorship bias. You’ll see more cards from games that go on longer with the methodology described.
That and some spicy uncontrolled multiple-hypothesis testing.
Seems like a pretty unreliable analysis as a result.
If you read the article, there are some... oddities in the shuffler.
The more interesting comparisons that have been done are between what the shuffler is like for players that actually pay money to play the game and the entirely free to play crowd.
In head to head games there's always someone ready to blame 'the algorithm' for their loss rather than their own performance, deck matchup, or rng. (The usual suspects.)
Game developers are not incentivized to induce losses. Losses lead to poor session length and retention. Moreover, a desire for fast queue times discourages deck analysis by 'the algorithm'. Why restrict your matchmaking pool so you can pull the strings?
The only queue manip mechanism I know of is in the player's favor. If you're on a losing streak you can be queued with others on losing streaks as a way to break at least one of your steaks and prevent you from logging off.
Here's a plausible explanation for making screw worse on 2 landers and flood worse on 5 landers: Wizards has data showing that keeping a 2 or 5 lander is bad for their metrics but players still tend to do it often, and they wish to artificially deflate results with such hands to disincentivize people keeping them. Let's say naturally your deck will have a 30% win rate keeping a 2 lander but the shuffler enforces screw and your actual win rate is 20%. You remember keeping as worse than it really is and you mull more often on 2 lands, leading to longer and more engaging games.
Of course, no evidence for this at all, but it seems like a plausible reason to me why they might do something like what's described.
So in this hypothetical, the reason they want to push players into accepting better opening hands is because losing in such a way is no fun. So their strategy to teach players better behavior is to make them experience it more often and to a worse degree? Like a parent who makes their child smoke a whole carton of cigarettes because smoking is bad for you?
There are three kinds of "possible worlds" with respect to shuffling, in M:tG. Let's call them "shuffle-worlds". We have a) a Balanced World, where land and non-land are well-mixed and you can expect to draw them in a way that represents their distribution in your deck; b) a Glut World where there's a big bunch of land stacked close to your opening hand; and c) a Screw World where there's a big bunch of land stacked far from your opening hand.
Now, your opening hand can give you no more than a hint of which world you're in, but it's the best you can get, short of library manipulation, including reshuffling and land-thinning effects (which are not available to all decks). What's more, Screw World and Glut World are bad, and there's two of them, whereas Balanced World is good but there's only one of it. So you're more likely to be in the Screw or Glut World, than the Balanced World, in any game you play.
So if you get a 2-land opening hand, you can expect to be in a Screw World, and if not, then you can expect to be in a Glut World (with the glut of land lurking just beyond the first 7 cards). If you see a 5-land opening hand, the same but for a Glut World.
And if you get a balanced opening hand, well, you may not be in a balanced world but, at least, if you've built your deck right, you can play your game for a few turns, and that should really be enough.
Note that all that happens in the physical game, as well as the online games. The only difference is that in the online games the shuffling is done automatically, but whether this means it's a shuffle more or less likely to bring up Balanced World draws, that's up for research.
The solution is to always try to play degenerate decks: decks that need only very little land (Good, old, Senor Stompy being the exemplar- I'm talking about the 18-land Ice Age archetype) or decks that need a lot of land, like decks with big, splashy, expensive spells that need to be stuffed with 25-26 land (in 60-card formats that is). That way, you're artificially tipping the scales towards either a Glut World or a Screw World, but you've actually built your deck around it. And now you have two good worlds to look forward to (because the Balanced World is not going to hurt you if, again, you've designed your deck right) so luck's on your side.
You gotta make your own luck. The rest is self-deception. And people who play games of chance always have their little superstitions.
Match making games are actually designed to keep successful players and teams from winning too much. Essentially in something like Halo a competitive team will slowly empty out players in the queue over the course of the night, as their opponents choose to stop a few games early (devs responded by keeping those teams in queues longer than necessary).
MTGArena aggressively manipulates what kind of deck you will play against (which disables the ability to make a counter META deck, since after picking a few counter mechanisms you're very rarely going to be put against the archetype you foil even if you hunt half the field), manipulates who goes first (some Streamers stand at recording over a thousand games and have gone first under 30% of the time, current formats are extremely powered up so the first turn advantage is the deciding factor of who wins often), and manipulates opening hands (something the devs have blogged about).
While harder to prove MTGArena also buries/floats cards. Some cards have patterns of existing in your opening hand or only after your 17th-22th draw, others occur in your opening hand more than 50% of the time, some truly toxic cards like Agent of Treachery are likely to have 3 of 4 of your copies in the last 20 cards. (Agent of Treachery is the easiest to see since such decks also have to tools to cycle through their deck and stall out the game to see their whole deck).
The shuffler also has a habit of giving duplicates of cards or making someone draw a duplicate of a card more often than "expected".
> Match making games are actually designed to keep successful players and teams from winning too much.
> MTGArena aggressively manipulates what kind of deck you will play against
> manipulates who goes first
> MTGArena also buries/floats cards.
> The shuffler also has a habit of giving duplicates of cards or making someone draw a duplicate of a card more often than "expected".
These are all falsehoods spread by people who are looking for something to blame after losing games. Seeing patterns that are not there.
You're posting conspiracy theories as if they're facts. There is no evidence to support these claims. Why would the developers spend money implementing such features just to make their players angry and dissatisfied? They can barely hold the game together as it is.
> and manipulates opening hands
This part is true, but only in a limited way in best-of-1.
>Match making games are actually designed to keep successful players and teams from winning too much.
Match making is generally designed to provide fair matches; this will naturally result in even really good players losing matches as their ELO rating converges on where it's supposed to be. It's like how in many games you'll see players complaining about a "forced 50% winrate" when really, that's just what happens when you're at roughly where you're supposed to be. You can't win forever.
> MTGArena aggressively manipulates what kind of deck you will play against
Only in Historic brawl is there desk strength based matchmacking
> manipulates who goes first (some Streamers stand at recording over a thousand
Never confirmed.
> While harder to prove MTGArena also buries/floats cards. Some cards have patterns of existing in your opening hand or only after your 17th-22th draw
Not confirmed, and an easy thing to get confirmation-bias on.
>The shuffler also has a habit of giving duplicates of cards or making someone draw a duplicate of a card more often than "expected".
Not confirmed and doesn't make sense? It's not like the shuffler is shuffling the deck as you play, that would break far too much.
EDIT: To be clear, the only actual shuffle "rigging" Magic Arena does (that the devs have talked about extensively due to Arena being Bo1 and Magic traditionally being Bo3) is your initial hand is generated twice and the shuffler chooses what it thinks is the better opening hand to present to you. After that it's all random.
62 comments
[ 3.7 ms ] story [ 119 ms ] threadI believe the only thing it does is shuffle your deck twice and try to give you the better starting hand of the two.
That said people do sometimes unintentionally write something like this (terrible and also buggy) algo
...which won't give an even distribution of all possible outcomes. If shuffling, look up a real algo (like Fisher-Yates for instance) and implement that. Or better yet, use a library implementation.Nerd sidenote: Because generating random numbers tends to be expensive, I had an idea once where you generate the full permutation with only a single random sample. Basically you could use something which fully enumerates a space like Gray codes[1] (you want one with a closed form solution which can arbitrarily you the nth code) then you generate one random number, multiply by the number of combinations, look up that code and decode that into the sequence of cards. I never actually got around to implementing it, but I suspect if your code lookup was fast it would be much faster than Fisher-Yates.
The use case was if you wanted to make a Monte Carlo algorithm to evaluate strategies in a card game for instance.
[1] https://en.wikipedia.org/wiki/Gray_code
Might not work - as I say I never actually got around to implementing it.
[1] https://en.wikipedia.org/wiki/Factorial_number_system [2] https://en.wikipedia.org/wiki/Lehmer_code
Also, you’ll have to make sure you pick each permutation is picked with equal probability. random() % factorial(52) likely won’t work because your RNG won’t return integers in a range k × 52! for some k > 1 (https://stackoverflow.com/questions/10984974/why-do-people-s...)
You can think of it as rolling one random number up to n!, then use x%n to pick the first element and then x/n to pick the next (n-1) elements (so the next step is then to pick the second element with (x/n)%(n-1) and use (x/n)/(n-1) for the remaining (n-2) elements).
Though as a sibling comment points out, since you need a random number up to n!, even 64 bits of randomness only get you so far (I think up to 20, but didn't check my math).
for i in [0..n-1] swap(a[i], a[rand in [i..n-1])
where rand in [I..n-1] coud be implemented as i + (rand() % (n-i))
essentially start with your finger at 0, pick a card from the unpicked set which is everything on and after your finger, swap that card with your finger, move your finger up one card
Fisher-Yates is pretty obvious but weirdly subtle in some ways. For someone not paying attention, it would be easy to get wrong, as the grandparent response points out.
[0] https://mechaelephant.com/dev/Fisher-Yates-Shuffle.html
https://sater.home.xs4all.nl/doc.html
If using a library implementation, you do still need to validate that it's using a proper algorithm. And that it doesn't change to something else during an update. Which probably requires you to understand the algorithm, and looking at wikipedia, it's a handful of lines of code to do it right and know that it doesn't change because it's your code. Maybe not worth the time to inspect and reinspect from a library.
That hasn't stopped the rumors.
So it's quite possible that the online Magic game manipulates the deck. Keeps players engaged more so they make more money. Pretty standard these days; Candy Crush famously does this too. Looks random, but very much isn't.
The game mitigates this with a mulligan rule, where you can get another hand with one less card if you want. That way, you can get rid of a bad hand, but it costs a card each time. Commonly, magic players overvalue the card, and don't mulligan hands that they should, but it is also possible (and common) to just lose games to luck even if you do everything right - top MTG pros only have ~65-70% win rates against random people.
MTG arena apparently also does an internal free mulligan for you (to make the game more fun) - it draws 2 hands initially and gives you the one with the better mix of cards.
Is there a name for this approach/any info on why it doesn't work?
Base case: n=1. Obvious.
Inductive step: n>1. The nth element swaps to itself w/ prob 1/n, and to any other element w/ prob 1/n. By induction the other elements have been uniformly shuffled. Any of those elements is swapped to the nth place w/ prob 1/n.
This proves that
works as a shuffle, by growing a random sub-array.*The first algorithm was
which has different biases.* I am not actually sure that this actually works.
Now, what should the probability be? There are exactly 6 ways to shuffle [a,b,c] (this is the number of permutations, 3! = 3 * 2 * 1 = 6). So we want to get [b,c,a] with a probability of 1/6. But 1/6 is not a multiple of 1/27 ! (You can see that by looking at the equation 1/6 = x/27, which is the same as x = 27 / 6 = 4.5 .)
The same argument works for any length n > 2, as n*n is not divisible by n-1, but n! is.
There's probably a bunch of other examples of this kind, (easy out of place, tricky in place) but non come to mind atm.
Suppose we're talking about a regular deck of cards, and someone says "the shuffler gives the first player too many hearts". That requires a different test to debunk/support it than the hypothesis "the shuffler gives the third player too many aces".
In other words, any claim that the shuffle is not random needs to include a testable assertion about the direction of bias it has, and allows you to make predictions about the next card with better than random accuracy.
That and some spicy uncontrolled multiple-hypothesis testing.
Seems like a pretty unreliable analysis as a result.
The more interesting comparisons that have been done are between what the shuffler is like for players that actually pay money to play the game and the entirely free to play crowd.
Game developers are not incentivized to induce losses. Losses lead to poor session length and retention. Moreover, a desire for fast queue times discourages deck analysis by 'the algorithm'. Why restrict your matchmaking pool so you can pull the strings?
The only queue manip mechanism I know of is in the player's favor. If you're on a losing streak you can be queued with others on losing streaks as a way to break at least one of your steaks and prevent you from logging off.
Of course, no evidence for this at all, but it seems like a plausible reason to me why they might do something like what's described.
Now, your opening hand can give you no more than a hint of which world you're in, but it's the best you can get, short of library manipulation, including reshuffling and land-thinning effects (which are not available to all decks). What's more, Screw World and Glut World are bad, and there's two of them, whereas Balanced World is good but there's only one of it. So you're more likely to be in the Screw or Glut World, than the Balanced World, in any game you play.
So if you get a 2-land opening hand, you can expect to be in a Screw World, and if not, then you can expect to be in a Glut World (with the glut of land lurking just beyond the first 7 cards). If you see a 5-land opening hand, the same but for a Glut World.
And if you get a balanced opening hand, well, you may not be in a balanced world but, at least, if you've built your deck right, you can play your game for a few turns, and that should really be enough.
Note that all that happens in the physical game, as well as the online games. The only difference is that in the online games the shuffling is done automatically, but whether this means it's a shuffle more or less likely to bring up Balanced World draws, that's up for research.
The solution is to always try to play degenerate decks: decks that need only very little land (Good, old, Senor Stompy being the exemplar- I'm talking about the 18-land Ice Age archetype) or decks that need a lot of land, like decks with big, splashy, expensive spells that need to be stuffed with 25-26 land (in 60-card formats that is). That way, you're artificially tipping the scales towards either a Glut World or a Screw World, but you've actually built your deck around it. And now you have two good worlds to look forward to (because the Balanced World is not going to hurt you if, again, you've designed your deck right) so luck's on your side.
You gotta make your own luck. The rest is self-deception. And people who play games of chance always have their little superstitions.
MTGArena aggressively manipulates what kind of deck you will play against (which disables the ability to make a counter META deck, since after picking a few counter mechanisms you're very rarely going to be put against the archetype you foil even if you hunt half the field), manipulates who goes first (some Streamers stand at recording over a thousand games and have gone first under 30% of the time, current formats are extremely powered up so the first turn advantage is the deciding factor of who wins often), and manipulates opening hands (something the devs have blogged about).
While harder to prove MTGArena also buries/floats cards. Some cards have patterns of existing in your opening hand or only after your 17th-22th draw, others occur in your opening hand more than 50% of the time, some truly toxic cards like Agent of Treachery are likely to have 3 of 4 of your copies in the last 20 cards. (Agent of Treachery is the easiest to see since such decks also have to tools to cycle through their deck and stall out the game to see their whole deck).
The shuffler also has a habit of giving duplicates of cards or making someone draw a duplicate of a card more often than "expected".
> MTGArena aggressively manipulates what kind of deck you will play against
> manipulates who goes first
> MTGArena also buries/floats cards.
> The shuffler also has a habit of giving duplicates of cards or making someone draw a duplicate of a card more often than "expected".
These are all falsehoods spread by people who are looking for something to blame after losing games. Seeing patterns that are not there.
You're posting conspiracy theories as if they're facts. There is no evidence to support these claims. Why would the developers spend money implementing such features just to make their players angry and dissatisfied? They can barely hold the game together as it is.
> and manipulates opening hands
This part is true, but only in a limited way in best-of-1.
Match making is generally designed to provide fair matches; this will naturally result in even really good players losing matches as their ELO rating converges on where it's supposed to be. It's like how in many games you'll see players complaining about a "forced 50% winrate" when really, that's just what happens when you're at roughly where you're supposed to be. You can't win forever.
> MTGArena aggressively manipulates what kind of deck you will play against
Only in Historic brawl is there desk strength based matchmacking
> manipulates who goes first (some Streamers stand at recording over a thousand Never confirmed.
> While harder to prove MTGArena also buries/floats cards. Some cards have patterns of existing in your opening hand or only after your 17th-22th draw
Not confirmed, and an easy thing to get confirmation-bias on.
>The shuffler also has a habit of giving duplicates of cards or making someone draw a duplicate of a card more often than "expected".
Not confirmed and doesn't make sense? It's not like the shuffler is shuffling the deck as you play, that would break far too much.
EDIT: To be clear, the only actual shuffle "rigging" Magic Arena does (that the devs have talked about extensively due to Arena being Bo1 and Magic traditionally being Bo3) is your initial hand is generated twice and the shuffler chooses what it thinks is the better opening hand to present to you. After that it's all random.