How to really shuffle a deck of cards

Question

When I need to shuffle a deck of poker cards in Java/Android, I use Collections.shuffle(List<?> list), of course. I've ever been doing this and the results seemed acceptable. But they aren't.

As outlined in this paper, there are 52! possible unique shuffles of a 52 card poker deck. That amounts to about 2^226.

But Collections.shuffle(List<?> list) uses new Random() by default which uses a 48-bit seed and can therefore only create 2^48 unique shuffles - which is only 3.49*10^(-52) percent of all possible shuffles!

So how do I shuffle cards the right way?

I've started using SecureRandom, but is that enough, finally?

List<Card> cards = new ArrayList<Card>();
...
SecureRandom secureRandom;
try {
    secureRandom = SecureRandom.getInstance("SHA1PRNG");
}
catch (NoSuchAlgorithmException e) {
    secureRandom = new SecureRandom();
}
secureRandom.nextBytes(new byte[20]); // force SecureRandom to seed itself
Collections.shuffle(cards, secureRandom);

From the paper: _The first thing to realize is that an algorithm capable of producing each of the 52! shuffles is not really required._ — flup, May 03 '13 at 14:49
you could generate a random number which define how often you shuffle the deck — Philipp Sander, May 03 '13 at 14:50
@Philipp Sander: Repeated shuffling does not increase randomness, does it? — caw, May 03 '13 at 14:53
than why not use Collections#shuffle? every shuffle generates an new (and random) start situation to shuffle with — Philipp Sander, May 03 '13 at 14:57
Because it can only generate an unbelievably small amount of all possible shuffles, as I've written in the question. — caw, May 03 '13 at 15:07
http://blog.uncommons.org/2008/04/10/a-java-programmers-guide-to-random-numbers-part-3-seeding/ This might help, I also updated my answer to not-totally-nonsense according to the article. — zw324, May 03 '13 at 15:09
Why not replace the generator with a better one than the default? (http://en.wikipedia.org/wiki/Mersenne_twister) might be a possibility. — pjs, May 03 '13 at 17:31
@pjs: Isn't the Mersenne Twister 32-bit or 64-bit while SHA1PRNG is 160-bit? — caw, May 03 '13 at 17:45
@MarcoW.Mersenne Twister produces 32 bit or 64 bit outcomes, but it's based on a much much larger internal state - its cycle length is 2^19937-1. — pjs, May 03 '13 at 18:11
Does that make any difference if the output is only 64 bit? Since this is what you seed PRNG with, isn't it? — caw, May 03 '13 at 22:36
@MarcoW. I believe it does. In any singly-seeded generator, like LCG's, once you see a given value for the second time the entire sequence will be repeated identically. When a larger state is collapsed/projected onto a smaller output state, seeing a repeat of the same value doesn't mean you will get a repeat of the same sequence. As for seeding, that's just picking an entry point into the big cycle. 64 bit seed means you pick one of around 10^18 entry points to the loop of length 2^19937-1. — pjs, May 04 '13 at 10:32

paxdiablo · Accepted Answer · 2013-05-03T15:32:25.497

4

You may only be able to get 2⁴⁸ different hands from a specific starting arrangement but there's no requirement that you start at the same arrangement each time.

Presumably, after the deck is finished (poker hands, blackjack and so on), it will be in an indeterminate order, and any one of those rearrangements will be suitable.

And, if you're worried about the fact that you start from a fixed arrangement each time you start your program, just persist the order when exiting and reload it next time.

In any case, 2⁴⁸ is still a huge number of possibilities (some 280,000,000,000,000), more than adequate for a card game, more so when you come to a realisation that it's limiting shuffles rather than arrangements. Unless you're a serious statistician or cryptographer, what you have should be fine.

edited May 03 '13 at 15:32

answered May 03 '13 at 14:52

paxdiablo

854,327
234
1,573
1,953

`Presumably, after the deck is finished (poker hands, blackjack and so on), it will be in an indeterminate order` Probably Blackjack doesn't really fit in here, since the strategy is too fixed. Also I doubt about other games, since the rules pretty much ruled out most of the permutations. – zw324 May 03 '13 at 14:55
It won't be in an indeterminate order. It will be in an order you can actually manipulate in the previous game. – flup May 03 '13 at 14:57
1

How can `2^48` be enough, even for a card game, if it's only `0.000000000000000000000000000000000000000000000000000349%` of all possible shuffles? "Some" will never be reached. And due to implementation issues, you usually have to start with the same fixed arrangement every time. – caw May 03 '13 at 14:58
If every one follows exactly the same rules, then possibly the next starting point may be determinate, but that's pretty unlikely. – paxdiablo May 03 '13 at 15:00
@Marco, see my first few statements. You don't start with the same arrangement before each shuffle, therefore you're not limited to 2^48 arrangement. Granted there are only 2^48 possible _transitions_ but that's not arrangements. Also, are you _likely_ to play 280 trillion hands? :-) – paxdiablo May 03 '13 at 15:01
Does that make a difference if I play 10 hands or 280 trillion? I think: no. Because if there are some arrangements that will never be reached (there are vast numbers of them), maybe some with a "Royal Flush", I will never see them. This changes the game. No matter if I play 10 hands or 280 trillion. And whenever my program is restarted, I start with the same arrangement again, that is fixed in my code. – caw May 03 '13 at 15:09
1

@aMarco, my advice would be to fix that. Other options may be to introduce true randomness such as using timings from user input to morph the random number sequence (eg, calling rand every 0.1secs during idle time). But I really think it's over engineering, myself. The simple fix of not starting with the same arrangement will suffice. – paxdiablo May 03 '13 at 15:15
Although 48-bit is a huge number in absolute terms, what does that get you if it is an unbelievably small number in relative terms? Thus it should be no subjective question if one thinks this is enough or not. It should be obvious that this is far too less. – caw May 03 '13 at 15:38
But you would say that Java's `Random` or `SecureRandom` is the best RNG that could be used without losing efficiency, right? And just by shuffling the old (already shuffled) cards again and again, the problem of shuffle sequences that seem unrealistic should be solved, shouldn't it? – caw May 03 '13 at 16:31
1

@Marco, I'm not certain I'm getting my point across. The "small" number of outcomes for the random sequence is _irrelevant_ since you're not using it from a consistent starting arrangemement. Consider a (very bad) shuffle function that only swaps cards 1 and 2. If you shuffle, then play a game that leaves the cards in a different starting arrangement, that shuffle won't produce the same arrangement next time despite it only allowing 2^0 transitions. It's the intervening _game_ that provides extra randomness, and _all_ 52! arrangements are possible. – paxdiablo May 03 '13 at 21:33
Thank you, I think I got your point ;) But that does not only work if the previous game has left the cards in a new arrangement but also if you just shuffle the shuffled deck again for the next game, right? Because the arrangement is different in this case as well, and although you can only reach 2^48 or 2^160 transitions, you will ultimately be able to reach all 52! arrangements. – caw May 03 '13 at 22:38

zw324 · Answer 2 · 2013-05-03T15:13:42.440

2

Although you are using a SecureRandom, is still has a limited state. As long as that input seed has a smaller range than 52! it can not be completely random.

In fact, SHA1PRNG is 160 bit seeded, which means it is still not random enough. Follow this link, it has a solution years ago by using a third party library called UnCommons Math.

edited May 03 '13 at 15:13

answered May 03 '13 at 14:47

zw324

26,764
16
85
118

Okay, thank you! 160 bit is definitely far better than 48 bit, so that's a good first step. Where is the source for SHA1PRNG having 160 bit, apart from the page you linked to? – caw May 03 '13 at 15:12
Wiki has it: http://en.wikipedia.org/wiki/SHA-1. SHA-2 or 3 could also work according to Wikipedia. – zw324 May 03 '13 at 15:13
So "SHA2PRNG" would be enough with SHA-256 having enough bits to generate all possible shuffles. – caw May 03 '13 at 15:16
2

While it is a nice feeling if the seed space is as large as the amount of possible shuffles, the seed need not be as big as the problem space. It only needs to be big enough so that it cannot be cracked and the random numbers should be distributed evenly enough so that the hands are not predictable. It does not matter that you miss out on possible flushes, as long as you don't miss out on more flushes than non-flushes. – flup May 03 '13 at 16:10
Maybe you should also include the title to the link, so the reference can be better googled (if the URL resolves to 404). In other words, I suggest to replace *Follow this link* by something like *Read [New Adventures in Software » A Java Programmer’s Guide to Random Numbers, Part 3: Seeding](http://blog.uncommons.org/2008/04/10/a-java-programmers-guide-to-random-numbers-part-3-seeding/)* – Wolf Nov 23 '14 at 14:12

score 1 · Answer 3 · answered May 03 '13 at 15:23

If you want real randomness, you could just skip pseudo random generators and go for something better like random numbers generated from athmospheric noise.

random.org offers an API to integrate random numbers generated that way into your own software.

score 0 · Answer 4 · answered May 03 '13 at 14:53

0

Stealing an answer from the article you link:

START WITH FRESH DECK
GET RANDOM SEED
FOR CT = 1, WHILE CT <= 52, DO
X = RANDOM NUMBER BETWEEN CT AND 52 INCLUSIVE
SWAP DECK[CT] WITH DECK[X]

The random number generator should be good and use a 64 bit seed that you pick unpredictably, preferably using hardware.

answered May 03 '13 at 14:53

flup

26,937
7
52
74

The shuffling algorithm is not the problem. Java's `Collections.shuffle(...)` should use the Fisher-Yates shuffle which is adequate. But the PRNG and its seed is the crucial point. – caw May 03 '13 at 14:54
1

Agreed, the key is in the random number generation. (Though the article describes how folks managed to get the shuffling wrong.) – flup May 03 '13 at 14:58

score 0 · Answer 5 · edited Nov 24 '14 at 13:42

How to really shuffle a deck?

There are several shuffling techniques.

Either (Stripping/Overhand):

Cut the deck in two
    Add a small (pseudorandom) amount of one half to the front of the front of the other
    Add a small (pseudorandom) amount of one half to the front of the back of the other
Do this until one hand is empty
Repeat

Or (Riffle):

Cut the deck in two
    Set down a small (pseudorandom) portion of one half
    Set down a small (pseudorandom) portion of the other
Do this until both hands are empty, and you have a new deck
Repeat

And there are more on top of this, as detailed in my link above.

Regardless, there are so many combinations that even the perfect shuffling algorithm would take a machine exploring 2*10^50 unique permutations per second to finish exploring every permutation in the time the universe has existed. Modern computers are only predicted to hit 1 ExaFLOPs (1*10^18 floating point operations per second) by 2019.

No human shuffler will explore that range of possibilities either, and you are, I believe (at the most basic level) simulating a human shuffling, correct? Would you find it likely that a croupier could shuffle an incrementally ordered deck into decreasing order in one shuffle? To split the deck with even ranks before odd, in one shuffle?

I don't find it unacceptable to limit yourself to a (albeit extremely) small subsection of that phase space (2^48 possible random numbers) in each shuffle, so long as you don't continuously seed the same way etc.

There are exactly 52 factorial (expressed in shorthand as 52!) possible orderings of the cards in a 52-card deck. This is approximately 8×10⁶⁷ possible orderings or specifically: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.
The magnitude of this number means that it is exceedingly improbable that two randomly selected, truly randomized decks, will ever, even in the history of the Universe, be the same. However, while the exact sequence of all cards in a randomized deck is unpredictable, it may be possible to make some probabilistic predictions about a deck that is not sufficiently randomized.
~Wikipedia

Also, it's worth noting that Bayer & Diaconis in 1992 proved it only takes 7 good shuffles to properly randomize a deck, here is the section on it from wikipedia which has plenty links to papers discussing this.

How to really shuffle a deck of cards

5 Answers5

Linked