Main Article 7Z72 by Richard Pavlicek
*D = total number of bridge deals = 53,644,737,765,488,792,839,237,440,000 = AD55 E315 634D DA65 8BF4 9200 hex (96 binary bits).
Now suppose one wished to map bridge endings as well, i.e., four-hand diagrams with fewer than 13 cards in each hand. First I will consider balanced endings, where each player has the same number of cards. Is it possible to number each ending and have a similar one-to-one relationship? Well, it has to be possible; so the real question is how to approach it.
One of the reasons for mapping deals and endings is to be able to store the information in the fewest number of bits. For example, a full deal is typically stored in 104 bits*, but the deal mapping process allows any deal to be stored in 96 bits. This is clearly the smallest possible storage space since the total number of deals is a 96-bit number. Hence, it would be impossible to distinguish every deal in 95 bits or less.
*The location of each card is determined by two bits. The four distinct values of the two bits (00, 01, 10 or 11) indicate which player (North, East, South or West) gets that card.
There are many more bridge endings than there are bridge deals. A lot more! The normal method (at least for me) of storing bridge endings is to use three bits per card. One bit determines whether the card is used, and the other two bits indicate which player gets the card (if used). While simple, this method requires 156 bits. Obviously, it is wasteful in storage efficiency; but just how many bits are really needed? In order to answer this it is necessary to calculate the number of bridge endings.
To get started, lets consider an ending with a specific number of cards in each hand, say, seven. How many seven-card endings exist? I am not concerned whether the ending is legal, i.e., reachable from a full deal with only legal plays (no revokes). For the sake of this discussion, any combination of cards may be held by any player.*
*The task of counting only legal bridge endings is beyond comprehension to me. Im not even sure how to approach it, let alone that there may not be enough computing power on earth to carry it out. But I could be wrong.
Determining the number of seven-card endings is easily done with combinatorial arithmetic, similar to the way of counting the number of full deals. The first hand can be obtained in 52c7 ways. The second hand, in 45c7 ways; the third hand in 38c7 ways; and the fourth hand in 31c7 ways. Note that, unlike a full deal, the third hand does not determine the fourth, so the fourth combinatorial factor is required. Multiplying these together gives the total number of seven-card endings:
24! x (7!)4
This number is almost four times larger than the total number of deals. The number of eight-card endings is several orders of magnitude larger; nine-card endings, much greater still; and 10-card endings, the most of all. The following table shows the exact number of endings for each number of cards. The Denominator column shows how each number was calculated (the numerator is always 52!). The table also includes 13-card endings (full deals) since the objective is to derive a general method to map all endings.
|Cards||Denominator||Number of Endings|
|12||4! x (12!)4||63839473138338558845060855160000|
|11||8! x (11!)4||787961497021778783459036840832000|
|10||12! x (10!)4||971089585681469963688868551062400|
|9||16! x (9!)4||222319044340995870807891151800000|
|8||20! x (8!)4||12544162796020587447287356785000|
|7||24! x (7!)4||201474727133525966905424640000|
|6||28! x (6!)4||984413552803410351119097600|
|5||32! x (5!)4||1478262843475644020034240|
|4||36! x (4!)4||653534134886878245000|
|3||40! x (3!)4||76277828779152000|
|2||44! x (2!)4||1896396138000|
|1||48! x (1!)4||6497400|
|Total Number of Endings:||2058009868335972036308496616883640|
In theory, every number from zero through N-1 should represent one and only one ending, and every ending should be represented by a number in that range. Suppose you are given a number (call it I) from zero to N-1. Below is my algorithm to convert this number to its unique ending.
|1. C=52; J=13|
|2. K=N[J]; If I < K, go to 4|
|3. I=I-K; J=J-1; go to 2|
|4. N=E=S=W=J; U=52-4*J|
|5. X=K*N/C; If I < X then N=N-1, go to 10|
|6. I=I-X; X=K*E/C; If I < X then E=E-1, go to 10|
|7. I=I-X; X=K*S/C; If I < X then S=S-1, go to 10|
|8. I=I-X; X=K*W/C; If I < X then W=W-1, go to 10|
|9. I=I-X; X=K*U/C; U=U-1|
|10. K=X; C=C-1, loop if not zero to 5|
Line 1 initializes the card count (C) at 52, and the index (J) at 13. By starting with full deals, the algorithm interprets numbers from 0 to D-1 in the same way as my deal mapping algorithm. Higher numbers (through N-1) will represent non-full deals.
Line 2 sets K to the current value N[J] and checks if I is less than K. If so, the proper index (cards per hand) has been found and it proceeds to Line 4; if not, I is reduced by the value K, the index is reduced by 1, and it returns to Line 2 to check again.
Line 4 initializes each players card count (NESW) to the index J, and the unused card count (U) to 52 minus four times the index J. Note that in the special case for a full deal, U becomes zero (52-4*13), which makes the remaining part behave just like my deal mapping algorithm.
The loop beginning at Line 5 is executed 52 times. On each iteration, the number K is divided into five partitions in the ratio N:E:S:W:U. If I falls in the first partition the card goes to North; in the second partition, it goes to East; in the third, to South; in the fourth, to West; and the fifth partition means the card is unused. The counter is decremented for whoever got the card (NESWU). The size of the selected partition (X) represents all remaining endings with that card so placed. The selected partition becomes the new space K for the next loop. Once each position (NESWU) becomes full, its counter is zeroed, so future partitions for that position become null; hence, it cannot receive any more cards.
Due to the composite makeup of the number K, the continued calculations of partition sizes (X) always produce integers. Or at least I hope so (hehe).
Now suppose you want to reverse the procedure. That is, given any balanced ending (including full deals), determine its number I. This is done with a similar algorithm:
|1. C=52; J=13; I=0|
|2. K=N[J]; If number of cards = J, go to 4|
|3. I=I+K; J=J-1; go to 2|
|4. N=E=S=W=J; U=52-4*J|
|5. X=K*N/C; If card is North then N=N-1, go to 10|
|6. I=I+X; X=K*E/C; If card is East then E=E-1, go to 10|
|7. I=I+X; X=K*S/C; If card is South then S=S-1, go to 10|
|8. I=I+X; X=K*W/C; If card is West then W=W-1, go to 10|
|9. I=I+X; X=K*U/C; U=U-1|
|10. K=X; C=C-1, loop if not zero to 5|
The number I starts at zero. Lines 2 and 3 adjust I to the lowest number for the appropriate number of cards (zero for full deals, D for 12-card endings, etc.). Once this is determined, it enters the main loop which, on each iteration, adjusts I to the base of the partition to which the current card belongs. The partition sizes are apportioned as before according to the running counts. Intuitively, this should build a unique number I for each ending.
In thinking about the best approach, the varying number of cards is a hurdle. Each hand could have any number of cards from 0-13, which makes 38,416 cases (14 to the fourth power) compared to 13 cases for balanced endings. The number of endings for each case could be figured separately, and similar algorithms used; but this is hardly sensible. Imagine having to store (or compute each time) 38,416 numbers (most of them huge) just to encode or decode an ending.
To calculate the number of unbalanced endings, I evaluated and summed each of the 38,416 cases. (Ill spare you the table.) The total is over 1 undecillion (37 digits) or to be exact: 1,068,380,067,768,858,063,542,620,835,042,803,325. In hexadecimal this is 00CD C334 4730 7D3E 53F6 746B 564F BE7D, which comprises 120 bits. This means that every possible ending could be mapped and stored in 15 bytes. Unfortunately, it wouldnt be easy.
For practical purposes, I decided on a different approach. Since each card can go in any one of five places (North, East, South, West or Unused), why not work with powers of five? For example, the first card is assigned a number 0-4 according to its location; the second card adds 0,5,10,15 or 20; the third card adds 0,25,50,75 or 100; and so forth. How big does this get? Well, it obviously becomes 5^52, which is over 2 undecillion, or 2,220,446,049,250,313,080,847,263,336,181,640,625. In hexadecimal this is 01AB A471 4957 D300 D0E5 4920 8B31 ADB1, which comprises 121 bits.
The reason this number is larger is because it also includes endings where a player has more than 13 cards. While this appears to be useless, it could have a purpose if you wished to store a fouled board (e.g., North with 14 cards and South with 12) or any silly layout for that matter. I can imagine my next bridge article already: There it is, folks! North has 32 cards and East has the rest. North opened 1 NT (what else with a flat 8=8=8=8), and South didnt know what to do with his entryless (and cardless) hand so he transferred to hearts. Luckily, he caught his partner with an eight-bagger. (OK, OK, Ill stop.)
|1. C=52; X=1; I=0|
|2. If card is unused go to 7|
|3. I=I+X; If card is North go to 7|
|4. I=I+X; If card is East go to 7|
|5. I=I+X; If card is South go to 7|
|6. I=I+X; (card must be West)|
|7. X=X*5; C=C-1, loop if not zero to 2|
In effect, this just creates a base-5 number of 52 digits, with digits 1-4 indicating which player (NESW) has the card (or zero meaning the card is unused). What could be simpler than that?
Reversing the process is just as easy. To determine the bridge ending represented by a number (0 to 5^52-1) the algorithm is:
|3. Remainder 0 indicates the card is unused.|
|4. Remainder 1-4 indicates the owner (NESW).|
|5. C=C-1, loop if not zero to 2|
It is also convenient that Ending Number 0 is exactly that, a null diagram with no cards in any hand.
One slightly annoying aspect of this scheme is that it requires 121 bits (rather than an even 120, or 15 bytes), but its still quite a savings over the 156 bits I currently use. The odd bit is no great concern since any efficient storage method would allot 16 bytes per diagram, so the extra seven bits can be used to store other information.
© 2001 Richard Pavlicek