Dealing All the Deals

Introduction 

When people play bridge, they deal the cards into four hands by the following method:

1)     The deck of cards starts in an unknown order.

2)     The dealer shuffles the cards imperfectly to mix them.

3)     They deal the cards from the top of the deck to each hand in turn until they have dealt all the cards. 

Computer-generated deals (used in tournaments and bridge-playing programs) are dealt in a similar fashion.  The computer mixes the deck (which generally starts out sorted) by exchanging the cards in various positions with other cards in various positions.  It does this many times (hundreds) and uses a pseudo-random number generator to select the cards to be exchanged.

The difference between these two methods is that while a human can’t shuffle the cards perfectly, the computer always does.  Computers use functions called pseudo-random number generators (pRNG) to simulate random events.  These are initialized using a starting number or seed.  Given the same seed for its pseudo-random number generator, a pRNG will always produce the same hands from a shuffle.  Also, because of the unpredicted result of a shuffle, it may also produce the same deal from a number of  different seeds.

The possible number of bridge deals is given by:

N_bd = (52!)/(13!)⁴ = 5.3644 x 10²⁸.

In binary form, this is a 96-bit number.  Thus, in order to produce any of all possible bridge deals, neglecting the duplication of deals mentioned above, the pRNG must use at least a 96-bit seed.   I have never heard of this being done.  The ACBL reportedly uses a 47-bit seed for their tournament deal generator[3].   This means they’re using a tiny subset of the possible bridge hands to produce tournament deals.  (Which ones are they leaving out?  No one knows!)

This paper proposes a method for selecting deals from the complete set of all possible bridge deals.  The process is divided into two parts:

1)     numbering the bridge deals and

2)     random deal selection.

Part 1 - Numbering Bridge Deals

The method proposed here specifies a system of numbering bridge deals such that:

·       For every number between 0 and (N_bd-1), a specific, unique bridge deal is produced, and

·       For every legal bridge deal, a unique number in that range can be assigned.

There are many ways to produce all deals.  The method used here is the following:

1)     Start with an ordered deck.

2)     Select a 52-bit number which has exactly 26 zeros and 26 ones.

3)     Divide the deck into two 26-card piles by assigning half to one pile (the even pile) and half to the other (the odd pile) using the array of  52 bits to assign each card to a pile.

4)     Select a 26-bit number which has exactly 13 zeros and 13 ones.

5)     Divide the even pile into two 13-card hands using these 26 bits to assign cards from the even pile.

6)     Repeat steps 4) and 5) for the odd pile.

The selected numbers referred to in steps 2) and 4) above are conceptually selected by taking the xth number in a complete, ordered list.  I will use the notation  N_26:13 to mean a number from the set of all 26-bit numbers having exactly13 bits set.

Using a bit array to assign cards means that each bit (either a ‘1’ or a ‘0’) places a card into one of two piles.  If the number selected in step 2) is selected from the set of all N_52:26, then any card can end up in either pile, and all possible equal splits of the cards can be selected.  The number of such splits (‘deck splits’)is given by:

N_ds = 52!/(26!)²  =495,918,532,948,104

which is exactly the number of  N_52:26  numbers.   (See Appendix A for tables of number sets)

The same method is used for the two 26-card piles.  The number ways we can divide 26 cards into two equal piles (‘pile splits’) is given by:

N_ps = 26!/(13!)² = 10,400,600

which is also the number of  N_26:13  numbers.

Dealing

To assign a deal to a specific number, we do the following:

Given deal number D, compute:

P_odd = D mod N_ps

                        P_even = (D div N_ps) mod N_ps

                        S = D div (N_ps)²

Start with a sorted deck (first card is A of Spades, last is 2 of Clubs).  Using S, we select N_52:26(S) and use it to divide the deck into two piles.  Using the P’s, we select the two 26-bit numbers ( N_26:13(P_even) and N_26:13(P_odd) ) and use them to divide each pile into two hands.

Numbering a Deal

To assign a number to a specific deal, we do the following (inverse) operation:

Construct a 52-bit number by setting a bit for each card found in the East-West hands or resetting it if the card is in the North-South (the A of Spades is bit 0).  Construct two 26-bit numbers (one for North-South, one for East-West) by setting a bit for each card assigned to that pair that is also assigned to the higher (South or West) hand or resetting it for the other hand.  These two numbers are formed by appending bits on the right (LSB) side.

Find the position of the 52-bit number in the set of all N_52:26.  This is S.  Find the positions of the 26-bit numbers in their sets, these are P_even (for the North-South hands) and P_odd (for East-West).  These three numbers are combined to form the deal number as:

D = ((( S x N_ps) + P_even) x N_ps) + P_odd

Handling Huge Number Sets

Implementing this system requires producing and finding entries in sets of numbers.  The numbers and positions used are:

1)     Find the N_26:13 given its position in the set.

2)     Find the N_52:26 given its position in the set.

3)     Find its position given N_26:13.

4)     Find its position given N_52:26.

This usage invokes a concept of an ordered list of numbers that can be indexed and searched.  In practical terms, this is impossible.  The list of N_26:13 contains 10 million numbers.  The list of N_52:26 contains 4.95 x 10¹⁴.  Lists that size are too large to implement on computers we use today.  Nonetheless, the values and their positions can be derived by decomposing the numbers into smaller chunks to implement these four functions. (See Appendix B for more details.) 

The combination of these functions and the methods described here were used to program the two required functions:

1)     Given N [in the range of 0 to (N_bd-1)], produce the Nth bridge hand.

2)     Given a bridge hand, find its number N in the range of  0 to (N_bd-1).

The program ‘RndDeal6’, which is available here, demonstrates these two functions.

Part 2 – Random Deal Selection

There are plenty of ways of selecting one of our set of bridge hands, but one of them isn’t

“Pick a number between 0 and 53,644,737,765,488,792,839,237,439,999.”

To pick a hand at random, we need a 96-bit number that is smaller than N_bd.  To set up 36 hands (the usual number for a tournament event) we need 36 96-bit numbers.  We can get these in two distinctly different ways, depending on the use.  If we need a deterministic sequence (i.e., one that’s repeatable), we can seed a suitably-wide pseudo-random number generator (pRNG) with a 96-bit seed derived from some event or phrase.  If we don’t need repeatability, we can use a true random number generator (RNG) like the one implemented on most modern PC’s.  That will give us actual random deals.

Pseudo-Random Number Generators

When you need to repeat a deal or sequence of deals, you need a good pRNG to generate the hand numbers.   It must have a period of at least N_bd and generate uncorrelated 96-bit numbers.   One that appears to have application here is the Secure Hashing Algorithm (SHA) driven by a text generator.  SHA is a function that ‘digests’ a text string to produce a pseudo-random 160-bit number.  It was developed by the National Security Agency and the National Institute of Standards and Technology for use in digital signatures.  It’s pseudo-random, but unpredictable by design.  I’ve implemented and tested it with a text generator with excellent results.  Briefly, it works this way:

·       Enter a string of 20 or more characters (e.g. ,“Let’s all have a good time”).

·       For each hand, add the words describing the hand number (“one”, “two”..).

·       Hash the resulting string using SHA.   This gives you a 160-bit number: H.

·       Compute D = H mod N_bd.  This is the deal number.

The attractive feature of this method is that the seed is humanly useable.  Of course, any text string would work, and it can be extremely long.

For much more about SHA, see [1].

Hardware Random Number Generator

When there is no reason to repeat the deals generated, a true random number generator seems like an ideal choice.  No seed is required, and the results are as random as the noise used to generate the numbers.

Beginning in about 1999, Intel^® added circuits to their chipset to support generation of true random numbers.[2]  The circuits measure the amplified voltage across a resistor and use the thermal noise as a signal source.  Programmers can access the output of this device or  request it from the Cryptographic API.  Using the latter method,  a specified number of bytes of random data is returned from the function call. 

The generator must sample the noise to provide the data, so this process takes time –about 5 milliseconds per byte.  Since we need 96 bits (12 bytes) to identify each deal, a run of 36 deals would require about 2.2 seconds.  That’s certainly acceptable, but a study of 1 million random deals would take 17 hours worth of noise to satisfy!

Conclusions

 If we could place all the possible bridge deals in a big barrel, shake it up real good, and pick out a few to play, most people would agree that these would be random deals.  The methods described here provide the hands on little slips of paper, and way to choose some at random.  Although the implementation is far from intuitive, it’s demonstrably accurate and, used with a true random number generator, unbiased.

Any method of mechanically producing bridge deals needs to be scrupulously ‘clean’ to instill a sense of fairness in the players.   This is true for all uses, but especially when hands are used in competition.  It would be very difficult to demonstrate that the subsets of deals generally used are not representative of the possible hands.  It seems probable that they are unbiased.  It is trivial to demonstrate that they are subsets.  The argument for choosing truly random deals from the set of all those possible rests in the elimination of any possible bias, and the relative simplicity of implementing it. 

Recommendations 

I have two specific reccomendations resulting from this study.

1)    Computer-generated deals which do not require repeatability should use a hardware (true) random number generator for hand selection or shuffling.  The easy availability of a proven device reduces the need to really study this.  Most computers already have this hardware.

2)    Computer-generated deals should use  a method that allows selection of all possible deals.  One such method is proposed here; many could be designed.   You need a 96-bit number to be able to select any bridge deal.

John Christman
 December 2001

References

 1. Bruce Schneier , Applied Cryptography,  John Wiley & Sons, Inc.  1994

2. Accessing the Intel^® Random Number Generator through a CSP for Microsoft CryptoAPI,  Intel Corporation  1999  www.intel.com

3. Paul Linxwiler, Computer-dealt hands:truly random or impishly fixed?  ACBL website,  www.acbl.org

Appendix A - Tables

Table 1 - Table of 13-bit Numbers

Table 2 -Table of 26-bit Numbers

Appendix B – Implementation Topics

In order to develop and test the ideas presented here, I developed a library of functions and several programs to explore the numbering system, and random deal selection.  (The program downloadable from the web site (RndDeal6.exe) is one of these.  It allows the interested user to explore a demonstration of the final results of all this math.)

As usually happens, investigating the problem (the numbering problem here) produced refinements in the algorithms, structures and methods.  The following describes one such aspect.

 Finding Numbers in a Bit-Count Set

Finding numbers in the set of all 26-bit numbers with 13-bits set is a challenging task.  After all, there are 10 million of them!  Consider the simpler problem of finding 13-bit numbers with n bits set.  There are 8192 13-bit numbers.  If you count the number of bits in each of them, you can create an ordered list of numbers for each bit-count from 0 to 13.  If you need the 231^st 13-bit number with 6 bits set,  it’s item 231 in that list.  Table 1 in Appendix 1 lists the populations for each bit count.  Table 2 shows the same data for  26-bit numbers.  These too can be counted, but storing them would be much more difficult.   By decomposing 26-bit numbers into an upper 13 bits and a lower 13 bits, they can be derived from the smaller table.

We will order the numbers such that the upper bits would have 0, then 1, then 2, 3,4,5,6,7,8,9,10,11,12,13 bits set, in all possible positions while the lower half would have the required number  (13, 12, …1,0) set in all possible configurations, with the lower changing faster. 

Example:

  Suppose you need the  5,000,000^th 26-bit number with 13 bits set.

The third column on Table 1 shows the number of combinations used when the upper half ends that series.  For 5,000,000 we can see that after 5 bits in the upper half, 2,255,644 numbers have been listed.  After 6 bits in the upper half, 5,200,300 have been listed.  We need to have 6 bits in the upper half, and the rest (7) in the lower.  And we need the number that is (5,000,000-2,255,644=2,744,356 ) positions  beyond the start of the 6-bit upper half numbers.  There are 1716 different 13 bit numbers with 7 bits set (Table 1, 2^nd column).  Dividing the position increment we need (2,744,356) by 1716 gives us 1599 with a remainder of  472.  The quotient gives the upper half position (in the 6-bits-set table).  The remainder is the lower half’s position (in the 7-bits-set table).  We can look these up in the 13-bit tables and combine them to form the 5,000,000^th 26-bit number with 13 bits set.  

(I haven’t included that table here, so we can’t actually look them up.  N_13:6(1599)=7182,  N_13:7(472)=2843,  and
 N_26:13(5,000,000)=58,837,787.   [In hex = 1C0E,  0B1B, and 0381CB1B] )

Well, that’s pretty tedious for humans with a calculator, but of course computers breeze through these computations.  I coded and debugged the two functions:  

Find26(nbits,p)  which returns the pth 26-bit number with nbits bits set

and      Pos26(nbits,N)   which returns the position of N in the set of 26-bit numbers with nbits bits set.

The logical way to test these, since they are inverse functions, is to check for identity if they’re applied in tandem.  The code looks something like:

            For b=0 to 26
                                    For I=0 to (number of entries in set b)
                                                if  (Pos26(b, Find26(b,I) )<>I) then declare an error

This runs both routines through all possible values, a total of 2²⁶  (67 million) tests.  It takes about 80 seconds to run on my PIII-600MHz PC.

Notice that these two functions work for any number of bits set in a 26-bit number.    That’s because they’re used to implement the same type of function on 52-bit numbers with 26 bits set.  The process is similar and there are two functions:

            Find52(p)        which returns the pth 52-bit number with 26 bits set

and      Pos52(N)         which returns the position of N in the set of 52-bit numbers with 26 bits set.

These can be tested easily by running in tandem, but not exhaustively, since there are too many values (about 500 trillion).   Running with random number inputs, 10 million numbers ran through both functions in 70 seconds.

 Appendix C  Number Theory –Integer Operations

Two of the operations used in this description are uncommon enough to warrant definition.  These integer operations use only whole numbers—no fractions or decimals.  

Integer Division

Everyone already knows about integer division, since it’s the way we learned about division in elementary school:  “7 divided by 2 equals 3 remainder 1.”

Integer division is doing this without concern about the remainder. 

                        7 div 2 = 3           13 div 4 = 3      5 div 6 = 0

The notation is different than ordinary division since we want an integer result ( 7 ¸ 2 = 3.5 would not work).

Modulo Function

The modulo function is the remainder of an integer division.

                        7 mod 2 =1         13 mod 5 = 3         12 mod 3 = 0  

Note that the result of    x mod n   is always less than n.  In fact, it’s always a number in the range from zero to one less than n.