[FWP] Shufflebug

[Amir Karger <karger@fermi2.chem.yale.edu>]

Hi.

Last year, I mentioned my "Random Schwartz" card shuffle on fwp:

	@{$deck->{"cards"}} =
	    map { $_->[0] } 
	    sort { $a->[1] <=> $b->[1] } 
	    map { [$_, rand] } 
	    @{$deck->{"cards"}};

http://bumppo.net/lists/fun-with-perl/1999/08/msg00029.html
http://bumppo.net/lists/fun-with-perl/1999/08/msg00076.html
start two of the threads.

Folks seemed to agree it was pretty random, although Chip turner said (in
msg00044.html) "I'm not 100% convinced this is a truly random
sort, but I think it should be pretty good.  Hopefully the rand perl
uses (which I hope desperately isn't the default rand that the OS
comes with, but deep down I suspect it is) is decent enough to give a
good distribution."

Well, today I got mail from James Wetterau, suggesting that it's not. (Minor
snippage)

----- Forwarded message from James Wetterau <jwjr@ignition.name.net> -----
Subject: bug in Games-Cards-1.45

I believe your shuffle has a bug (at least if it's meant to produce a
truly shuffled deck).  

Your shuffle revolves around the ordering of (up to about) 52
consecutive calls to rand.  On a machine with 15 randbits I believe
the randomization sequence repeats within 2 ^ 32 iterations.
(According to my Solaris manpage.)  This means that there are only 2 ^
32 unique deck combinations that can be created out of these calls by
pulling out a set of 52 consecutive random calls from the sequence.

Assuming this ratio, holds constant, even a machine with 31 randbits
would repeat its sequence of numbers after 2^64 iterations.  (I'm
guessing at this.)

Now the total number of deck combinations possible by shuffling a true
deck is between 2 ^ 225 and 2 ^ 226.  So if you only shuffle once,
you're playing with a greatly diminished subset of the possible truly
well-shuffled decks. 

Now then, a good solution might be to shuffle multiple times.  I
haven't thought this through, but possibly application of a random
number of shuffles, say between 5 and 10 times, might allow your
shuffles to get to all the decks in the possible space of shuffled
decks.  But users should definitely not rely on single calls to
shuffle from a pristine ordering to offer them a truly random,
well-shuffled deck, because they'll only get one from among a very
small subset of possible deck permutations.

----- End forwarded message -----

I know nothing about randomness. So the questions:

(1) do you agree that this problem exists?
(2) do you agree with the fix? 

It seems clear that always doing 5 shuffles gives you exactly the same
number of permutations as doing 1 shuffle. However, I can't work out whether
randomly doing between 5 & 10 random shuffles would multiply the number
of possible decks by 6 (10-5+1), or give you much more randomness.
Would it help if I chose a random number of random numbers in between the
shuffles, thereby shifting the randomization sequence?

This doesn't seem to matter terribly much, since 2^32 hands is still more
than you could ever play in your lifetime. But fwp isn't necessarily about
things that matter, right?

<plug>
For those who might care, the Games::Cards module which includes this
shuffle just had a new release, v1.45, which includes two perl/Tk solitaire
games. That's *definitely* fun with perl!
</plug>

-Amir Karger
karger@fermi2.chem.yale.edu

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe