Shuffling

December 3, 2007

Pop quiz, hotshot. How would you write code to shuffle a deck of cards?

I was thinking about this after reading Mike's card-shuffling algorithm woes:

Here's where the non-CS mind comes into play. My first thought was to generate an unshuffled deck as an array-like structure -- all cards in order by suit. Then I'd create a second array-like structure. I'd walk through each card in the unshuffled deck, pick a random number, and insert the card at the randomly selected spot in the second array. If the randomly chosen position in the second array was already occupied, I'd choose another random number, see if it was used, and so on until the random selection happened to land on a free spot. I'll call this the Random Insert approach.

It seemed an odd approach to me, but unlike Mike, I have the dubious benefit of a programming background. I went immediately for my old friend, the loop. Let's assume we have an array with 52 members representing the 52 cards in the deck.

var rand = new Random();
for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    int temp = cards[i];
    cards[i] = cards[n];
    cards[n] = temp;
}

So we loop through the deck, switching each card with another card from a random position in the deck. Seems straightforward enough, although I do wish there was a built in Swap command in the C# language to simplify the code a bit. It's eerily similar to the Knuth or Fisher-Yates shuffle, which doesn't mean I'm particularly smart, but that shuffling is an easily solved problem.

Or is it? This looks correct; there's nothing obviously wrong here. But there are two problems with this code. Can you see them?

The first problem is right here:

new Random();

Computers are lousy random number generators. Any shuffling you do, whatever the algorithm, will only be as good as your random number generator. So if you're running, say, an online casino, you need to be very careful when you start throwing around the word "Random" in your code. If you aren't careful, there will be.. problems.

The flaw exists in the card shuffling algorithm used to generate each deck. Ironically, the code was publicly displayed at www.planetpoker.com/ppfaq.htm with the idea of showing how fair the game is to interested players (the relevant question has since been removed). In the code, a call to randomize() is included to produce a random deck before each deck is generated. The implementation, built with Delphi 4 (a Pascal IDE), seeds the random number generator with the number of milliseconds since midnight according to the system clock. That means the output of the random number generator is easily predicted. A predictable "random number generator" is a very serious security problem.

By synchronizing our clock with the clock on the online casino and hitting the "shuffle" button, our program can calculate the exact shuffle. That means we know all the cards that have yet to appear, everyone's hand, and who will win. The screen shot below shows the information displayed by our program in realtime during an actual game. Our program knows what cards are to appear in advance, before they are revealed by the online game.

To be fair, this was 1999. I'd assume most online casinos have hired competent cryptographers and statisticians by now. With the ever looming specter of insider cheating and poker bots, they'd be fools not to.

The second problem with this code is that it's too complicated. Eric "purplicious" Lippert explains why, in his own inimitable way:

The standard way of implementing this algorithm is: associate each card with a random real number between 0.0 and 1.0. Sort the list based on its associated number. That's O(n log n) and has no bias.

As it turns out, the easiest way to implement a shuffle is by sorting. It's not exactly faster, as the typical sort is O(n log n) compared to the O(n) of the Knuth Fisher-Yates shuffle algorithm. We'll just sort by a random number-- in this case, a GUID.

var cards = Enumerable.Range(0, 51);
var shuffledcards = cards.OrderBy(a => Guid.NewGuid());

So we can ultimately implement a secure, unbiased shuffle as a one-liner in a modern programming language.

Which proves.. well, nothing, I suppose, but like so many other programming problems, there are a lot of ways to get shuffling wrong if you're not careful.