OK, I had a hard time coming up with a single sentence title, so please bear with me.
Let’s assume I have a computer with a perfect random number generator. I want to draw from a (electronic) deck of cards that have been shuffled. I can see two distinct algorithms to accomplish this:
-
Fill a list with the 52 cards in random order, and then pull cards from the list in sequence. That is, defining the (random) sequence of cards before getting them. This is analogous to flipping over cards from a the top of a well-shuffled deck.
-
Generate a random card from the set that hasn’t been selected yet. In other words, you don’t keep track of what card is going to come up next, you do a random select each time.
Programattically I can see advantages to both systems, but I’m wondering if there’s any mathematical or statistical difference between them.
Mathematically, no, there is no difference.
However, if you’re playing a card game that requires deck manipulation, you will of course want to generate the whole deck at once, because you might need to perform actions like placing a card from your hand on the bottom of the deck. You can’t do that if the rest of the deck doesn’t exist yet.
If you’re generating cards at draw time, it can get expensive to check to see if a card has been generated yet, because you’ll have to check the table, everyone’s hand, and the discard pile. Or maintain a separate list of all cards generated so far, but at that point you might as well have just generated a whole deck in the first place.
if you’re playing a card game that requires deck manipulation…
Ah! This is something that I hadn’t directly considered. Interesting point, and it could be a serious concern for some games.
Thanks!
Assuming I’m understanding your thought experiment correctly, AFAIK, unless the chance of a duplicate card coming up is an issue, it should be about the same.
QI did a bit about this:
The chances that anyone has ever shuffled a pack of cards in the same way twice in the history of the world are infinitesimally small, statistically speaking. The number of possible permutations of 52 cards is ‘52 factorial’ otherwise known as 52! or 52 shriek. This is 52 times 51 times 50 . . . all the way down to one. Here’s what that looks like: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.
To give you an idea of how many that is, here is how long it would take to go through every possible permutation of cards. If every star in our galaxy had a trillion planets, each with a trillion people living on them, and each of these people has a trillion packs of cards and somehow they manage to make unique shuffles 1,000 times per second, and they’d been doing that since the Big Bang, they’d only just now be starting to repeat shuffles.
There’s one quibble about this that might actually alter the answer for OP. Your numbers are correct for purely random shuffles, but a shuffle isn’t purely random. A significant number of shuffles begin with a fresh deck where the cards are arranged in order and by suit. And a significant number of shufflers use the same methods, specifically the riffle, the overhand, or some other variant of those.
This is relevant to the field of cryptography, because humans are bad at simulating randomness. If you were to draw the top card from a shuffled deck, you probably have a lower chance of drawing an ace of spades than any other card, simply because the shuffler would not feel like they had shuffled if it was still on top. When picking lotto numbers, people tend to spread out their picks to get a quasi-even distribution across the available numbers, but it’s just as likely to come up 1, 2, 3, 4, 5, and 6 as any other combination of numbers. Likewise, people playing with cards tend to cluster suits or pairs together when playing, so you’d be more likely to see those cards in proximity depending on the type of shuffle. Overhand tends to keep clumps together, and riffle or weave tend to interlace the cards in a way that still keeps pairs, sets, and runs close.
Of course, the difference would only be mathematically interesting, since in practice a good few shuffles is certainly close enough to completely random, especially if you start with a previously-shuffled deck. If you were trying to predict a card, your odds on any given draw is still going to be roughly 1 in 52.
I have seen the QI clip a few times and never thought about this. Very interesting! Thank you for explaining it.
Well, a little bit of ‘yes’ and a little bit of ‘no’.
If it is possible over the course of the game for turn orders to be changed, or for a player to choose to draw a card, or cause another player to draw a card, then it matters in a way.
If I can cause actions to make another player draw a card, then it is more meaningful if the deck is shuffled already, because the card that I caused the player to draw is the same as the card I would have drawn if I drawn a card instead. However, from the perspective of the user, there is no way for them to know the difference.
I feel like it is better for the integrity of the game if the deck is shuffled for real, though. Because if ever a user finds out that it doesn’t work how it is expected, then it cheapens the experience in a way. Kind of like how the old Mario Party games determined the outcome of dice rolls when the die appeared on screen instead of when you pressed the button to ‘roll’ them.
If it is possible over the course of the game for turn orders to be changed, or for a player to choose to draw a card, or cause another player to draw a card, then it matters in a way.
This is a fascinating wrinkle, and quite correct. (and non-obvious, I would say.)
Everything that people have been posting leans towards laying out the order ahead of time, even if there’s no mathematical difference in drawing the next card.
(Unless you’re not dealing with a deck of cards, but instead 50k decks at once. :-D )
I mean, you can get the same sequence of cards, as long as your mechanism used to select a card in #1 is the same as in #2. It’s just like doing #2 52 times in advance and then recording the results.
There are certain reasons that you might want to do #1 that don’t relate to the sequence of cards coming up. There are certain problems involving multiple untrusted parties where it can be advantageous to be able to prove that you have not fiddled with the card order after the initial “deal”; one way to do this is to generate and then transmit an encrypted list of cards, then later send the decryption keys.
https://en.wikipedia.org/wiki/Mental_poker
Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum’s flipping a coin over a distance, Yao’s Millionaires’ Problem, and Rabin’s oblivious transfer.
The problem can be described thus: “How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?” (Eliminating the trusted third-party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the resources required.)
An algorithm for shuffling cards using commutative encryption would be as follows:
- Alice and Bob agree on a certain “deck” of cards. In practice, this means they agree on a set of numbers or other data such that each element of the set represents a card.
- Alice picks an encryption key A and uses this to encrypt each card of the deck.
- Alice shuffles the cards.
- Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
- Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
- Bob shuffles the deck.
- Bob passes the double encrypted and shuffled deck back to Alice.
- Alice decrypts each card using her key A. This still leaves Bob’s encryption in place though so she cannot know which card is which.
- Alice picks one encryption key for each card (A1, A2, etc.) and encrypts them individually.
- Alice passes the deck to Bob.
- Bob decrypts each card using his key B. This still leaves Alice’s individual encryption in place though so he cannot know which card is which.
- Bob picks one encryption key for each card (B1, B2, etc.) and encrypts them individually.
- Bob passes the deck back to Alice.
- Alice publishes the deck for everyone playing (in this case only Alice and Bob, see below on expansion though).
The deck is now shuffled.
… you do a random select each time.
Is that even possible? I know that computers are not able to make true randomness, and that people are even worse at it. There’s that lava lamp wall that somebody uses, maybe?
Computers are able to “make true randomness” if you give them the appropriate sensors and hardware, leveraging physical phenomena. Regardless, OP specified the following:
Let’s assume I have a computer with a perfect random number generator.
The lava lamps are not true random though. For something to be truly random, it must be non-deterministic (no seed at all). The only way for a computer to accomplish this is to read from a source of true randomness in nature. The lava lamps are random enough, but not truly random.
At the moment, the only source thought of being non-deterministic is quantum mechanics.
So if you make a computer generate random numbers out of the randomness of quantum mechanics, you would have truly random numbers.
And even then, if you look at quantum mechanics through the right lens, its apparent randomness is only an illusion of perspective. If you flip the quantum coin, then with 100% certainty, perfectly deterministically, it will come up heads in one timeline and tails in the other. It’s only because your two future selves can’t interact with each other that they can’t have an argument about what the result “really” was, so one says, “it actually came up heads, and the result was completely random,” and the other says, “it actually came up tails, and the result was completely random.”
deleted by creator
Yeah, #2 is both more space efficient and more time efficient.
How I’d generally do something like that:
- Create an empty linked list.
- Generate a random integer between 0 and 51 inclusive.
- Iterate over the linked list and increment the random integer by one for each integer in the linked list less than or equal to your newly-generated random integer. You can break out of that loop as soon as you hit the first integer in the linked list greater than the newly-generated integer.
- Binary insert that integer into the sorted linked list.
- For the denomination, output the newly-generated integer modulus 13 plus one. Translate 1 to ace, 11 to jack, etc.
- For the suit, output floor of the newly-generated integer divided by 4 plus one. (Translate zero to “hearts”, one to “diamonds”, etc.)
- Loop back to step 2 51 more times.
Step 3 can definitely be optimized much more with a B-tree and a little thought. If you want jokers included, it’s pretty straightforward. (Just change step 2 to generate a random integer between 0 and 53 and tweak steps 5, 6, and 7.)
I think you’re approach is generally correct, but you’ve made a few errors which make it hard to follow (e.g. mixing up suit and denomination).
However, method two is only more efficient if onky a few cards will be drawn. If nearly the entire deck is drawn or dealt, then 1 is superior. Method 1 can be done with two lists and a random number generator. The length of the 2 lists will always sum to 52 and the RNG is used to decide the order that cards are removed from the first list and added to the 2nd. It requires generating at most 51 random numbers.
Good call on both counts!
I went ahead and fixed the suit/denomination mixup. I’ll leave the reast as-is so folks can learn from my mistakes and your post continues to make sense.
Cheers!
