when writing a card dealer are there any requirements other than:
- not predictable
- during a hand don’t deal the same card twice
- the cards should be dealt randomly
perfect shuffle in perl :
sub shuffle {
my @a = ();
my @b = ();
return @_ if (@_ 2);
for (@_) {
if (random_bit()) {
push @a, $_;
} else {
push @b, $_;
}
}
return (shuffle(@a), shuffle(@b));
}
This is similar to the radix sort algorithm with random numbers.
random_bit returns a boolean. This bit can be read from /dev/random for true randomness on linux.
Very cool app. Can you tell me where to download the Help files? Apparently they didn’t make it during the install process, so it won’t load them. Thanks!
Thank you very muCh
Thanks for addressing this issue so quickly, Dr. Lessig. I thought something was fishy in that article.
So the OrderBy criteria:
- var shuffledcards = cards.OrderBy(a => Guid.NewGuid());
is basically equivalent to - Random rand = new Random()
- var shuffledcards = cards.Sort((a,b) => rand.Next(0,2) == 0 ? -1 : 1);
since a new guid is created on every comparison. So it’s basically sorting with every Compare returning a random result - which isn’t the same as the sort Eric mentioned - it will likely be biased based on the sorting algorithm used.
thank you was a useful article…
Thanks a load for the stats. Haven’t seen anything nearly as comprehensive or useful anywhere else.
I can’t wait for the day when web design programs are as easy as layout programs for print!
how can i divide the deck into three parts and then shuffle them?
A possible source of randomness that is available to everyone is environmental RF noise. This can be sampled off of the line input from the sound card. Best if it is hooked up to a radio between AM stations, but even with nothing plugged into it, there is usually a little noise. In an actual casino, a microphone may be a good source as well. What is needed is a real world (as opposed to computed) source because the real world is not predictable. Sample this several times, and combine the results into a seed.
Not quite radioactive decay, but pretty good for the price.
Any algorithum is going to be predictable where are “random” numbers should be unpredictable. So there is a problem right there.
Sampling noise and mouse click helps makes the output more unpredictable, thus the resulting number should be unpredictable.
Of course there are many ways to shuffle cards. Throw all cards on table and move them around with your hands. Stack, cut and deal. You could also try to mimic that behavior and consider the deck shuffled.
There is also probabilities to be considered. If decks are shuffled, probability says 1/52 chance of first card being an Ace of Spades. Now you may shuffle a thousand times and not get an Ace of Spades as the first card, but with a large amount of attempts (and I do mean large), the percentage should converge to 1/52. Otherwise, someone may think your shuffle is rigged.
So not only does you shuffle have to be random, but its results should converge to known probabilities over time.
Two thoughts that are being addressed here:
-
If you are doing anything you care about, research the random number generator (PRNG) you are using. The best ones will have passed a number of theoretical tests to deterimine that they indeed have no pattern. Fun to note that one of the quick litmus tests is to generate a large number of 5-card poker hands and see how the result aligns to computed probabilities.
-
Using noise and other environmental sources is tempting. However, I think this creates a maintenance burden to ensure that the quality of the random number stream is high and stays high!
As others have said, the problem with Random is often the seed. .NET’s random number generator is pretty decent if you use an unpredictable seed:
Random rand = new System.Random(Guid.NewGuid().GetHashCode());
For something like online gambling where significant money’s involved, the crypto RNG would be better. In that case, you’ll need to give up on a one-liner (unless it’s one unreadable line), since the RNG returns an array of bytes.
http://msdn2.microsoft.com/en-us/library/system.security.cryptography.rngcryptoserviceprovider.aspx
I know this is a late comment, but I have something to add to this. I don’t have experience with deck shuffling algorithms, however I can’t really see much problem here. Even though random and psuedo random coding is sketchy at best, when it comes to deck shuffling, it shouldn’t be difficult to figure out how to randomize the deck.
Take real world shuffling with the hands, you roughly cut the deck in half, then attempt to merge them so that the deck is in staggered as perfectly as possible. However in real life it doesn’t happen with perfection, and therefore there are always a few to several cards that are “misplaced” in the pattern. repeat until one is “comfortable” with the randomized nature of the deck.
One could simply emulate this with a few random routines. Literally randomly deciding which is the next card to merge into the new deck from the split decks.
If one loops the deck through something like this, the results should be staggeringly more random than initially suspected.
dim deck
for i = 0 to 12
main(
I would like to have a preview first, I hit the post button accidentally while writing thise. Though I suppose I should have written in a text editor first.
I don’t think you need the rest to understand what I mean though.
This is a bit of a tongue-in-cheek suggestion, but I’ve actually used it a few times.
As many posters have pointed out, choosing a good seed value can make all the difference. My method is called Pr0nSeed. I select an image from a library of photos I’ve taken. (I’ve yet to run out, but I could shuffle them based on (say) file-size and dimensions and a random component, and then cycle through the newly shuffled list).
Then I use the built-in RNG to select a pixel (in a variant of this, you could simply cycle through each pixel in sequence, but that depends on your image – continuous tone gradients can be predictable). Then I build a seed using the R, G, and B values of the pixel that results.
Obviously the type of images you use will affect the quality of your seed – for one thing, the less compression and the less post-processing, the better.
You could even generate the “random” number directly from the RGB values without using the RNG to generate X and Y values, just by iterating through the pixels.
Another thought to improve quality (i.e. unpredictability): If you have a library of images you can (in a pre-process) run through them and toss out those that don’t meet a certain threshold for the number of distinct colors (i.e. an overexposed picture of a white piece of paper would be fairly useless).
Also, you could pick R, G, and B values from separate pixels, not the same one.
This seeding algorithm relies on the idea that you own a collection of images that no-one else has access to. If you take your own pictures (particularly high-res ones) and secure them decently, you can rely (as far as I can see) on your sequence being fairly unpredictable.
I called it Pr0nSeed because when I originally came up with I needed a large library of images, so I used my, uh, downloaded adult-themed images 
Now I use a collection of photos I’ve taken myself which are far more boring but contain less continuous-tone imagery – stuff like sand, gravel, trees, etc.
Ultimately this algorithm uses the system RNG (or a library RNG) simply as an indexer into a large array (the image) of unpredictable numbers. The current picture is changed every “x” calls to Random(), where “x” represents a tradeoff between possibly repeating values (due to a poor RNG or an image with too few distinct colors) and performance.
Not being a mathematician (or, indeed, even having a CS qualification of any kind) I’d be interested in comments on potential flaws in this approach (I’m sure there are many).
I hope this comment will bubble up.
Post has a lot of good details, but there is a problem with the second code in C#.
var cards = Enumerable.Range(0, 51);
var shuffledcards = cards.OrderBy(a => Guid.NewGuid());
There are two problems with it covered by Eric Lippert:
Do not use a random function as a comparator and feed that to a sorting algorithm. Sort algorithms are permitted to do anything they please if the comparator is bad, including crashing, and including producing non-random results. As Microsoft recently found out, it is extremely embarrassing to get a simple algorithm like this wrong.
Do not sort on a "random" GUID as your key. GUIDs are guaranteed to be unique. They are not guaranteed to be randomly ordered. It is perfectly legal for an implementation to spit out consecutive GUIDs.
Kind Regards,
Lukas M
Funny story. I had to create an algorithm in C# that would shuffle 2 lists in a database that we had yet to get from the client. After much head-banging and learning about RNG, i discovered the total length of our 2 lists we needed to shuffle. 4 and 26. Hence 4 factorial and 26 factorial.