programming and human factors
by Jeff Atwood
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.
I had to randomly shuffle some data once for machine learning testing.
That's when I discovered the STL's random_shuffle method. Works pretty well.
Tom on December 4, 2007 2:14 AMIn Java:
java.util.Collections.shuffle(cardList);
http://java.sun.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List)
Arend on December 4, 2007 2:23 AMNo Swap built in? Don't cry, create! :-)
Seems like an case for extension methods:
public static void SwapT(this T[] vaData, int vnJ, int vnI)
{
T lnTemp = vaData[vnJ];
vaData[vnJ] = vaData[vnI];
vaData[vnI] = lnTemp;
}
...
cards.Swap(i, n);
Shuffling 52 cards randomly requires quite a specialised random number generator, whether you use the Fisher-Yates method or the sorting method.
There are 52! (52 factorial) ways of arranging the cards, and 52! is a very large number - bigger than 2^225. Any random number generator used to generate fair shuffles must thus have an internal state of at least 226 bits to randomly generate shuffles. If it only has 32 bits (or even 128 bits), you can only hope to generate a minute fraction of the possible shuffles.
I'm not sure what properties Guid.NewGuid() has, but since there are only 2^122 GUIDs, it seems unlikely that it has more than 225 bits of internal state - can someone confirm or refute this?
Chris Johnson on December 4, 2007 2:29 AMA really good random generator has NO state.
Or does have radioactive decay any state?
Only pseudo-generators need to mantain a state.
In most implementations, however, random_shuffle uses the srand() seed, unless you provide it a RNG object of your own. And in both of these cases, your randomizer is only as good as the seed you give it. Too many people still use time() for a seed, which renders random_shuffle as useless as the randomize() example above.
Camille on December 4, 2007 2:33 AM"I'd assume most online casinos have hired competent cryptographers and statisticians by now"
Err ... excuse me ? You "assume" that a given programming problem is solved competently by expert programmers ... and "most" ? Do you have ANY actual real life experience (I know you do, just saying) ?
J. Stoever on December 4, 2007 2:47 AMNo matter what algorithm you use a very important thing to keep in mind is to keep that implementation abstracted away. So, no matter how you do it, the programmer should do nothing more than call a shuffle function (that doesn't allude to a specific algorithm).
In Python:
import random
shuffled_deck = random.shuffle(range(52))
Fair point - if you have random numbers straight from radioactive decay then you're sorted. Most applications can't justify the hardware expense though.
Chris Johnson on December 4, 2007 2:49 AMI was unfamiliar with the term GUID so I looked it up on wikipedia, but even there I didn't find any reason why it should be more random than a randomly generated number. For all I know, the system could just count upwards from 000....0001 for the GUID, or am I wrong?
Care to elaborate?
Winsmith on December 4, 2007 2:56 AM"I'd assume most online casinos have hired competent cryptographers and statisticians by now"
I assume that because there's a *lot* of money at stake for online casinos, unlike most programming jobs. And not just the "company's" money, which is somewhat disposable, but real people who get quite upset when you steal it from them.
Jeff Atwood on December 4, 2007 2:57 AMOh please, when has involvement of money ever made programs better ?
J. Stoever on December 4, 2007 3:01 AMSame Ruby version I wrote at the original article:
cards.sort_by { rand }
Nice and simple.
I am surprised that many developers don't know that the pseudo random number generators that come with most programming languages - especially with the popular ones are weak. For the needs of cryptography you need to roll your own. It would be a good idea to get a good source of randomness - radioactive decay or some similar method is a good source but a bit non-practical unless you have a huge budget. Some encryption software make you type random characters or move a mouse on the screen making a human source of randomness. Again not perfect but better than nothing. This is a whole long topic on which a lot of computer science papers are based.
Tom on December 4, 2007 3:05 AMreminds me of a project I was asked to write for a job interview. It was actually, to simulate a slot machine.
I was the only one to simulate machine behavior; everyone else just randomized.
Same sort of thing here... you're just randomizing a list/array/whatever. it doesn't simulate real world shuffling. That may be better than real world, or maybe not.
/just sayin'
josh on December 4, 2007 3:06 AMI don't think the sorting approach is necessarily better than the swapping approach! It's more elegant but less performant (which matters for many applications).
You're still depending on a pseudo-random generator (only new it's called Guid not Random) so problem #1 is still there. Problem #2 is mitigated, but the performance is O(n log(n)) vs. O(n) with the swapping approach.
Shu Wu on December 4, 2007 3:13 AMI wrote a program for a trading card game that allows the user to "simulate" their opening hand for the deck they created. While it isn't as critical to get it purely randomized, using the seeded random generator to grab a card from the deck and put it in a new one works well.
But the really interesting thing is that when kids (and adults) play this game in real life, they never shuffle like this. Most of the time, they like to "pile shuffle". Assuming you're using 8 "piles" you take the top card of the deck and put it in pile 1, the second in pile 2, and so on. When you go through all your cards (minimum of 40, no maximum) you then grab your piles at random and you have your deck again.
And there are other techniques too. There's your "rifle" shuffle where you split the deck in half and fan the cards together. There's the "clump" shuffle where you grab a clump of cards from the middle to back of your deck and bring them to the front.
I'm still working on making various shuffle algorithms into the program, but to some extent, the players want the deck randomized, but not too randomized, because after a round they have some of their better cards clumped together, and they want to keep it that way.
I wonder if casinos would ever use various styles in their shuffler, since most of it is not done manually anymore.
Sean Patterson on December 4, 2007 3:14 AMIs a hand-shuffled and cut deck of actual playing cards really randomly sorted?
PJ Doland on December 4, 2007 3:28 AMNo swap in C++? What about std::swap in algorithm?
Puzzler183 on December 4, 2007 3:30 AM... in algorithm?
Puzzler183 on December 4, 2007 3:31 AMping could be used as a random number, especially if you have many clients connected to the server (as online poker games probably do). Just collect the ping from all the players a few times every game, hash it to produce a standard string/byte array. The ping is "random" because it is influenced by a third party (the network, other users, other routers) which cannot be predicted.
Ihoss on December 4, 2007 3:36 AMIs a hand-shuffled and cut deck of actual playing cards really randomly sorted?
In my opinion, this is because physical methods can only *approximate* truly random shuffling. Computers, with clever random functions, can get much closer to true randomness than a human ever could.
Kind of ironic, really, since computers are about as deterministic as you can get, yet when properly programmed they can do much better than a human.
I'm not sure I buy the argument that we should duplicate inferior physical shuffling, because shuffling is somehow *intended* to be non-random. At least not in a typical Casino gameplay environment.
Jeff Atwood on December 4, 2007 3:39 AMI definitely find that modeling real shuffling is more fun than actually randomizing the deck. My model for a bridge shuffle is:
1) Simulate imperfect cut
[set partition of array +/- X of center]
2) Two stacks. A force is applied on the bottom card of each stack proportional to the number of cards left in that stack (since the cards are bent, and can be treated roughly as springs). Probability comes from the proportion of these forces.
There are so many fun parameters here. Cut error, card flexibility (per-card?!), perhaps the shuffler's dominant hand influences next-card force?
Impractical, but a lot of fun :D Any other ideas for parameters?
Mike Lundy on December 4, 2007 3:41 AMIs that algorithm reliable? It depends on the sorting algorithm to call the key function once for each element and cache the key. I don't see anything in the OrderBy docs that state that it does this. It could potentially call the key function multiple times resulting in the same element receiving different GUIDs and thus a non-deterministic end point.
So far the only language I've seen with shuffling as a built-in array method is SystemVerilog (hardware programming/verification language).
engtech on December 4, 2007 3:46 AMThank you for not posting suck this time.
m on December 4, 2007 3:49 AMI use my own random numbers code for my C/C++ programs, to have the same behavior from the same seed everywhere. And also to have some guaranties :D
A pseudo-random number generator with a long period (2^219937 #8722; 1), fast (bits manipulation only), and good statistical properties is the Mersenne Twister. There is a special SIMD version of it, and it has some proof behind it. It simply rocks for simulations.
But the Mersenne Twister is also pretty easy to predict, just 634 outputs are neaded to predict it. The Blum Blum Shub generator is very hard to predict (I mean, you need a computer that not exists) while having good statistical properties. It uses product of big prime numbers so it also slow, that is not very important for a card game without AI. Blum Blum Shub, beside having a cool name, should be perfect for a poker game.
Alex on December 4, 2007 3:53 AMjosh and others: Trefethen, L N Trefethen, L M, "How Many Shuffles to Randomise a Deck of Cards?", Proceedings of the Royal Society London, A 456, 2561 - 2568 (2000). The paper describes their model of "real shuffling."
Y'all should be careful about calling system or standard library "shuffle" routines unless you know how good the PRNG behind them is. Another good question is whether the PRNG is thread-safe (srand() / rand() isn't).
There's some interesting work out there about how to seed PRNGs from stock hardware by looking at uninitialized memory. You can also fetch "random" bits from /dev/random or /dev/urandom. Does Windows have something like this?
Mark Hoemmen on December 4, 2007 3:54 AMAlex -- if you're using a PRNG for crypto or otherwise want unpredictable outputs, you should run it through a one-way function of some kind. The Mersenne Twister was designed specifically to improve the accuracy of Monte Carlo simulations; it's not at all meant for crypto or secure applications.
Incidentally, I've written a parallel PRNG tutorial at:
http://www.cs.berkeley.edu/~mhoemmen/cs194/Tutorials/prng.pdf
Mark Hoemmen on December 4, 2007 3:57 AMHow about some C++:
random_shuffle(cards.begin(),cards.end());
And if we want to use some serious randomness:
int rand_gen(int max, int seed=0)
{
boost::mt19937 mersenne_twister(seed);//uniform distribution
//in 623 dimensions
return mersenne_twister()%max;
}
random_shuffle(v.begin(),v.end(), rand_gen);
//or with a seed
boost::function int (int) f = bind(rand_gen,_1, seedval);
random_shuffle(v.begin(),v.end(), f);
I would not use GUIDs in your shuffling algorithm. Older GUID generation algorithms (such as found in VS6) actually encoded the current time as the first part of the GUID and the MAC address of the computer's network card in the last part of the GUID. The newer algorithm in Guid.NewGuid() eventually makes a Win32 call to UuidCreate, which generates a random GUID, though nothing in the docs says that it uses a non-pseudo random number generator. So I suspect that Guid.NewGuid() is no better than the pseudo random number generators that you're recommending against. If you're working in .NET, you want to use the RNGCryptoServiceProvider (http://msdn2.microsoft.com/en-us/library/system.security.cryptography.rngcryptoserviceprovider.aspx), which generates cryptographic quality random numbers.
James Kovacs on December 4, 2007 4:01 AM@Mark Hoemmen : You should look at the wikipedia 'Blum Blum Shub' entry. It uses a well-known one way function : big prime numbers products. I cited it because of the bad security inherent to the Mersenne Twister ;)
Alex on December 4, 2007 4:04 AMMore evidence that physical shuffling is a pretty poor approximation of randomness:
http://www.flatrock.org.nz/topics/art_of_playing_cards/how_to_win_at_poker.htm
--
Two mathematicians hit the headlines in 1990 when they claimed that it took seven shuffles to make a pack of cards fully random, with no vestige of its original card order. Now comes a challenge to that claim. Five shuffles will almost do the job of randomisation, and six will make it certain, according to a paper in the Proceedings of the Royal Society*.
It all depends on how you define "random", say Nick Trefethen and Lloyd Trefethen, respectively of Oxford University, UK, and Tufts University in Massachusetts in the US.
The magic number of seven shuffles was proposed by David Bayer and Persi Diaconis in the USA, who considered how shuffling affected a quantity called the "total variation norm." This is a complicated measure of how effectively an ingenious gambler could be expected to win bets that the arrangement of cards in the deck was not completely arbitrary.
Bayer and Diaconis chose to define randomness in this way because they were interested in how shuffling might affect play in casinos. Some professional card players will go to any lengths to exploit an element of non-randomness in a card deck. Most casino dealers shuffle between two and four times - which, according to Bayer and Diaconis, was nowhere near enough to lose all trace of the starting configuration of the pack. In fact, they claimed that there is virtually no true randomisation, as they defined it, until the 5th shuffle. Only after the 7th, they said, does their measure of "orderliness" of the deck fall below half the initial value - enough to consider the pack well mixed.
Diaconis, himself a card magician, realised that astute card players could capitalise on this. He said that in his experience, shuffling seven times was almost unheard of in casinos. And he once spotted how bridge players in a New York club could anticipate the order of a deck shuffled four times between each hand.
--
First off, you could easily make a generic swap method if you wanted (I don't think there is one in .Net already; they do use make one in the documentation as an example of a generic method)
Second, you could use RNGCryptoServiceProvider to get much better random numbers. Random is made to be fast and easy; RNGCryptoServiceProvider is made to be secure.
Allied on December 4, 2007 4:14 AMAre you showing off your lambda expressions knowledge? :P
Andrei Rinea on December 4, 2007 4:15 AM"although I do wish there was a built in Swap command in the C# language to simplify the code a bit"
http://icr.vox.com/library/post/swapping-variables-in-c.html
[ICR] on December 4, 2007 4:21 AMWhy even bother to shuffle the array? It's probably easier and simpler to put the cards into a collection and then randomly pick one to remove based on the size of the Collection.
[code]
int pos;
String card;
ListString d = newDeck();
while(!d.isEmpty()) {
pos = new Double(Math.random() * d.size()).intValue();
card = d.get(pos);
d.remove(pos);
}
[/code]
Swap an integer, the XOR way:
ValueA ^= ValueB;
ValueB ^= ValueA;
ValueA ^= ValueB;
http://en.wikipedia.org/wiki/XOR_swap_algorithm
Shawn Poulson on December 4, 2007 4:33 AM"Why even bother to shuffle the array? It's probably easier and simpler to put the cards into a collection and then randomly pick one to remove based on the size of the Collection."
I've used a similar approach in the past, though I seem to remember abandoning it for some reason. I can't quite remember why though.
[ICR] on December 4, 2007 4:33 AMI'm reminded of one of Knuth's Exercises: "Look at the subroutine library of each computer installation in your organization, and replace the random number generators by good ones. Try to avoid being too shocked at what you find."
jpsa on December 4, 2007 4:35 AMThank you for not posting suck this time.
No-- thank you!
Jeff Atwood on December 4, 2007 4:45 AM@Alex -- duly noted ;-) though to the Mersenne Twister's credit, the author specifically indicated that MT was _not_ crypto-secure. The author's implementation of MT is a chunk of highly optimized C code and is likely to be faster than good crypto-secure PRNGs, though I haven't run benchmarks. MT grew out of the need for accurate Monte Carlo simulations.
Mark Hoemmen on December 4, 2007 4:46 AM""Why even bother to shuffle the array? It's probably easier and simpler to put the cards into a collection and then randomly pick one to remove based on the size of the Collection."
I've used a similar approach in the past, though I seem to remember abandoning it for some reason. I can't quite remember why though."
It's more security conscience as well. Assuming the random number generator is good the only thing you can predict, via memory inspection, is what cards are left. As we all know people count cards in the casinos as it is, so it's not like that'll be giving anything away.
Mike on December 4, 2007 4:46 AM"var cards = Enumerable.Range(0, 51);
var shuffledcards = cards.OrderBy(a = Guid.NewGuid());"
How does
var shuffledcards = orderby(a=Guid.NewGuid())
work?
I wouldn't think you could sort by a guid considering its not part of int.
Brian on December 4, 2007 4:56 AMYears ago I was tasked with creating a card game, and given instructions to make it as realistic as possible, as it would be used to simulate actual card playing. At first, I thought about a true random shuffle, then I sat at my desk with a pack of cards, and actually shuffled, and I noticed that none of my shuffling was really very random at all.
The two main methods I was using were cutting the deck, and riffle shuffles. I decided to implement these, along with a few other shuffle methods directly in the code, and then call random shuffle methods, a random number of times. For example, you might have a cut called with an offset of 30, which would yield a top pile of 22 cards, and a bottom pile of 30, then the top pile would be moved to the bottom, followed by a riffle shuffle with an offset of 25, where there were a pile of 25 cards and a pile of 27, which were then combined one after another, with some weighting to determine the likelihood of two or more cards being grouped, followed by another cut.
In the end, the algorithm gave a more natural shuffle so to speak, and was much closer to the results of a human physically shuffling the deck. Given humanities ability for complex subconscious pattern recognition, it wouldn't surprise me at all if normal nonrandom shuffling behavior affects poker betting, on and offline.
jcnnghm on December 4, 2007 5:04 AMThis reminds me of a blackjack program on the VIC20 that got much slower towards the end of the pack because it was looking for a card it had not already used.
Speeking of seeding with milliseconds, even if you have your computer clock set at the same time precisely to the millisecond, how do you know exactly when the random numbers are being generated?
Those pesky preemptive windows messages also get in the way and disrupt the timing.
Andrew on December 4, 2007 5:31 AMThere's a third problem with the first method, and that's got to do with the probability actually not equaling 1/count after you start choosing new ones. I can't remember exactly, but I recall doing something quite similiar in school.
TraumaPony on December 4, 2007 5:46 AM@Mike Random removal from a mutable array is the same approach I used last time, and the same approach I'll use next time, unless someone shows me why it's wrong.
Mike Lee on December 4, 2007 6:16 AM@Shawn Poulson
Swap an integer, the XOR way:
Cute, but that isn't as efficient as using a temp variable. Any optimizing compiler would locate t in a CPU register, using no actual memory (if we use integers). The xor method would move both variables into registers first before being able to operate on them.
Bill on December 4, 2007 6:25 AM"Speeking of seeding with milliseconds, even if you have your computer clock set at the same time precisely to the millisecond, how do you know exactly when the random numbers are being generated?"
If you know roughly the time the RNG was seeded and the two cards you were dealt as well as the cards of the flop the cheat program could check a range of seed times until it gets the same cards. Looking at the screenshot on the linked page it seems that is exactly what is happening.
Jeff: Thanks for the interesting post!
unthinkableMayhem on December 4, 2007 6:31 AMIn Ruby:
(1..52).sort_by { rand }
True random number generators are pretty easy. You don't need nuclear decay. Actual random number generators are pretty cheap, and I bet must gambling sites have them. A DIY one is also easy. Plug a microphone into your sound card, put it next to the power supply fan, and read the sound coming in. Filter out all but the very highest frequency components, and you have a pretty strong source of randomness.
FraserOrr on December 4, 2007 7:41 AMSELECT CardNumber FROM dbo.Cards ORDER BY NEWID()
Dustin on December 4, 2007 7:52 AMThis reminds me of how I was taught sorting algorithms in high school and a paper I wrote later. My teacher used a deck of cards to teach me the basic sorts (Shell, Bubble, Quick, Insertion etc. etc.) In the paper I wrote I included an algorithm that was the least efficient (in terms of lines processed to achieve a sorted array).
The algorithm was the equivalent of throwing a pack of cards in the air and checking if it is sorted. If not, try it again. I used the real number between 0.0 and 1.0 approach in the algorithm.
I wish I could include the algorithm and the results here but I am currently at work.
Albert on December 4, 2007 8:05 AMWhat does a GUID get you that, say, generating a number based on a good /dev/rand implementation not get? GUIDs are designed to be unique globally -- across machines, etc., etc., which means that many implementations have a lot of redundancy (aka "waste") when used as random seeds on a local box.
I do need to generate a number from a field larger than 52!, but that's still just generating a number, so why not just do that?
One of my biggest beefs in software development is sandblasting the salt off a soup cracker: do what you need to do, and no more.
Robert Fischer on December 4, 2007 8:16 AMNothing is ever truly random, just confusing enough to make a person think it is.
Mattkins on December 4, 2007 8:16 AMCould you discuss detail as to why generating a guid is more "random" than calling random? And, is that REALLY a one-liner? It doesn't look like you're storing the GUID's anywhere- how is it comparing against the GUID's already representing other cards elsewhere in the deck?
Also, @Shawn: Swapping values "the XOR way" sets both your ints to 0 if they have the same value:D I read an article once citing that snippet as an example of "the dangers of clever code"
@ Chris Johnson
RE: There are 52! ways of arranging the cards [...] any random number generator [...] must thus have an internal state of at least 226 bits
I tend to agree, though talking about the internals of a PRNG to determine it's suitability to a specific fixed task seems, to me, to be missing a crucial point. So many programmers treat PRNGs as something to initialise once and then use to get a potentially infinite number of random bits out of. This is wrong. A PRNG has INPUTS as well as an output. You should be constantly feeding the inputs with anything even remotely random that you can lay your grubby mitts on... keystroke timings, hard-disk response times, bytes received at network layer, CPU cycle count, ring-0 context times, etc. Everything. Anything. All the time.
The Fortuna PRNG by Bruce Schneier Niels Ferguson might have potentially 10s of thousands of bits in the entropy accumulators - from which it can generate an output stream. It is really an impressive piece of work and given enough diverse inputs rapidly achieves immunity from poisoning.
Your comment about O(n) for Knuth Fisher-Yates shuffle algorithm is ignoring a subtle detail. Since there are n! different permutations and representing n! takes log(n!) = O(nlog(n)) bits. So sampling *uniformly* from all permutations will take at least time O(nlog(n)). Of course we can assume that n fits into a 32 bit number and we're fine, but for ginormous numbers this would become an issue.
Pall Melsted on December 4, 2007 8:42 AM@Andrew R
RE: You should be constantly feeding the inputs with anything even remotely random that you can lay your grubby mitts on... keystroke timings, hard-disk response times, bytes received at network layer, CPU cycle count, ring-0 context times, etc. Everything. Anything. All the time.
I believe there are ways in which this can bite you. Most of us are probably ill-equipped to even measure the true randomness of any such source of entropy, for one thing. I certainly am.
There are -- as you point out -- expert-designed schemes for entropy distillation and accumulation. When true randomness is important, perhaps we should use those systems, and not just "roll our own."
Western Infidels on December 4, 2007 9:55 AMJeff, I actually found your initial method to be "weird" - so to speak. I've always used the "assign a random id and sort" method myself, can't even remember if I saw it online or came up with it; but even if it weren't for the big-O, it's still the "logical" way of doing it.
Correct me if I'm wrong here: When you replace each card with a randomly selected card, you're going to swap some cards around twice and some cards around once; because as you move along the deck, you can end up swapping each card with one either above or below it. Then when you get to _that_ card, you swap it again, and so on and so forth.
This is closest to the behavior of a "manual" shuffle.
But when you assign a random integer to each and sort by it, you're guaranteeing that all cards have the same probability of being shuffled.
Both end-results are as "random" as each other, but the second method gets you a more "equal" randomness - which is something that counts in cryptography.
Computer Guru on December 4, 2007 10:32 AMAlthough you've correctly identified some of the things a secure card shuffling algorithm needs to do, you've missed a lot of others. Chris Johnson brought up one issue in his comment above, and you can read some more at http://en.wikipedia.org/wiki/Shuffling#Implementation_of_shuffling_algorithms
Hey, where are the test results? You claim that your algorithm is a "secure, unbiased" shuffle, but is it? Is it even better than the built-in RNG? Please run your shuffling algorithm through a test battery like NIST or TestU01 and let us know how that goes.
http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
[Also: When n=52, O(n) notation doesn't mean squat. For small n, an O(n log n) algorithm can easily beat an O(n) algorithm depending on the constants involved. O(n) analysis generally assumes that memory access is O(1) and arithmetic operations are all equally fast, but we all know neither of those assumptions is true. At modern CPU speeds, memory access patterns and CPU instruction scheduling dominate the cost of many algorithms -- especially RNGs.]
You should see what pokerstars.com writes on its website about its shuffle. For the random number generator, it supposedly uses, among other things, mouse movements of the users!
Greg
Greg Magarshak on December 4, 2007 11:07 AMFunnily enough, I wrote a quick implementation of Knuth’s shuffle in Haskell a couple of days ago; http://hpaste.org/4216#a1.
Porges on December 4, 2007 11:12 AMAll right, everyone who didn't mention TAOCP Vol-2, hand in your geek cards right now, you're all banished for the next 12 months.
For the newbies out there that are scratching their heads asking "what the fuck is this TAOCP thingie, just google it."
My 1st game was a Tetris clone. I made it in Turbo Pascal 3.0!
I could not find a random() function so i made my own by using a pattern of digits returned from logarithmic functions.
(*) If you want secure pseudo random numbers I think its a really BAD idea to use known methods.
Ok, so PokerStars has done it's homework. Any more good examples?
Good to know that the shuffles are properly done when you feel like playing Poker.
djchester on December 5, 2007 1:31 AMJeff, I'm disappointed. There are two things I completely disagree with here.
Calling up a new GUID and using it to shuffle is too simplistic and abstracted. You're asking for someone to come along and spend a some time reverse engineering their way back to a point where they can find a shuffle through a rainbow-like attack. Where's the 'random' in GUID creation? How do you know it's random enough? GUID's aren't always perfect, and it could be possible to track them down if you were to use a static function like that. This is a problem where even 'theoretically possible' is not good enough. Ergo a custom built algorithm with a phenomenal amount of randomness is the only worthwhile and fair solution.
The more important thing you forgot is that as soon as you put money on a table, it belongs to the casino. A better encryption or shuffling algorithm is only advertising and customer retention. The goal of any casino is to pull as much money as possible with the odds on its side onto the table, (or pull out a percentage) then keep the players playing as long as possible. There is inefficiency in the system because the system is designed by those creating the inefficiency.
A casino programmer's job is to bring in as many players as possible and make standard distribution at least APPEAR to apply so you can continue siphoning money from more and more people... I mentioned fair solutions, but it may not be in the casino's best interest to have a fair solution all the time.
Dylan Brams on December 5, 2007 1:47 AMI do not think that shuffling is an "easy solved problem", especially since the shuffle algorithm you describe is very easy to get wrong. In fact, almost all swap-based algorithms are wrong.
You already made a mistake in your textual description: "So we loop through the deck, switching each card with another card from a random position in the deck". That is wrong (doing just that would produce a biased shuffle) and it is also not what you are doing: you are not switching with any random card, but only with a random card that hasn't been swapped yet!
The subtle difference makes the difference between a biased and an unbiased algorithm (assuming the RNG is fair). Your textual description does not match your code, which is why the code is correct while the description is wrong.
A better way to describe the algorithm that you actually implemented (that is probably easier to understand and analyze as well) would be:
- At the start the shuffled deck is empty, and all (unshuffled) cards are in a pile.
- Remove a card from the pile at random, and add it at the end of the deck.
- Repeat until the pile is empty.
The deck is now shuffled without bias.
The reason you use swaps at all, is just to simulate the behaviour describe above without having to allocate a separate data structure. In your for loop elements at index 0 through i represent the (unshuffled) pile, and elements at index i through (cards.Length) are the deck (you add cards in the front, in this implementation).
Maks Verver on December 5, 2007 1:55 AMTo make matters worse, your code for the shuffling-by-sorting is wrong. A sorting algorithm is only guaranteed to do anything meaningful if you call it with a partial ordering of the data. If you generate a different random key for the same element every time it is evaluated, the keys do not describe a partial ordering.
It probably works in practice because of the way the sorting algorithm works behind the scenes, but the correctness does not follow from the code. Some algorithms may not even terminate (or more correctly have a low probability of terminating) if you do not define a consistent ordering.
(DISCLAIMER: I don't really know the language used (VB.NET?) so it may be that additional guarantees are given by the language or library that I may have missed.)
What about employing several shuffling methods and alternate between them "randomly"?
Lahur on December 5, 2007 2:46 AMI'd just use the JDK function.
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#shuffle(java.util.List)
Funny that in my post about job interviews and reusing JDK functions to reverse a String one poster called me arrogant, because I thought most people when ask to write a String reverser would implement it instead of reuse it.
http://stephan.reposita.org/archives/2007/11/12/job-interviews-for-developers-attention-to-detail/
Thanks for proofing my point.
I don't think anyone has mentioned HotBits yet (http://www.fourmilab.ch/hotbits/) -- random bits made to order, generated from radioactive decay. You can build your own as well, instructions and code is on the site (the inline assembly brings back fond memories ;-)
bjorn on December 5, 2007 4:04 AMPeter: That is exactly why I suggested using a random real number between 0 and 1.
If the randomness source is crypto-strength random, and you generate batches of 52 double-precision sort numbers then you should expect there to be collisions in less than one out of every twenty trillion decks generated. (The math justifying this claim is left as an exercise.)
Crypto-strength guids have a much _smaller_ collision rate than doubles. I haven't worked out the math exactly, but order of magnitude, it'd be around one out of every trillion trillion decks.
In short, this is not a significant source of bias.
SELECT CardNumber FROM dbo.Cards ORDER BY NEWID()
Dear god... No!!
Shannon on December 5, 2007 4:58 AMHas Catto given up reading Coding Horror?
Mat on December 5, 2007 5:10 AMThe problem with the swap algorithm is not that it is too complex. It is perfectly straightforward. The problem is that some of the n! possible outputs are more likely than others.
Eric, I read your original description of this, and I even went over it with another programmer here. We *still* don't understand how the Knuth shuffling algorithm can have any bias, assuming the random number generator is crypto-strength.
Jeff Atwood on December 5, 2007 5:36 AMWay back circa 1989 I implemented a blackjack program using the sorting algorithm you suggested. The interesting thing was that the "platform" was a spreadsheet -- the whole thing was implemented in spreadsheet macros, and it was a complete implementation of the game, with insurance, splitting, etc.
The sort was done by having a named range of cards with 2 columns: the card itself, and the forumla RAND(). To shuffle I just told the spreadsheet to sort the range. I was pretty proud of that little thing.
At the time, I was in college and working part time as a tester of an office application suite. The guys in my department each implemented a different casino game as a means of pushing the tests as far as they'd go.
One guy did craps, and set it up to play automatically all night. The next morning we came in and it was rich, winning a bazillion dollars. We figured "that can't be right -- over time, you have to lose", so we ran it again the next night, and got the same result. It turns out that he'd uncovered a flaw in the spreadsheet's random number generator. Through some quirk, the dice rolls came up 11 (and 12) much more frequently than they should have.
Chris Wuestefeld on December 5, 2007 5:40 AMThank you, this post very clearly demonstrates the need to do quality work when developing software. A lot of times we take shortcuts and somewhere down the line, chaos happens. And thank you Mike for that excerpt from the PokerStars web site.
Sameer Alibhai on December 5, 2007 5:40 AM"@Andrew R RE: You should be constantly feeding the inputs with anything even remotely random that you can lay your grubby mitts on... keystroke timings, hard-disk response times, bytes received at network layer, CPU cycle count, ring-0 context times, etc. Everything. Anything. All the time."
I recently stumbled across a Java RNG that sought to "improve" on the one in the library by feeding the result back as the seed. When working on numbers in fairly small ranges it converged on the stable patterns of repeating numbers very quickly. At 5 digits it only produced a handful of results over and over. The requirement in this app was "few duplicates" regardless of any patterns or predictability. I just took out the "improvements."
How do you factor in those feedback sources to avoid this problem?
Interesting. Your physical definition of shuffle differs from mine. You're using the computer science notion of shuffle, not what actually occurs when one shuffles a deck of cards in the standard way.
As part of a course on counting theory, I built a card shuffling algorithm that models the way that humans shuffle a deck.
That algorithm, roughly, is:
1. Divide the deck into two stacks.
2. Pop the top item from the first stack into a result stack.
3. Pop the top item from the second stack into the result stack.
4. Repeat steps 2-3 until both stacks are exhausted, and the result stack contains all 52 cards.
What's interesting about this algorithm is that the results appear random by human observers, but are quite deterministic. If you shuffle the stack perfectly either 8 or 26 times (depending on implementation of the algorithm), the deck returns to the original order!
This is the algorithm used by most card sharks and all automatic card shufflers in Reno and Vegas, even if they don't call it an algorithm.
Then as part of this college course, I looked at the entropy introduced by non-perfect shuffling. Which was pretty interesting. It came in handy when working in Reno, although I wasn't legally allowed to bet anything.
By the way, thanks for the link to Cigital's case study! Contact me if you have any questions, or want some code for the above algorithm:
bwalther@cigital.com
By the way, Cristian's Python code is wrong:
He said:
import random
shuffled_deck = random.shuffle(range(52))
it should be:
import random
deck = range(52)
random.shuffle(deck,random.random)
The shuffle sorts it in place, and returns NULL. The second variable is not optional; it is what specifies which random number generator to use. If none is specified, the deck is not randomized at all.
(in Python 2.5 at least)
@ Western Infidels
"... ill-equipped to even measure the true randomness of any such source of entropy... expert-designed schemes for entropy distillation and accumulation.... not just "roll our own.""
I agree. Absolutely. In fact, I'm pretty sure that is precisely what I said.
@ Jim
"I recently stumbled across a Java RNG that sought to "improve" on the one in the library... I just took out the "improvements."
Good for you. I hope that worked out for you, though I conjecture that both versions are rubbish.
Did either of you realise what you were actually suggesting in your following statements abot entropy sources?
Let's review...
ME: you should use absolutely any even source of even remotely/potentially random noise as input to your PRNG
YOU: how do you purpose to judge the value of an entropy source?
So...
You're suggesting that a PRNG have NO source of entropy?
Perhaps you're suggesting that somehow the PRNG has a magic internal yet-software-based source of entropy?
Entropy has to come from somewhere and it sure ain't embedded in the PRNG itself. Meanwhile, I can't judge the value of any source. But I *can* provide a crapload *of* them, which will result in the largest possible yield of entropy. So I'll do that and trust that the person who wrote the PRNG is pretty smart and knows to push their entropy sources into block-cipher/hash algorithms like SHA1 and mix it all up etc.
I suggest you both read up on the Fortuna PRNG.
I repeat: it is an impressive piece of work - I cannot do it justice here.
Andrew R on December 5, 2007 7:20 AMI was about to post that someone should build a web service that provided realistic random numbers, but with a bit of quick googling it appears that it exists already. And as another commenter suggested, it uses environmental noise. Cool stuff.
JohnFx on December 5, 2007 7:34 AMThe sorting shuffle is biased! Here's why:
Sometimes, the random number generator will assign the same number to two different cards. (Because of the Birthday Paradox, this can happen *much* more often than you might expect.) The order of cards assigned the same number is then just a property of the sorting algorithm. For instance, if you're using a stable sort, your shuffler will have a slight order-preserving bias.
Whether this bias is large enough to worrying about depends on the context, but it can be hard work to prove that the sorting shuffle is good enough for your purposes. So why not just use the Knuth shuffle instead? It's really not so hard; I can describe it in one sentence: "To shuffle n cards, shuffle the first n-1 cards, and then swap the nth card with the card at a randomly chosen location."
Peter on December 5, 2007 8:59 AMThere is no random, there is only unpredictable.
brian on December 5, 2007 9:32 AMI'm working on a gambling program, and made the decision to collect random #s from www.random.org. This site makes the following statement: RANDOM.ORG offers true random numbers to anyone on the Internet.
It's a different approach - I created a data file of 10k #s, and run through them in a circular fashion each time I need a new #.
Gene Sewell on December 5, 2007 10:23 AMJeff: Julian's Array Swap algorithm is not the same as Knuth's. The difference is in the line:
R = Random number from 1..52
Knuth's version would be:
R = Random number from 1..X
Eric's (really neat!) proof of bias only applies in the first case.
Eric: I was about to flame you, but then it occurred to me that you're a smart guy who earns more than I'm ever likely to, so maybe -- just maybe -- I could learn something.
So why do we differ?
You like Sorting Shuffle because it's simpler and easier to explain.
I like Knuth's Shuffle because it's more elegant and easier to prove correct.
When you're managing programmers, Sorting Shuffle wins every time. Having said that, the Birthday Paradox still leaves me feeling a little uneasy....
Okay. That's enough hair-splitting from me.
Peter on December 5, 2007 10:25 AMMr. Sean Patterson has an interesting quote:
Assuming you're using 8 "piles" you take the top card of the deck and put it in pile 1, the second in pile 2, and so on. When you go through all your cards (minimum of 40, no maximum) you then grab your piles at random and you have your deck again.
Which comes directly from one of the many Collectible Card Games (in this case I would guess Magic the Gathering, limited play has 40-card decks). It's neat that he's mentioned this shuffling method b/c a game like Magic hinges on a balanced distribution of a couple of classes of cards. You'll have a deck comprised of 3 classes of cards in a 17-16-8 distribution and then you'll start with 7 off of the top. For the game to really flow you'll need 2-4 cards from the first class (17) 2-4 cards from the second class (16) and 1-2 cards from the last class (8).
Normally, this works, but every once in a while the hand is "no good" and you have to take a mulligan. To avoid this, rookie casual players will pick up the played cards (about half of the deck), pile them by class and then "weave" them together. They then do a quick shuffle: a couple of riffles and overhand cut or two. This type of shuffling generally cuts down on the mulligans because the cards are either nicely ordered or clumped in small groups (still acceptable).
Of course, the method described by Sean is actually considered cheating at the pro level (yes there is a pro level). "The weave" is something like an automatic disqualification and pro players don't even stack their cards by type, they just pick up everything between games and shuffle away. The shuffling ritual can suck up 5 minutes of a 50 minute round, but hey it's part of the game.
Of course, there's also Magic: Online which provides a digital version of the game. Some class of online players have personified and villified "The Shuffler" as if some machine construct were out to get them.
In reality, the real-life pros also dominate the on-line game, despite all of this randomness. Which is likely a sign that they're shuffling pretty well :)
Gates VP on December 5, 2007 10:56 AMThe guid approach sounds approximately as bad as the original random number generation approach. What they really need to do is focus on randomizing the seed value, and I really don't think that would take much for this purpose.
I have a few ideas for one. Random typing by a trained monkey would be my second choice.
Jess Sightler on December 5, 2007 11:05 AM* As others have noted, guids are not guaranteed to be a good source of randomness. Though most implementations are in fact crypto-strength random, it would be wise to call a method guaranteed to return crypto-strength randomness.
* The problem with the swap algorithm is not that it is too complex. It is perfectly straightforward. The problem is that some of the n! possible outputs are more likely than others.
How would you write code to shuffle a deck of cards?
By going to a book of algorithms and looking up the optimal solution.
(I assume the question is a variant of the proposition that the best tool for repairing a TV is a TV repairman).
Dave on December 5, 2007 12:15 PMMy first impulse was to randomise the cards as I was filling the array/list (populating a parallel set to check for dupes), not actually shuffling an existing deck. This, and the "pick a random card from the collection", method does not come from the idea of a pre-existing ordered deck and I think that's a good thing (because there is no "order" to be unexpectedly exposed should the randomness be less than expected).
Jonas on December 5, 2007 12:26 PMHere's a clip from the PokerStars website (they did their homework):
[quote]
SHUFFLE
"Anyone who considers arithmetic methods of producing random digits is, of course, in a state of sin." - John von Neumann, 1951
We understand that a use of a fair and unpredictable shuffle algorithm is critical to our software. To ensure this and avoid major problems described in [2], we are using two independent sources of truly random data:
* user input, including summary of mouse movements and events timing, collected from client software
* true hardware random number generator developed by Intel [3], which uses thermal noise as an entropy source
Each of these sources itself generates enough entropy to ensure a fair and unpredictable shuffle.
Shuffle Highlights:
* A deck of 52 cards can be shuffled in 52! ways. 52! is about 2^225 (to be precise, 80,658,175,170,943,878,571,660,636,856,404,000,000,000,000,000 ways). We use 249 random bits from both entropy sources (user input and thermal noise) to achieve an even and unpredictable statistical distribution.
* Furthermore, we apply conservative rules to enforce the required degree of randomness; for instance, if user input does not generate required amount of entropy, we do not start the next hand until we obtain the required amount of entropy from Intel RNG.
* We use the SHA-1 cryptographic hash algorithm to mix the entropy gathered from both sources to provide an extra level of security
* We also maintain a SHA-1-based pseudo-random generator to provide even more security and protection from user data attacks
* To convert random bit stream to random numbers within a required range without bias, we use a simple and reliable algorithm. For example, if we need a random number in the range 0-25:
o we take 5 random bits and convert them to a random number 0-31
o if this number is greater than 25 we just discard all 5 bits and repeat the process
* This method is not affected by biases related to modulus operation for generation of random numbers that are not 2n, n = 1,2,..
* To perform an actual shuffle, we use another simple and reliable algorithm:
o first we draw a random card from the original deck (1 of 52) and place it in a new deck - now original deck contains 51 cards and the new deck contains 1 card
o then we draw another random card from the original deck (1 of 51) and place it on top of the new deck - now original deck contains 50 cards and the new deck contains 2 cards
o we repeat the process until all cards have moved from the original deck to the new deck
* This algorithm does not suffer from "Bad Distribution Of Shuffles" described in [2]
PokerStars shuffle verified by Cigital and BMM International
PokerStars submitted extensive information about the PokerStars random number generator (RNG) to two independent organizations. We asked these two trusted resources to perform an in-depth analysis of the randomness of the output of the RNG, and its implementation in the shuffling of the cards on PokerStars.
Both independent companies were given full access to the source code and confirmed the randomness and security of our shuffle. Visit Online Poker Random Number Generator for more details.
[2] "How We Learned to Cheat at Online Poker: A Study in Software Security" - http://itmanagement.earthweb.com/entdev/article.php/616221
[3] "The Intel Random Number Generator" - http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf"
You should see what pokerstars.com writes on its website about its shuffle. For the random number generator, it supposedly uses, among other things, mouse movements of the users!
Greg
Greg Magarshak on December 5, 2007 12:50 PMI'd probably use a few different "shuffling" techniques back to back – If possible, I'd change up the order in which the different techniques where applied.
It wouldn't be as efficient as some people's suggestions, but I think it'd produce a fairly random shuffle; at least as far as users would notice.
Frank on December 5, 2007 12:50 PMFor those asking about why the built-in Rand() function and Timer seeds are less than optimal.
Rand() uses the generated Random number as the Seed to the next number. So even if you used the Timer to start the initial seed you can predict every number after the first randomly generated one as it is a sequnece that can be repeated every single time.
So to try to clarify, if the Random number generated using Rand() and a Timer seed was 52, then 52 is used to seed the next number and you will get the same value every time, in fact RandomNumber2 through Random NumberInfinity is now predictable.
All that using the Timer for a seed does is scramble the first possible number.
Rand() is classified as a Linear Congruential function.
A good random number generator has three properties:
1. It generates evenly distributed numbers
2. The values are unpredictable
3. It has a long and complete cycle (it generates a large number of different values and all the values in the cycle can be generated).
Linear congruential functions meet the first property but fail the second property miserably! In other words, rand() produces an even distribution of numbers, but each next number is highly predictable!
Let’s look at the source code to a typical rand function:
unsigned long int next =1;
int rand(void)
{
next = next * 1103515245 + 12345;
return (next/65536) % 32768;
}
DotNet has a much better random number generator called RNGCryptoProvider.
I appreciate the elegance of Jeff's solution in that it reduces the required code to just several lines. I have used this exact same problem in my programming classes and have seen solutions with 100+ lines of code over the years.
The other advantage to using random numbers and sorting is that it scales very well to very large number sets.
David E. on December 6, 2007 1:00 AM@WaterBreath
"Instead I suggest to just pull and discard numbers from your PRNG"
How, pray tell, do you intend to make your "pull and discard" algorithm non-deterministic?
Perhaps you can use a random timing?
But, oops, that requires a random number, which requires a non-deterministic PRNG... in other words, you need a non-deterministic PRNG to build your non-deterministic PRNG...
When I first saw this example of shuffling, I had no idea about syncing the random seed with another could lead to such a security hazard. But I don't believe using a GUID is a perfect way to generate a random number, unless you know that it's algorithm produces an equally distributed random number--and that is determined by the GUID algorithm's "variant and the version" (http://www.famkruithof.net/guid-uuid-make.html).
So either be careful when choosing the API your GUID is generated from, seed your random generator with a unique number, or randomly sort the GUID's
[If you don't know about hash tables, find a tutorial about the various ways you can make them. Very interesting if you enjoy data structures and algorithms]
My idea is to use a hash table to sort the cards into by each cards generated GUID. By using a randomly generated number in the hash tables algorithm, this guarentees evenly distributed shuffling as well as essentially O(n)--which is only interesting when you come across much a much larger amount of cards (i.e. encryption and such).
In this way, if you use an API which is inflexable (doesn't let you seed your random number generator or choose your GUID algorithm), you can still adapt an equally distributed GUID method.
James on December 6, 2007 6:04 AMIf you need real random numbers ie your business depends on it. You need
to decaying radioactive material.
Example of that is below:
http://www.fourmilab.ch/hotbits/
http://www.fourmilab.ch/hotbits/hardware3.html
nuff said.
Scott Wickham on December 6, 2007 8:14 AMThe comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |