Card games have been mankind's favorite passtime long before the era of computers. Many, perhaps most, popular card games have been programmed into computer software.

Every card game I have ever seen starts by shuffling the cards. The purpose of the shuffling is to rearrange the cards in a more-or-less random order.

Surprisingly, despite the popularity of card games among computer users, just about any programming textbook teaches several algorithms on how to sort a pack of cards but most offer no clue on how to shuffle it.

In this node I will present my own card-shuffling algorithm. I also hope others will present other card-shuffling algorithms.

Preliminaries

First of all, to use my algorithm we need to represent the cards as an integer array of size n, where n is the total number of cards.

For example, a typical solitaire game uses one deck of cards consisting of four suits each containing 13 cards (from ace to king). In this case, n is equal to 4 times 13, or 52.

A different game can use two decks, plus four jokers, for an n of 108, etc.

Whatever the size of n, we will have n cards which we will refer to as card[0] ... card[n-1]. Each card has a unique value in the [0...n-1] range.

It is quite simple to convert the integer value of a card into its suit and face value. For example, with n = 52 we have four suits (0...3), so any card[i] is inside the suit card[i] / 13, while its face value is card[i] MOD 13, where MOD designates modulo division.

The Algorithm

Step 1: Initialize the cards. For each i in the [0...n-1] range, set card[i] = i.

Step 2 (optional): Seed the random number generator.

Step 3: Let i = 0.

Step 4: Let j = random_number MOD n.

Step 5: Exchange the values of card[i] and card[j].

Step 6: Let i = i + 1. If i is less than n, go to step 4.

Sample Source Code

Here is a sample C function implementing the algorithm:

void shuffle(int *card, int n) {
	int i, j, k;

	for (i = 0; i < n; i++)
		card[i] = i;

	for (i = 0; i < n; i++) {
		j = rand() % n;
		k = card[i];
		card[i] = card[j];
		card[j] = k;
	}
}
To test whether the preceding algorithm (or for that matter any card shuffling algorithm) is truly random you should perform a few tests:
  1. Over a number of shufflings (100,000 lets say) what is the percentage of a particular card appearing first?
  2. From the same pool, what is the percentage of a particular suit appearing first?
  3. What is the percentage of particular rank appearing first?

If over significantly large number of games the results approach the mathetmatically predicted ones (that is 1/52 is a chance of first draw being ace of diamonds, etc) then we can safely conclude that it's really random.

Note that the algorithm should also work for multiple card deck games.
Often, a bigger issue in practice than "Is my card shuffling algorithm statistically random?" is simply "Is my deck space big enough?", which is basically a test of your random seeding.

You only have as many shufflings as you have random seeds. There are 52! unique deck shufflings, which is around 2220. Many random number generators accept only a 32-bit seed, and we note that 2220 is a much bigger number than 232 (2188 times bigger, in fact).

The real world implications of this is that in cases where you need a random shufflin, you may be vulnerable to brute force attacks. In late 1999 it was discovered that three online (live money) poker sites had exactly this problem, and a sample attack program was created that would take the known cards and quickly narrow down the possible decks until the player had perfect information about the cards the other players held and the cards to come.

Obviously, not every program needs 220 bits of randomness in their shuffler. A Texas Hold-Em program with a statistically perfect shuffling algorithm that supported 10 players would need about 120 bits of randomness (the exact number is log base 2 of (52!/27!)).

Anyway, the pont being that when you are evaluating a card shuffling algorithm, the right choice depends on the application, and when you have a deck space that is 52! points long, typical seed limitations are pretty puny.

Log in or register to write something here or to contact authors.