7 ms·
I analyzed shuffling in a million games of MtG Arena (2020)
- jmuguy 4y agoI 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.
- seanhunter 4y agoI 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.
- gambiting 4y agoOf course, the question is why would this be the case in Arena. You play against other players, not the casino.
- jna_sh 4y agoThe 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.
- seanhunter 4y agoThey make money by selling the cards right? I would think that might change their incentives somewhat. I don’t really know the game.
- slackfan 4y agoYes, 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.
- manimino 4y agoThe 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]
- seanhunter 4y agoRight. 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 https://en.wikipedia.org/wiki/Gray_code
- 6keZbCECT2uB 4y agoI'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.
- seanhunter 4y agoThe 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.
- toast0 4y ago> 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.
- pclmulqdq 4y agoThe 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.
- rightbyte 4y agoWhat? It manipulates the hand?
- uxp100 4y agoIn the best of one, more casual mode, yes.
- manimino 4y agoThe 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.
- pclmulqdq 4y agoIf 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.
- Marazan 4y agoShuffling 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.
- drawfloat 4y agoI'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?
- charlieyu1 4y agoTrue shuffling is pretty easy to achieve, most programming language already have array.shuffle() methods.
- senkora 4y agoThis 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.
- afiori 4y agoI 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.
- senkora 4y agoAh, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.
- nvarsj 4y agoWorth 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.
- toxik 4y agoI don’t quite understand, why can’t you just determine the probability of a game’s draws and do a regular null hypothesis test?
- dmurray 4y agoYou 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.
- toxik 4y agoThe 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.
- deleted 4y ago[deleted]
- ProjectArcturis 4y agoNo, you can do a Chi-squared to test whether the distribution is significantly different from theory in any way.
- strstr 4y agoPretty 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.
- zahrc 4y agoThread is 3 years old and no 100% conclusive answer was found - move along nothing to see here.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- avgcorrection 4y agoHow do you test a shuffle procedure?
- pclmulqdq 4y agoDo it a lot of times and see if the outcome is statistically different from expected.
- slackfan 4y agoIf 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.
- a13o 4y agoIn 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.
- cool_dude85 4y agoHere'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.
- usea 4y agoSo 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?
- cool_dude85 4y agoThe idea would be to make it artifically worse (in terms of win rate) so it becomes less common.
- 4y ago