Study 7Z68 Main

Mapping Bridge Deals

by Richard Pavlicek

Before I explain my mapping process, let’s consider the number of possible bridge deals. It’s an enormous number, but it is easily calculated with combinatorial arithmetic. The formula for the number of combinations of N items taken R at a time is given by:

N!/R!(N-R)!

The notation N! (N factorial) is the product of all integers from 1 through N, e.g., 6! = 720.

First, let’s use this formula to determine the number of bridge hands that can be dealt to one player. Setting N=52 and R=13, the calculation becomes:

52!/13!×39! = 635,013,559,600

This is the number of possible bridge hands, but we still haven’t constructed a full deal. Now consider the second player. Only 39 cards remain, so the number of combinations is obviously fewer. Setting N=39 produces:

39!/13!×26! = 8,122,425,444

This is the number of possible hands a second player can receive after the first player’s hand is determined. For the third player only 26 cards remain, so it becomes:

26!/13!×13! = 10,400,600

This is the number of possible hands for the third player. Only 13 cards remain, which perforce go to the fourth player; i.e., once you have determined any three hands, you have a unique bridge deal.

The number of possible bridge deals is calculated by multiplying the above three numbers. Note how the factors 39! and 26! neatly cancel out to leave:

52!/(13!)⁴ = 53,644,737,765,488,792,839,237,440,000

That’s 53+ octillion if you began to say it, but I never want to write this number again, so from here on I will it D — for “Deals” or “Damn, that’s big” (pick one).

Study 7Z68 Main Top Mapping Bridge Deals

Mapping a Number to a Deal

Now suppose you are given a number, ranging from zero to D-1. Intuitively, this should represent one and only one bridge deal, which should be different from the deal produced by any other number. In other words, there should be a one-to-one correspondence between each number and its deal. The first task is to map the number (call it I) to the specific deal it represents.

My algorithm is outlined below. Line 1 initializes the vacant slot count for each player (NESW), the total number of cards (C) and a variable K which tracks the “space” into which all the remaining card distributions must fit. The loop beginning at Line 2 is executed 52 times, once for each card which is given to the player whose counter is decremented.

1. N=E=S=W=13; C=52; K=D
2. X=K*N/C; If I < X then N=N-1, go to 6
3. I=I-X; X=K*E/C; If I < X then E=E-1, go to 6
4. I=I-X; X=K*S/C; If I < X then S=S-1, go to 6
5. I=I-X; X=K*W/C; W=W-1
6. K=X; C=C-1, loop if not zero to 2

To understand it, consider what happens on the first iteration to place one card, say the spade ace. The first value of K is equal to D and N/C (13/52) is equal to 1/4, so I’m dividing the space into four equal parts:

0……………………X……………………X′……………………X′′……………………D

If the number I is less than X, then the spade ace goes to North, and the space from 0 to X must represent all the possible deals where North holds the spade ace. Hence, the remaining 3/4 of the space is discarded (the spade ace would belong to East, South or West) and the next space K is set to X.

If the number I falls in the range: X <= I < X′, then the spade ace goes to East. Now we must discard the space below X, as well as the space from X′ and above. For ease in calculation, the new space is aligned at zero and the number I is reduced accordingly to keep its relative position. Similar logic applies when I falls in the upper regions, giving the card to South or West.

On subsequent iterations the space is not divided into fourths but into portions that are proportionate to the number of vacant slots left for each player. In each case the size of the portion represents all the possible remaining deals if the current card went to that player. The number I determines which portion is chosen, the card goes to that player, and that portion becomes the new space. When a player runs out of vacant slots the size of his portion calculates to zero.

It is enlightening to note that repeated calculations of the variable X will always produce integers due to the makeup of D. I wanted to exploit this further by calculating K/C at the beginning of each loop (since the ratio is used up to four times) but this interim step can be a fraction that is removed on later multiplication. Therefore, to avoid complications in implementing the algorithm, I multiply first.

Study 7Z68 Main Top Mapping Bridge Deals

Mapping a Deal to a Number

Now suppose you want to reverse the process. That is, given a specific deal, determine its number I. This can be done with a similar algorithm:

1. N=E=S=W=13; C=52; K=D; I=0
2. X=K*N/C; If N card then N=N-1, go to 6
3. I=I+X; X=K*E/C; If E card then E=E-1, go to 6
4. I=I+X; X=K*S/C; If S card then S=S-1, go to 6
5. I=I+X; X=K*W/C; W=W-1
6. K=X; C=C-1, loop if not zero to 2

The number I starts at zero. If the first card (spade ace) belongs to North, I is unchanged; if it belongs to East, I is increased by the space necessary to represent all the deals where North held the spade ace; if it belongs to South, I is increased by North’s and East’s space, etc. In other words, on the first iteration I is set to the base of the quadrant for the player who holds the spade ace, and that quadrant becomes the new space K.

On subsequent iterations the space is apportioned according to the number of slots remaining for each player, and I is increased by the distance to the base of the portion for the player who has that card. Intuitively, this should build a unique number for each deal.

Note that the number I remains at zero if the first 13 cards were held by North, the next 13 by East, and the next 13 by South. Conversely, it reaches the maximum (D-1) if they were held by West, South, and then East. Otherwise, it would fall somewhere in between.

Study 7Z68 Main Top Mapping Bridge Deals

Testing the Algorithms

The major difficulty in testing these algorithms is the unwieldy arithmetic, though it is easy to implement by computer. Consider the number D. This translates to 96 binary bits or 12 bytes, which is a convenient size to work with. In hexadecimal (base 16) it is:

AD55 E315 634D DA65 8BF4 9200

What about the order of cards? I order them by rank ( A, A, A, A, K, … 2) but this doesn’t matter as long as it’s the same for both algorithms.

I have implemented these algorithms using my own 96-bit math routines and tested them many times. One procedure is to choose a random number and create a deal with the first algorithm, then use that deal to generate a number with the second algorithm. Did the numbers match? Yes, every time. I have also tested in reverse fashion (deal to number, then number to deal) and the deals matched as well, so I’m convinced the algorithms work.

Of course, one still must rely on theory here, because there is no way to test every deal. Imagine this: If you had a million computers, and each tested a million deals per second (an amazing performance) it would take over a billion years — 1,701,063,475 to be exact. Mind boggling, no? (Okay, okay, it would actually be a little less since I ignored leap years.)

Acknowledgment: Thanks to Thomas Andrews for his help in correcting flaws in my first attempt to write the number-to-deal algorithm. Thomas has tackled this project using a completely different method in his Impossible Bridge Book.

Study 7Z68 Main Top Mapping Bridge Deals