8 ms·
The Math of Card Shuffling (2018)
- thunderrabbit 6y agoWhy can't I keep riffling once the King reaches the top? I thought I had found my next idle clicker.
- 1f60c 6y agoI love articles that marry prose and interactive simulations to make a point.
- wodenokoto 6y agoWhy does every card, on average, need to be ruffled in order for the dev to be randomized?
- crdrost 6y agoThey talk about this in the associated Numberphile video. The starting bottom-most card can be thought of as creating a partition of the deck into two parts: the ones "above" it are not uniformly shuffled but the ones "below" it must be, and so right at the moment when it is placed into the deck, the deck must become perfectly uniformly shuffled and any further shuffles cannot take it out of that state. They also cover that overhand shuffles in practice require something like 10,000 shuffles to properly randomize. The problem is familiar to cryptographers: this scheme has "confusion" but not "diffusion". You can see this yourself: sort a deck of cards[1], then do two overhand shuffles in a row and splay out the cards and look at how random the result looks. They kind of "undid" each other, they "commuted" with each other or so. If you want something a little more interesting, try to overhand shuffle with large cuts and then overhand shuffle with smaller cuts, and this gives somewhat more diffusion. Or just overhand-large, overhand-small, and then riffle -- the riffle will give you tremendous diffusion of the cut entropy created by the overhands. Anecdotally it seems somewhat unlikely that one gets to the full 220-something bits of randomness from only 7 riffles as that would require each riffle to have 30+ bits of entropy which seems... unlikely. [1] you can do this fastest probably with a sort of omniscient quicksort: sort black/red, then sort black into spades/clubs, then sort spades into high/low, then sort the 6 low spades by eye, then sort the 7 high spades by eye, then sort clubs into high/low...
- sjcsjc 6y agoSeems a good opportunity to link to this again: http://czep.net/weblog/52cards.html http://czep.net/weblog/52cards.html
- TedDoesntTalk 6y agoThat neon blue glow really hits the spot!
- throwaway744678 6y agoThe explanation of the 1-card riffle looks fine on a purely mathematical (computer) simulation, but what about an actual human trying to do it manually? I'd presume one would be much more likely to insert the top card somewhere near the middle of the deck, and almost never at or near the top, nor at the bottom of it. Would the calculation still stand, or should one need more riffles to reach a truly random state?
- have_faith 6y agoThere's a sort of magic trick involving doing perfect riffle shuffles where the whole deck retains it's order. If my memory is correct if you perform 8 perfect riffle shuffles (split deck 50/50, riffle one for one card correctly) then the order resets itself after 8 shuffles. It's usually only performed as a demonstration of skill by experienced card magicians than as a standalone trick.
- impendia 6y agoYup! That's correct, here's a demonstration: https://www.youtube.com/watch?v=rEoYwyHddLc https://www.youtube.com/watch?v=rEoYwyHddLc Explaining why it works is an exercise in number theory. For example, card 1 stays in place; card 2 goes to position 3, then 5, then 9, then 17, ... In short, the reason why it works is that 2^8 - 1 is divisible by 52 - 1.
- bhrgunatha 6y agoWhat amazing control in that video. From the very start, spreading the cards so evenly that every single card can be shown to be in order, then even more the precision needed to riffle the cards together perfectly eight times.
- wool_gather 6y agoIt you want to see more amazing, Ricky Jay could do this while keeping up a stream of amusing patter and making his hand motions seem almost casual. E.g. https://www.youtube.com/watch?v=eonlrksCsw8 https://www.youtube.com/watch?v=eonlrksCsw8
- bena 6y agoRichard Turner does it with patter, casual motions, and while being blind. https://en.wikipedia.org/wiki/Richard_Turner_(magician) https://en.wikipedia.org/wiki/Richard_Turner_(magician)
- 6y ago
- b0rsuk 6y agoWhat the article failed to mention is that a very common shuffling method - overhand shuffle - is terrible. You need about 10000 (ten thousand) of them to shuffle an ordinary deck of 52 cards. This can seriously impact you when playing board games, and collectible card games like Magic: the Gathering. In competitive CCGs it can make the game unfair. In non-competitive games it just makes it boring because the same situations tend to occur. Smushing is a great way to shuffle cards (used on poker tournaments) but it doesn't work if they're sleeved. For this reason I really appreciate board games which use bags and tokens as card substitutes. It's really the best shuffling method, except that token-sized cards don't have room for text on them. Now that I mention it I'm surprised there are no playing cards in the form of bag and tokens. Probably because ordinary playing cards are so cheap.
- strogonoff 6y ago> You need about 10000 (ten thousand) of them to shuffle an ordinary deck of 52 cards. My source[0] says the lower bound for full overhand shuffle is number of cards squared, so less than 3000 shuffles for 52 cards. Upper bound around 5000. Your source? [0] https://arxiv.org/abs/math/0501401 https://arxiv.org/abs/math/0501401
- tridentboy 6y agoWell, it seems that his point still stands. Overhand shuffle is terrible for actually shuffling a deck of cards.
- strogonoff 6y agoAssuming 4 shuffles per second, 3000 shuffles would take about 12.5 minutes, while 10000 shuffles would take more than 40 minutes. One of those sounds feasible during a break on a casual game night. Of course, those numbers apply only if the shuffle is done literally—I personally try to mix individual cards by letting one hand’s batch cut in-between the other’s (and I think I’m not the only one)—but I’m still curious where did those 10000 come from.
- 6y ago
- mswen 6y agoI went down the rabbit hole of looking at Idyll [0] the tool that he uses to create the shuffling simulation. Some pretty interesting examples in the gallery. Trying to decide whether the capabilities are worth the learning curve. [0]https://idyll-lang.org/ https://idyll-lang.org/
- dghughes 6y agoAn interesting bit if history. Electronic card shuffles were invented by a former truck driver. Casinos rented the devices from his company I don't think any were sold (their value was approximately $20,000 each). I haven't worked at a casino for four years but at that time I beleive the market opened up. It sounds like a patent expired or maybe the fisr card shuffle company was sold.
- zxcvbn4038 6y agoYou can buy card shufflers on Amazon for under twenty dollars. I've only used one once and geez was it loud - hopefully they do not all have that issue. https://www.amazon.com/card-shuffler-automatic-card-shuffler/b?ie=UTF8&node=13291451 https://www.amazon.com/card-shuffler-automatic-card-shuffler...
- dghughes 6y agoThe casino type shuffler have cameras to read the cards and remember the order of the cards after shuffling them. It also has a pseudorandom number generator it uses as a guide to shuffling randomly. You need to set the card type before loading too. Casinos order their own cards so you need to make sure the shuffler can read them. At casinos there's so many proprietary devices for example a small plastic block like a prism the size of a quarter. It sits on the table in the area where the dealer sets his cards. Blackjack dealers use it to view their cards when face down only they can see the image. Just that little stupid plastic block is patented and costs something like $10 per device per day for every casino that leases them.
- jonplackett 6y agoThe link in this to another article about the number of different combinations of cards is mind blowing. I mean, I know I should probably have realised that really, but I didn't think it would be such a beyond-astronomical number of potential orders.
- zxcvbn4038 6y agoAnd then you consider a game like blackjack where you often have six decks in play, 312! combinations instead of 52!. Interesting question just popped into my head, if the orientation of the card matters, how do people randomize that?
- ninju 6y agoThis page has a "workflow" you can go through to get a sense of how big 52! really is http://czep.net/weblog/52cards.html http://czep.net/weblog/52cards.html
- jonplackett 6y agoI'm designing a card game at the moment and have been pondering this because I'm doing play testing online, so the shuffling is done by a computer and is therefore perfectly random. I'm wondering how having non-perfect shuffling will affect the game play when it's a real world game and card combinations end up being left together.
- zxcvbn4038 6y agoThere are well known algorithms for shuffling cards, you don't need to reinvent it. Most online casinos use this: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://www.rosettacode.org/wiki/Knuth_shuffle https://www.rosettacode.org/wiki/Knuth_shuffle
- jonplackett 6y agoHey thanks for the article. What I mean though is that in real life people won’t shuffle the same way as the computer does so my online playtesting might be inaccurate. They’ll just do crap shuffling and cards will still be together in sets from the previous game - what I need is a bad / human shuffling algorithm that shuffles like lazy normal people do!
- WorldMaker 6y agoMost naive algorithms for card shuffling that you find people using that aren't Fischer-Yates or Knuth shuffle (as mentioned above) are sometimes "more lazy" than normal people and will give you worse results than the average human shuffling especially when you factor in how bad the average computer PRNG is. (Computers don't have "perfect random", so your assumption above is probably more amusing to me than you intended it to be. Even a bad/lazy human is still likely more "perfectly" random than the average computer.) (ETA: One perfect naive algorithm example is directly in the article here: the riffle one card at a time algorithm. Select any n riffles less than the mean 236 and it is a guaranteed lazy/bad shuffle. Even selecting above the mean doesn't guarantee a perfect shuffle, again because of the properties of a computer PRNG.)
- sbrass 6y agoNumberphile did cover this some years ago, see for example: https://www.youtube.com/watch?v=AxJubaijQbI https://www.youtube.com/watch?v=AxJubaijQbI
- bhrgunatha 6y ago148. Presumably some poor sap took over 350 riffles. https://imgur.com/Oh18356.png https://imgur.com/Oh18356.png
- praptak 6y agoSo 7 riffles can produce every permutation equiprobably, right? Is there a smaller number of riffles that can produce every permutation, not necessarily equiprobably?
- irontinkerer 6y ago> equiprobably I thought you made up that word, but you didn't! Thanks for teaching me somethign new! > e·qui·prob·a·ble > (of two or more things) equally likely to occur; having equal probability.
- Falling3 6y agoSophomore year of HS, my math teacher introduced us to the word equidistant. For at least an entire quarter, I thought he had a speech impediment and was trying to say "equally distant".
- andrewla 6y agoI don't think the arrangements are equiprobable. Well-distributed, likely. Heuristically, there are a finite number of outputs of a riffle shuffle (probably fairly large; basically the number of different ways that you can clump cards together, 52^20 or thereabouts). But any finite number of outputs raised to the 7th power is not going to divide 52 factorial, in terms of the number of output possibilities.
- data_now 6y ago8 Faro Shuffles later... Muhahaha!
- Taylor_OD 6y agoI've always shuffled three times due to hearing at some point in my childhood that 3 times was the max amount of shuffles needed to completely shuffle a deck. Recently I realized that doesnt check out but it's been hard to break the habit as more than 3 shuffles seems to take forever. 7 though? Wow.
- secdeal 6y agoWith practice you can get a riffle under 2-3 seconds without weaving. But if 7 still seems too much, do less but do a running cut or overhand shuffle between two of the riffles, like riffle -> riffle -> running cut -> riffle -> offer to cut -> deal. I heard this is what casinos did in older times, and they do have a direct interest in not making the shuffling too long (less hands played) or too weak (can be abused).
- gkop 6y agoThis inspires fond memories of the NexTag Programming Problem, which apparently has survived online longer than NexTag itself! https://spellscroll.wordpress.com/2008/12/10/nextag/ https://spellscroll.wordpress.com/2008/12/10/nextag/
- abfan1127 6y agoThis is fun! One thing I notice is that rarely do I get one-to-one riffles. Often they group 2-3 cards together. I've always wondered (but not enough to do the leg work) if those 2-3 cards tend to stay together shuffle to shuffle. Can small physical attributes (size, edge alignment, inter-card friction, air pressure) contribute these cards to affect the entropy?
- kenjackson 6y ago> Can small physical attributes (size, edge alignment, inter-card friction, air pressure) contribute these cards to affect the entropy? This is the basic premise of the Svengali deck of cards. One half of the cards is slightly smaller than the rest which gives the magician some ability to do tricks including things like "effectively" have two cards stick to each other (or jump each other). https://www.newcasinosonline.co/svengali-deck/ https://www.newcasinosonline.co/svengali-deck/
- tzs 6y agoA question I've wondered about is whether or not every possible permutation of the deck can be reached by riffle shuffling. As the article notes, a 1 card riffle can move the card at the end of the deck to any position within the deck, leaving the other cards undisturbed, so obviously you can reach any permutation by a series of 1 card riffles. What about if you can only use "believable" riffles? By "believable" I mean that the cut is near the middle of the pack, and the alternate left and right drops are mostly small and about the same size. The answer is yes, you can reach every permutation. Let P be a perfect out riffle shuffle. Let S(n) be an almost perfect out riffle shuffle, differing only in that when the cards that would end up n and n+1 from the bottom are the next two cards to drop in a perfect out riffle you drop switch the order they drop. S(n) is a believable riffle. The result of applying S(n) is the same as if you applied P and then swapped the two cards that are n and n+1 from the bottom. Let O(R), where R is any shuffle, be the minimum number of time you have to apply R consecutively before the deck returns to its starting order. (By "starting order" I mean the order it was in before you applied the O(R) R shuffles). For example, O(P) = 8, because 8 perfect out riffle shuffles leaves the deck in the order you started with. If you take a deck, do O(S(n))-1 shuffles using S(n), followed by one perfect out riffle P, the result is that the deck is back to its original order except that the cards at n and n+1 from the bottom are swapped. Since you can produce any permutation by a serious of swaps of adjacent items (hello, Bubble Sort!), this shows you can reach any permutation by a series of believable riffles. This is not necessarily an efficient way to achieve a given permutation, but hey, my bachelor's degree is in pure math, not applied math--efficiency is someone else's problem. :-) Swapping n and n+1 with the above procedure takes: 72 shuffles for n = 0 or 50 56 shuffles for 1 or 49 40 shuffles for 16, 17, 33, or 34 120 shuffles for 22 or 28 16 shuffles for everything else Here's some Python code to play with this [1]. It takes n as an argument, and just does the O(S(n))-1 shuffles with S(n) followed by a perfect out riffle and then displays what cards ended up moved, along with how many total shuffles were done. Probably not very efficient, as it was just a quickie for when I was playing around with this problem. (One shortcut it takes that might be confusing if you are not familiar with group theory. It does not actually do O(S(n))-1 applications of S(n). It takes advantage of the fact that the permutation you get by applying a permutation, R, O(R)-1 times is the same as applying the inverse permutation, R', once. So it actually just computes S'(n) and then applies S'(n) and P to the deck). PS: if you apply S(n) once followed by P seven times, the result is to swap card (n+1)//2 with n/2+26 if n is even, or with (n+1)/2+25 if n is odd. If you do S(n), 7 P, S(n+1), 7 P, S(n), 7 P you get swaps of consecutive cards. If n is even, you swap n/2 with n/2+1. If n is odd, you swap the cards that are 26 past the cards that doing this for n-1 would have swapped. That gives you a procedure for swapping any adjacent pair in 24 shuffles. That beats the original procedure I have for 10 values of n. [1] https://pastebin.com/bZW5ine7 https://pastebin.com/bZW5ine7
- SeanFerree 6y agoVery cool!
- andrewla 6y agoAlso interesting here is that the number of single-riffles taken is expressed as a harmonic series, which in the limit can be simplified for 52 * (log(52) + .57) (where .57 is the Euler gamma constant). So this approach of shuffling is O(n log n), which is also the expected complexity of putting the deck back in order with pairwise sorting.
- Yhippa 6y agoIf someone has tips on how to shuffle a deck of 100 double-sleeved cards without using a riffle I would love to hear them!
- matsemann 6y agoI once attended a talk by Roger Antonsen where he displayed lots of computer generated art he had made. The pictures of card shuffling he has made are simple but very elegant. https://rantonse.no/en/art/2018-07-25 https://rantonse.no/en/art/2018-07-25
- jonathathan 6y agoThis is a really nice visualization. One recommendation I'd have for the author is to use a four-colour deck (usually blue and green for diamonds and clubs). This would make it much easier to see where each card lands after inserting it randomly into the deck.
- dang 6y agoDiscussed at the time: https://news.ycombinator.com/item?id=17333047 https://news.ycombinator.com/item?id=17333047
- movedx 6y agoI would love to see someone pick up a $100,000 "Magic: The Gathering" vintage deck and giving it seven riffle shuffles saying, "The maths doesn't lie!" :P