Re: Card dealing and random repetition

On Wed, 04 Jan 2006 10:42:04 +0100, Schraalhans Keukenmeester
<none@xxxxxxxxxxx> wrote:

>Most rand() implementations, even the more sophisticated PRNG's
>are limited to 32 or 64 bits at best. Given the fact that they will
>always produce identical series given the same seed, it follows the
>randomizer repeats itself after max. 2^32 cq 2^64 numbers.
>
>If you shuffle a deck of 52 cards, there are 52! different decks to end
>up with, or 8.0658175170943878571660636856404e+67 different possibilities.
>
>(I did an experiment, not exhaustively, but I manually shuffled a deck
>of cards, created an array with the same card order and shuffled a deck
>continuously and kept track of how many cards in the shuffled deck
>matched the order in the 'test' array. To my shock & horror after more
>than a 100 billion shuffles I had only the first three cards matching.
>Quite bizarre! Note: I may have had more matches, but I only count rom
>the top, and quit when the first non-matching card is found)
>
>I know several poker/bj-sites brag about using true random seeds each
>run, I still think that if there are 'just' 2^64 (18446744073709551616)
>possibilities there are no more than that number of ways the resulting
>deck is shuffled. Or am I wrong?
>
>I'd say, only if you (RANDOMLY) reseed the randomizer between each card
>picked there is a chance you will eventually exhaust the possibilities.
>
>How would one get around this problem without resorting to a true random
>source?
>
>Your help/insight is very welcome.

Have a look at L'Ecuyer: "The basic underlying generator for this
implementation is a combined multiple recursive generator with period
length of approximately 2^191"

From: http://or.pubs.informs.org/Media/L'Ecuyer.pdf

rossum


--

The ultimate truth is that there is no ultimate truth
.

Relevant Pages

  • Re: portably shuffle a deck
    ... this cannot portably shuffle a deck, ... RNG schemes). ... the cards up using a set of shuffle techniques that are more or ...
    (comp.lang.c)
  • Re: I pee in the open
    ... But humans also don't start with a new ordered deck ... probably per game just to make sure all the cards are there. ... These things will add some randomness. ... people don't shuffle perfectly, so randomness only occurs on a scale ...
    (alt.lang.asm)
  • Re: Card dealing and random repetition
    ... and inspiring for an 'elegant' way to simulate a shuffle. ... The dealer divide the deck in two parts, trying to make them equally big (but I estimate the error margin being between 1 to 5 cards from the count of 26 cards per half-deck). ... adding a random probability of the next card on the array being picked instead of the next of the other array. ...
    (comp.programming)
  • Re: Quote of the day
    ... grand proclamations to the effect of "I have super high standards that ... I have never seen anyone cut the cards in all the ... Frankly I don't recall if I ever cut the deck but having reasonable ... deck blackjack table style shuffle). ...
    (rec.games.bridge)
  • Re: Madness Network + Rotschreck is too good!
    ... I assist a novice in building a combat-heavy deck using cards from ... to play DotB, and there can be Protean-based cards. ... Valerius player or with another player to kill Valerius". ...
    (rec.games.trading-cards.jyhad)