Background | Random Number Generator | Shuffling of Cards
Hand Logs

Integrity

Below is a discussion of some of the common issues encountered when shuffling decks of cards on a computer. It addresses some of the commonly used algorithms and their flaws, and then shares the superior solution we use at BugsysClub Poker to shuffle decks of cards.

We want you to know the algorithms we use for generating random numbers and shuffling cards so you have all the confidence that you are using world class solutions when you play at BugsysClub Poker.

Background:

Given a 52-card deck, there are over 8.065817517 x 10⁶⁷ possible unique sequences (approx. 8 x 10⁶⁷, or 2²²⁵) to an entire deck. This is an enormous number, which when spelled out looks like this very long number:

80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.

To understand why so many 52-card deck sequences are possible, think of it this way: the first card in the deck is one of 52 possible cards, the second is one of the remaining 51 cards, the third is one of the remaining 50, etc. So, for each of the 52 possible first cards, there are 51 possible second cards, and for each of the 52 x 51 first pairs of cards, there are 50 possible third cards. Continue with this logic to the last card, and you get: 52 x 51 x 50 x 49 ... x 4 x 3 x 2 x 1 possible card sequences (expressed mathematically as 52!, or 52 factorial) which when multiplied out, yields the huge number shown above.

In order to generate all the unique sequences possible in a 52-card deck, a random-number generation algorithm must be able to yield at least 52! unique random number sequences.

Random Number Generator

To ensure we can randomly generate all the unique sequences possible in a 52-card deck, we use the widely accepted and widely utilized Mersenne Twister PRNG (described at: http://www.wikipedia.org/wiki/Mersenne_Twister), invented by Makoto Matsumoto and Takuji Nishimura in 1997.

With increased exposure over the past few years, The Mersenne Twister PRNG is increasingly accepted as the random number generator of choice for all statistical simulations and generative modeling, especially because it overcomes the shortcomings of prior pseudorandom number generators (PRNG).

Prior Shortcomings:

Many older random sequence algorithms yield far less than the number of possible unique sequences of a 52-card deck. You often see only 2¹⁶, or 65,536 unique sequences generated by older RNGs, which is far short of the approximately 2²²⁵ needed to cover all possible sequences in a 52-card deck.

Another shortcoming of prior PRNGs is guaranteed periodicity - it is certain that if the generator uses only a fixed amount of memory, then given a sufficient number of iterations, the generator will revisit the same internal state twice, after which it will repeat forever. A generator that isn't periodic can be designed, but its memory requirements would slowly grow as it ran. In addition, a PRNG can be started from an arbitrary starting point, or seed state, and will always produce an identical sequence from that point on. Also, in practice, many prior PRNGs exhibit artifacts which can cause them to fail statistical significance tests. These include:
· Shorter than expected periods for some seed- states
· Poor dimensional distribution
· Successive values may not be independent
· Some bits are more random than others
· Lack of uniformity

What BugsysClub Uses:

The invention of the Mersenne Twister algorithm, by Makoto Matsumoto and Takuji Nishimura in 1997, avoids most of the problems that prior deterministic algorithms had.

The Mersenne Twister:

· Has a colossal period of 2¹⁹⁹³⁷-1 iterations, which is far more than the number needed to generate the number of possible unique sequences of card decks (approx. 2²²⁵ compared to the Mersenne Twister's 2¹⁹⁹³⁷ ).
· Accepts a seed of up to 19,968 bits. Other sites think a 2016 bit seed is overkill, we go much farther with 19,968 bits.
· Has a very high order of dimensional equidistribution. In fact, it is proven to be equidistributed in 623 dimensions (for 32-bit values). Note that this means, by default, that there is negligible serial correlation between successive values in the output sequence.
· Runs faster than all but the least statistically desirable generators.
· Is statistically random in all the bits of its output.
The above is why, as people have learned about the Mersenne Twister PRNG, that it has increasingly been accepted as the random number generator of choice for all statistical simulations and generative modeling. It's also why BugsysClub chose to use the Mersenne Twister PRNG.
Reference:
· M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.

Shuffling of Cards

The use of a fair and unpredictable shuffle algorithm is critical to a fair poker game. The three goals of a shuffling algorithm are: correctness, lack of bias, and lack of predictability.
Correctness means that cards don't appear more than once. Lack of bias means that without knowledge of the state of the random-number generator, at any given time when there are N cards remaining in the deck, the likelihood of any given card being chosen is 1/N. And Lack of predictability means that when denied direct access to the state of the random number generator, an observer will not be able to predict the next card with a likelihood greater than 1/N (or less than 1/N either).

The Shuffle:

BugsysClub Poker uses an incremental Knuth shuffle. The problem some other sites have noted with the Knuth shuffle (introduction of a bias towards lower numbers) is actually a problem with their random_range function used to generate a number between 0 and 51 from the number their PRNG gave them, which is why they needed to shuffle several times.

In our case, our PRNG (the Mersenne Twister) gives us a random number between 0 and 2^32 - 1 (a bit over 4 billion). We also do not use the random_range function others use. We use one which is free of bias, and uses a simple and reliable algorithm. For example, if we need a random number in the range 0-25: the seed is now between 1 and 2 to the 19,968 power.

-- We take 5 random bits and convert them to a random number 0-31. This is valid because the Mersenne Twister PRNG is statistically random in all the bits of its output.
-- If this number is greater than 25 we just discard all 5 bits and repeat the process

This method is not affected by biases related to modulus operation for generation of random numbers that are not 2n, n = 1,2,...

So the net of the above is that there's no need for us to shuffle multiple times.

Because BugsysClub Poker uses the Mersenne Twister PRNG and the incremental Knuth shuffle (with a range function that is free of bias) you are guaranteed that you will receive a 'true' shuffle for any given hand.

Finally, very different than other online poker sites, this Software has dealt over 13million hands at the time of launch and has had several thousands of real players enjoying a great game of poker before it was launched on BugsysClub.

Hand Logs

We maintain a Hand Log database of every hand and action that takes place on the software.
We use this information to:

· Protect against cheating. In this way, our experts can examine suspicious occurrences for evidence of collusion or other forms of cheating. Go to Collusion for further information on how BugsysClub Poker detects collusion.

· Conduct research. When we perform research, no individual is identified. The data gathering process is automated to further assure privacy of players. For example, we may use computer programs to scan our database to determine what games are most popular.

To forward hand histories at a player's request.