[NBLUG/talk] Request for help--how to program shuffling

[Andru Luvisi]

On Tue, 20 May 2003, Steve Zimmerman wrote:
[snip]
> Therefore, *a truly random shuffle would prevent the
> programmer from ordering the cards in any way whatsoever,
> either randomly or non-randomly!*
[snip]

Unfortunately, you simply cannot create "randomness" on a deterministic
machine.  If a computer is working properly, it will spit out the same
output every time you give it the same input.

If you want something to be "truly" random, you need a source of really
random numbers.  /dev/random and /dev/urandom provide "random" numbers
that the kernel creates using network traffic levels, hard drive
statistics, and other things that "should" contain entropy.  I hear that
atomic decay is another decent source for truly random numbers.

I highly recommend reading the beginning of Knuth's chapter on random
numbers.  He talks about his super random function that was terrible, and
then explains why a pseudo random function chosen at random is likely to
be lousy.  I believe that this same lesson is also applicable to one's
choice of shuffling algorithm.  If you pick (or make up) one at random, it
is likely to have biases.  If you use Fisher/Yates, at least you only need
to worry about your random number source (which is hard enough).

Several online casino's have had problems with their shuffling algorithm.
In one particularly sad case that I heard of, once the player had seen a
certain number of cards, he could deduce the order of the rest of the
deck.  Because only a small percentage of the potential orders were
actually possible, the player could figure out which one was currently in
play.

For a good time, check out Bruce Schneier's PRNG, Yarrow:
  http://www.counterpane.com/yarrow.html

Schneier knows what he is talking about.  He has cracked numerous
encryption systems by finding vulnerabilities in their PRNGs.

Andru
-- 
Andru Luvisi, Programmer/Analyst



Quote Of The Moment:
  Truth is hard to find and harder to obscure.