science of board games

There has been a lot of hubbub about shuffling algorithms the past few weeks. This post on Coding Horror is one of my favorites. He does not list my own naïve sorting mechanism, which does not use any swapping (written in Ruby):

src = [1,2,3,4,5]
dest = []
while src.length > 0 do
	dest += [src.delete_at(rand(src.length))]
end

Swapping just irritates me. Regardless, this seems to have nearly identical randomness as the Knuth/Fisher-Yates, Shuffle (in that it generates exactly as many permutations as there can be), shown here:

src = [1,2,3,4,5]
(src.length-1).downto(0) { |i|
	n = rand(i+1)
	src[i],src[n] = src[n],src[i]
}

Some quick test runs have verified to my liking that both my algorithm and KFY produce about the same levels of randomness of shuffles. KFY just modifies the array in place, while mine does so in a copy. I don't immediately see that KFY works (though it does), while my algorithm makes a little more intuitive sense to me.

In general, computer shuffles are notoriously difficult to get correct. One major problem stems from the fact that, for a deck of 52 cards, you have 52! = 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 different ways of arranging the cards. That's a big number. A standard random number generator has only about 32-bits of precision, for a maximum of 4,294,967,296 different shuffles it can produce.

There's a huge difference in those two numbers. According to my back-of-the-envelope calculations, you need at least a 226-bit random number generator to hit all of the 52! permutations of a deck. But then you run into a problem, as illustrated in the article cited above: unless you hit is *just* right, you may be favoritizing some shuffles more than others.

It's also really hard to notice that you are doing it, too. Once you have a deck of 13 cards, the number of permutations exceeds 6 billion, meaning merely storing counts becomes nearly impossible, let alone the computation time to generate these counts to a statistically meaningful amount.

The best thing you can do is to use a very large, very good random number generator, preferably with real random numbers. Barring that, follow guidance set for by Knuth (and other brilliant folks, too) when designing your hardcore shuffling algorithms.