From: tnh@sw.stratus.com (Tim Hill)
Newsgroups: rec.games.bridge
Subject: Re: Which inference is better, WAS - "finesse or play for the drop"
Date: 20 Nov 92 16:29:28 GMT
Organization: Stratus Computer, Inc.
NNTP-Posting-Host: bigbootay.sw.stratus.com

In article <davidm.722210891@questor>, davidm@questor.Rational.COM (David Moore) writes:
> A British Bridge magazine did an analysis of hand dealt hands about 20 years
> ago which supported this; because there is some "memory" in a hand-shuffled
> deck, Q's lie under K's more than 50% of the time. What they actually showed
> ib the magazine was that hands tend to be flatter with hand-shuffled decks.

Note that this applies to decks shuffled, say, three or four times.  Hand deals
after at least seven shuffles are, for all practical purposes, random.  (Sandy
Kutin pointed to a paper that discusses this mathematically:  Bayer & Diaconis,
"Trailing the Dovetail Shuffle to its Lair," _The Annals of Applied Probability_,
1992, 2, no. 2, pp. 294-313)

(When I was a lad, my Mother often admonished me not to "shuffle the spots off
the cards" on the theory that overshuffling produced flatter deals.  Wrong.)

There have been some questions here and on the OKBridge mailing list about the
randomness of computer deals.  Programs that CORRECTLY implement the simple
algorithms in Knuth [_The Art of Computer Programming, Volume 2, Seminumerical
Algorithms_, 1969, Addison-Wesley, Reading, Mass.] produce deals that are, for
all practical purposes, random.  OKBridge apparently has it right.  I hope the
ACBL has it right, but I don't know.

However, there are a couple pitfalls* in implementing those algorithms.  As
somebody noted, the dealing program recently posted here hits one of those
pitfalls.  I'm sure that, among the thousands of programs that deal cards,
a substantial number don't have it right.


                                    Tim


*The pitfalls:

1)   The least significant bits produced by a linear-congruential pseudo-random
     number generator aren't very random.  If the output from your generator
     is an integer in the range [0,2^N) and you want an integer in the range
     [L,U], the best technique is to divide by 2^N (producing a fractional
     result, which can be represented as floating or fixed point), multiply
     by U-L+1, truncate to an integer, and add L.  This works very well provided
     U-L << 2^N.

2)   The simplest way for a computer to deal is to pick a card pseudo-randomly
     from the unshuffled deck, then pick another card pseudo-randomly from the
     remaining 51, etc.

     If you prefer to "shuffle" the deck in place before dealing, Knuth gives
     an algorithm that is equivalent to the above:  Pick a card pseudo-
     randomly from the whole deck (including the bottom card) and swap it with
     the bottom card, then pick a card pseudo-randomly from the top 51 cards
     and swap it with the next-to-bottom card, etc.

     Note that only the top 53-N cards should be candidates for the Nth swap.
     This gives each card exactly one chance to end up in each slot.

     The pitfall is including the bottom N-1 cards among the candidates for the
     Nth swap.  This gives cards originally placed in low slots extra chances to
     be yanked out of those slots.  (If this isn't clear, work out the
     probabilities for a three-card deck.  You'll discover that three
     permutations are twice as likely as the other three, and that the
     probabilities of a given card ending up in a given slot are 4:3:2 instead
     of 1:1:1.)
Newsgroups: rec.games.bridge