Re: [FWP] Shufflebug

[Bennett Todd <bet@rahul.net>]

2000-07-18-15:36:53 Bernie Cosell:
> > ...In physical cards it's the proximity of positions that
> >  have to be overcome by multiple shufflings.
> 
> Not quite: for bridge, you only have to randomize the position *mod*4 
> -- this is actually a lesser constraint than having to have a shuffle 
> that can generate all 52! [or whatever it is] shuffles with equal 
> probability.  That is, you don't care that card A's *position* is 
> indpendent of its position in the pre-shuffled deck, but rather that 
> *the*hand*that*gets*it* is independent of that...  alas, I can't 
> offhand come up with an algorithm that I can defend that just makes a 
> "random deal" [rather than a randomly shuffled deck] but my intution 
> says we ought to be able to come up with one...

Well, the trivial direct random deal would follow naturally from the
Fisher-Yates shuffle, when expressed as a series of splices rather
than swaps; e.g. (untested)

	my(@deck) = 0 .. 51;
	my(@hands) = ([], [], [], []);
	while (@deck) {
		for (@hands) {
			push @{$_}, splice(@deck, rand(@deck), 1);
		}
	}

But that's no improvement, in terms of needing fewer random bits; it
just does a shuffle and a deal all at once.

It _seems_ to me that perhaps a genuine random deal, using the
absolute minimum number of random bits, could possibly be done with
something like

	my(@deck) = 0 .. 51;
	my(@emtpy_hands) = ([], [], [], []);
	my(@dealt_hands);
	while (@deck) {
		if (@empty_hands == 1) {
			push @{$empty_hands[0]}, splice(@deck, 0);
			push @dealt_hands, splice(@empty_hands, 0);
			last;
		}
		my $hand = rand(@empty_hands);
		push @{$empty_hands[$hand]}, splice(@deck, rand(@deck, 1));
		if ($#{$empty_hands[$hand]} == 13) {
			push @dealt_hand, splice(@empty_hands, $hand, 1);
		}
	}

(very untested).

Of course this begs the question of whether the real behavior of
rand(), when used this way to generate random numbers of various
sizes and discard the floating point part, is as desired: that
apparently different sequences end up emerging as a consequence of
the scaling factor used, so that the above algorithm actually works
better. It also leaves out the hard part, which is that even if you
can get away with treating rand() as though the range of the output
affects the amount of randomness consumed, you need to keep track of
how much you've gobbled, and re-seed it each time you've used up the
last 32 bits you fed it via srand. I don't think I want to try and
address either of those questions, I'm so far over my head here that
I can't even see the surface:-).

Wait a minute, just had a brainstorm, lessee, how about (wildly
untested)

	srand;
	my $pool = 32;
	sub log2 { log($_[0])/log(2) }
	my(@deck) = 0 .. 51;
	my(@emtpy_hands) = ([], [], [], []);
	my(@dealt_hands);
	while (@deck) {
		if (@empty_hands == 1) {
			push @{$empty_hands[0]}, splice(@deck, 0);
			push @dealt_hands, splice(@empty_hands, 0);
			last;
		}
		if ($pool < log2(scalar(@empty_hands))) {
			srand;
		}
		my $hand = rand(@empty_hands);
		push @{$empty_hands[$hand]}, splice(@deck, rand(@deck, 1));
		if ($#{$empty_hands[$hand]} == 13) {
			push @dealt_hand, splice(@empty_hands, $hand, 1);
		}
	}

-Bennett

PGP signature