Main Article 7Z72 by Richard Pavlicek
In my article Mapping Bridge Deals I showed how every number from zero to D-1* can be mapped to a unique bridge deal, and that every bridge deal can be encoded as a unique number in that range. In other words, there is a one-to-one correspondence between every possible deal and its number.
*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! × (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: ~2.058 × 1033 = 2058009868335972036308496616883640|
The preceding table shows there are over 2 decillion balanced endings (including full deals), which is more than 38,000 times the number of full deals. In hexadecimal, this is 6577 BC87 87C3 6425 0B71 123D 85B8, which requires 111 bits, or 14 bytes with 1 bit unused. I will refer to this total as N. The 13 numbers that comprise N will be referred to as an array N[J], where the index J represents the number of cards in each hand.
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 K, the continued calculations of partition size X always produce integers. Or at least I hope so (ha-ha).
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.
The preceding mapping method has a caveat. It does not include unbalanced endings, which are often necessary to diagram a single hand or a pair of hands (other hands being blank). Unbalanced endings are also sometimes used to indicate a mid-trick position, e.g., when one or more players have yet to play to the current trick (personally, I avoid this practice since the ending can always be diagrammed in a balanced manner with an adjusted explanation). Another use (at least for me) is to store a template of fixed cards for creating random deals within specified constraints. Therefore, for a mapping algorithm to be practical, it should include unbalanced endings as well.
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 ~1.068 × 1036 or 1,068,380,067,768,858,063,542,620,835,042,803,325 to be exact. 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 × 1036 or 2,220,446,049,250,313,080,847,263,336,181,640,625 to be exact. 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: There it is, folks! North has 32 cards; East and West each have 10. North opened 1 NT (what else with a flat 8-8-8-8) and South didnt know what to do with his entryless, cardless hand, so he transferred to hearts. Luckily, he caught his partner with an eight-bagger. (OK, OK, Ill stop.)
Despite the larger number of cases, the power of 5 mapping scheme is much simpler to implement. The calculations are also faster, with only one multiplication (or division) per loop. Further, the algorithm is easy to understand:
|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.
A nice feature of the power-of-5 algorithm is that there is no concern about whether it works. The logic is so obvious and intuitive that it has to work. In my Mapping Bridge Deals study, I estimated that a million computers testing a million deals per second would take over a billion years to test the algorithm on every deal. Well, that was peanuts. For bridge endings, it would take over 40 quadrillion years. Good to know. Kind of like the monkey at a typewriter hitting random keys infinitely, eventually producing the complete works of Shakespeare. Mind boggling, indeed.
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 needed in a bit-mapping scheme. 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 additional information.
To make this faster and simpler for computer programs, I decided to encode each suit separately. This requires only 513 or 1,220,703,125 values per suit, or 31 bits, which neatly fits a 32-bit computer word. I use the extra bit as a flag: 0 = standalone suit, 1 = part of a deal. For details see my ZBS Format.
© 2001 Richard Pavlicek