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.

Of course, the question is why would this be the case in Arena. You play against other players, not the casino.

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.

They make money by selling the cards right? I would think that might change their incentives somewhat. I don’t really know the game.

The better "experience" they transmit to the players, the more engaged they will be and the more cards/packs they will sell

Players who aren’t having fun won’t buy cards or will stop buying cards when they quit.

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.

The correct Fisher-Yates shuffle is this (from Wikipedia):

  -- To shuffle an array a of n elements (indices 0..n-1):
  for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

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.

[0] https://mechaelephant.com/dev/Fisher-Yates-Shuffle.html

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.

Are you sure they do bijective mapping instead of simply running a RNG with the given seed?

Yes - see the “Making bridge deals” section of:

https://sater.home.xs4all.nl/doc.html

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

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.

[1] https://en.wikipedia.org/wiki/Gray_code

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.

I think you're looking for a factorial number system [1] and/or Lehmer code [2].

[1] https://en.wikipedia.org/wiki/Factorial_number_system [2] https://en.wikipedia.org/wiki/Lehmer_code

Thanks!

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).

> 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.

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.

I don't think you can apply this proof to the described algorithm.

This proves that

    for i in range(min_key,max_key):
        swap(arr, i, choice(i, max_key))

works as a shuffle, by growing a random sub-array.*

The first algorithm was

    for i in range(min_key,max_key):
        swap(arr, i, choice(min_key, max_key))

which has different biases.

* I am not actually sure that this actually works.

Ah, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.

Your first one is one of the versions of the standard Fisher–Yates shuffle, so it does work :)

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.

True shuffling is pretty easy to achieve, most programming language already have array.shuffle() methods.

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.

Why would the developers be constrained this way when decks are like 60 cards long? Surely any app can spare that much memory.

The original version of magic online from the early 2000s messed it up slightly, but since then, the shuffles have been perfect.

That hasn't stopped the rumors.

What? It manipulates the hand?

In the best of one, more casual mode, yes.

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.

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.