home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / games / bridge / 6611 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  3.7 KB
  1. Path: sparky!uunet!europa.asd.contel.com!emory!wupost!zaphod.mps.ohio-state.edu!rpi!bu.edu!transfer.stratus.com!sw.stratus.com!tnh
  2. From: tnh@sw.stratus.com (Tim Hill)
  3. Newsgroups: rec.games.bridge
  4. Subject: Re: Which inference is better, WAS - "finesse or play for the drop"
  5. Message-ID: <1ej3p8INN6f@transfer.stratus.com>
  6. Date: 20 Nov 92 16:29:28 GMT
  7. References: <1992Nov17.175850.18797@cbnewsi.cb.att.com> <davidm.722210891@questor>
  8. Organization: Stratus Computer, Inc.
  9. Lines: 61
  10. NNTP-Posting-Host: bigbootay.sw.stratus.com
  11.  
  12. In article <davidm.722210891@questor>, davidm@questor.Rational.COM (David Moore) writes:
  13. > A British Bridge magazine did an analysis of hand dealt hands about 20 years
  14. > ago which supported this; because there is some "memory" in a hand-shuffled
  15. > deck, Q's lie under K's more than 50% of the time. What they actually showed
  16. > ib the magazine was that hands tend to be flatter with hand-shuffled decks.
  17.  
  18. Note that this applies to decks shuffled, say, three or four times.  Hand deals
  19. after at least seven shuffles are, for all practical purposes, random.  (Sandy
  20. Kutin pointed to a paper that discusses this mathematically:  Bayer & Diaconis,
  21. "Trailing the Dovetail Shuffle to its Lair," _The Annals of Applied Probability_,
  22. 1992, 2, no. 2, pp. 294-313)
  23.  
  24. (When I was a lad, my Mother often admonished me not to "shuffle the spots off
  25. the cards" on the theory that overshuffling produced flatter deals.  Wrong.)
  26.  
  27. There have been some questions here and on the OKBridge mailing list about the
  28. randomness of computer deals.  Programs that CORRECTLY implement the simple
  29. algorithms in Knuth [_The Art of Computer Programming, Volume 2, Seminumerical
  30. Algorithms_, 1969, Addison-Wesley, Reading, Mass.] produce deals that are, for
  31. all practical purposes, random.  OKBridge apparently has it right.  I hope the
  32. ACBL has it right, but I don't know.
  33.  
  34. However, there are a couple pitfalls* in implementing those algorithms.  As
  35. somebody noted, the dealing program recently posted here hits one of those
  36. pitfalls.  I'm sure that, among the thousands of programs that deal cards,
  37. a substantial number don't have it right.
  38.  
  39.  
  40.                                     Tim
  41.  
  42.  
  43. *The pitfalls:
  44.  
  45. 1)   The least significant bits produced by a linear-congruential pseudo-random
  46.      number generator aren't very random.  If the output from your generator
  47.      is an integer in the range [0,2^N) and you want an integer in the range
  48.      [L,U], the best technique is to divide by 2^N (producing a fractional
  49.      result, which can be represented as floating or fixed point), multiply
  50.      by U-L+1, truncate to an integer, and add L.  This works very well provided
  51.      U-L << 2^N.
  52.  
  53. 2)   The simplest way for a computer to deal is to pick a card pseudo-randomly
  54.      from the unshuffled deck, then pick another card pseudo-randomly from the
  55.      remaining 51, etc.
  56.  
  57.      If you prefer to "shuffle" the deck in place before dealing, Knuth gives
  58.      an algorithm that is equivalent to the above:  Pick a card pseudo-
  59.      randomly from the whole deck (including the bottom card) and swap it with
  60.      the bottom card, then pick a card pseudo-randomly from the top 51 cards
  61.      and swap it with the next-to-bottom card, etc.
  62.  
  63.      Note that only the top 53-N cards should be candidates for the Nth swap.
  64.      This gives each card exactly one chance to end up in each slot.
  65.  
  66.      The pitfall is including the bottom N-1 cards among the candidates for the
  67.      Nth swap.  This gives cards originally placed in low slots extra chances to
  68.      be yanked out of those slots.  (If this isn't clear, work out the
  69.      probabilities for a three-card deck.  You'll discover that three
  70.      permutations are twice as likely as the other three, and that the
  71.      probabilities of a given card ending up in a given slot are 4:3:2 instead
  72.      of 1:1:1.)
  73.