Main Study 8H11 by Richard Pavlicek
Have you ever faced the problem of escaping handcuffs after a police bust? Or removing ankle chains during a prison break? Or just getting out of a straightjacket at your local ward? Well, youve found the right place! Dealing with constraints requires foresight and a scientific mind. Always carry an up-to-date set of lock picks, a tube of salve, and a copy of my latest book The Bust Stops Here.
Oh, wait. My bad. This study is about creating bridge deals with constraints. For example, deals where West has six hearts, or North has a balanced hand, or East has a two-suiter but otherwise truly random. The simple solution, undeniably perfect, is to create plain random deals and select only those that meet the desired criteria.
The deal-and-select method, however, runs into problems when the constraints become stringent, e.g., if South requires a 9-card suit, or if multiple hands must be constrained. The simple method may work, but it could take thousands (millions) of attempts to produce one deal. Indeed, extreme constraints could take a lifetime or a million lifetimes for that matter.
Years ago, circa 1999, I devised a solution to this problem (Randomization Techniques) to create bidding practice deals. While serving a useful practical purpose, it missed the mark on being truly random, because it did not properly account for interdependence between hand patterns and HCP. Close is not good enough for theoretical work, so if at first you dont succeed
There are many ways to create a random deal. Most obvious is to form an array of 52 elements representing each card by position, with 13 assignments for each player. For example:
|W W W W W W W W W W W W W N N N N N N N N N N N N N E E E E E E E E E E E E E S S S S S S S S S S S S S|
Then simply randomize the order. This is unquestionably perfect, as long as the random number source is perfect.*
*Arguably there is no such thing, but this study is not about random number generators and will assume a reliable source.
When dealing with constraints, the above method is virtually useless. Instead, the process is to determine the pattern of each constrained hand. To illustrate, suppose you want to create random deals where West has nine spades a good way to boost your bidding confidence or land you in the nut house (pick one). First make a list of the specific West patterns that comply, including the number of hands for each, as shown in the following table:
|Case||Pattern||Calculation||Number of Hands||Cumulative Total|
|15||9=0=0=4||13c9·13c0·13c0·13c4||511225||T = 58809465|
The next step is to select the pattern. To do this fairly, the chance of selecting each pattern must be weighted by the number of hands it represents, which is calculated as shown. Obtain a random number from 0 to T-1, where T is the total number of hands, then find where this number lies in the cumulative totals. If the random number is less than 9425130 select 9=2=1=1; if less than 18850260 select 9=1=2=1, etc. Intuitively, this will choose a random pattern by exact theoretical odds.
If thats the only constraint, the rest is easy. Suppose Wests pattern was chosen to be 9=1=2=1. Complete the West hand by randomly selecting nine spade ranks, one heart, two diamonds and one club. Whatever cards remain are distributed randomly among the other three hands, and youre done a truly random deal with West having nine spades.
That was easy. Now suppose an additional constraint is for East to be 6-6 in the minors. It is not sufficient to choose the West hand first with nine spades and work from there, because of the interaction of the two conditions; i.e., each affects the probabilities of the other. Instead, the list must pair each West pattern with each East pattern, including the combinations thereof, as shown below:
|30||9=0=0=4||0=1=6=6||13c9·13c0·13c0·13c4·4c0·13c1·13c6·9c6||957970213200||T = 556991252532000|
Note that the basis for calculating the second hand (East) changes from 13 to the number of available cards in each suit when paired with that West shape. The combinations now represent sides rather than hands, but the principle is the same. Each of the 30 possible sides is weighted exactly by its probability of occurring, so a random number from 0 to T-1 will make a fair selection. Suppose the random number is 277777777777777. Going down the right column, the first time this is less than the cumulative total occurs at Case 8, so West is 9=2=2=0 and East is 0=1=6=6. Each suit is filled randomly, and whatever cards remain are split randomly between North and South.
The order of the paired hands is irrelevant. For example, in Case 1 if East (6-6 minors) is calculated first, the combinatorials become 13c1·13c0·13c6·13c6·12c9·13c2·7c1·7c1 = 32187799163520, which is exactly the same as the table. Hence, the weightings and total (T) will be identical.
It is feasible to extend the pattern-dealing method to constrain a third hand, however, the effort is rarely beneficial. (Even two hands can produce extensive listings if common shapes are involved.) More practical is to pattern-deal according to the two most-constrained hands, then select only those deals that fit the third hand conditions.
Applying HCP constraints to random dealing is difficult, because HCP in theory is not a number like a hands spade length, but various combinations of specific cards to comprise that number. I am always looking for shortcuts, but I dont think there is a theoretically correct way to generalize the application of HCP constraints. To create a truly random deal, it is necessary to enumerate all hands that qualify and make a random selection thereof the same procedure as above but more complex.
First consider the application of HCP constraints alone, regardless of hand pattern. Suppose you want to create random deals where North has 3 HCP. Each possible arrangement of specific high cards must be enumerated, as shown in the following table:
|Case||High Cards||Calculation||Number of Hands||Cumulative Total|
|7||J J J||36c10||254186856||4509891036|
|8||J J J||36c10||254186856||4764077892|
|10||J J J||36c10||254186856||5619070044|
|17||J J J||36c10||254186856||10128961080|
|24||Q J||36c11||600805296||T = 15636342960|
Only one combinatorial is required in each case; 36 is the total number of spot cards (non-HCP) which is followed by the number of additional cards necessary to fill the hand. The rest is straightforward. Obtain a random number from 0 to T-1 and see where it falls in the cumulative totals. Suppose the random number happens to be 8673163632, which looks very familiar to Case 14. No! It must be below the cumulative total, so Case 15 is selected. North gets the Q and J, and the rest of his hand is filled randomly from the 36 spot cards. All unused cards (including high cards) are then distributed randomly to West, South and East.
Now suppose two hands require HCP constraints. The general strategy is the same, though the listing gets longer, and the numbers larger, because the enumeration represents sides rather than hands. To keep the list friendly, consider a trivial case where North requires 2 HCP and South 0-1 HCP a good way to practice your grand-slam defense, or feed an inferiority complex. Here is the table:
|38||Q||J||36c12·24c12||3384731762521200||T = 122891799377692800|
Note that the combinatorial for the second hand (South) is based on the remaining spot cards, rather than 36. As with pattern dealing, the order of the two hands makes no difference; e.g., if South were chosen first in Case 1, the combinatorials would be 36c13·23c11, which produce the same 16-digit product. Simply fetch a random number between 0 and T-1, find where it falls in the cumulative totals, and bingo, a truly random deal with the given HCP constraints.
Now suppose you want to apply both pattern and HCP constraints. No problem, though it requires more enumeration. Each possible pattern must be listed with each possible high-card arrangement. To illustrate, suppose you want to create random deals where East is 5-3-3-2 with 34 HCP call it slam-bidding practice for morons. The table becomes:
|1||5=3=3=2||A-K-Q-J A-K-Q A-K-Q A-Q||9c1·9c0·9c0·9c0||9||9|
|2||5=3=3=2||A-K-Q-J A-K-Q A-K-J A-K||9c1·9c0·9c0·9c0||9||18|
|3||5=3=3=2||A-K-Q-J A-K-J A-K-Q A-K||9c1·9c0·9c0·9c0||9||27|
|4||5=3=3=2||A-K-Q A-K-Q A-K-Q A-K||9c2·9c0·9c0·9c0||36||63|
|5||5=3=2=3||A-K-Q-J A-K-Q A-K A-K-J||9c1·9c0·9c0·9c0||9||72|
|6||5=3=2=3||A-K-Q-J A-K-Q A-Q A-K-Q||9c1·9c0·9c0·9c0||9||81|
|7||5=3=2=3||A-K-Q-J A-K-J A-K A-K-Q||9c1·9c0·9c0·9c0||9||90|
|8||5=3=2=3||A-K-Q A-K-Q A-K A-K-Q||9c2·9c0·9c0·9c0||36||126|
|9||5=2=3=3||A-K-Q-J A-K A-K-Q A-K-J||9c1·9c0·9c0·9c0||9||135|
|10||5=2=3=3||A-K-Q-J A-K A-K-J A-K-Q||9c1·9c0·9c0·9c0||9||144|
|11||5=2=3=3||A-K-Q-J A-Q A-K-Q A-K-Q||9c1·9c0·9c0·9c0||9||153|
|12||5=2=3=3||A-K-Q A-K A-K-Q A-K-Q||9c2·9c0·9c0·9c0||36||189|
|13||3=5=3=2||A-K-Q A-K-Q-J A-K-Q A-Q||9c0·9c1·9c0·9c0||9||198|
|14||3=5=3=2||A-K-Q A-K-Q-J A-K-J A-K||9c0·9c1·9c0·9c0||9||207|
|15||3=5=3=2||A-K-Q A-K-Q A-K-Q A-K||9c0·9c2·9c0·9c0||36||243|
|16||3=5=3=2||A-K-J A-K-Q-J A-K-Q A-K||9c0·9c1·9c0·9c0||9||252|
|17||3=5=2=3||A-K-Q A-K-Q-J A-K A-K-J||9c0·9c1·9c0·9c0||9||261|
|18||3=5=2=3||A-K-Q A-K-Q-J A-Q A-K-Q||9c0·9c1·9c0·9c0||9||270|
|19||3=5=2=3||A-K-Q A-K-Q A-K A-K-Q||9c0·9c2·9c0·9c0||36||306|
|20||3=5=2=3||A-K-J A-K-Q-J A-K A-K-Q||9c0·9c1·9c0·9c0||9||315|
|21||3=3=5=2||A-K-Q A-K-Q A-K-Q-J A-Q||9c0·9c0·9c1·9c0||9||324|
|22||3=3=5=2||A-K-Q A-K-Q A-K-Q A-K||9c0·9c0·9c2·9c0||36||360|
|23||3=3=5=2||A-K-Q A-K-J A-K-Q-J A-K||9c0·9c0·9c1·9c0||9||369|
|24||3=3=5=2||A-K-J A-K-Q A-K-Q-J A-K||9c0·9c0·9c1·9c0||9||378|
|25||3=3=2=5||A-K-Q A-K-Q A-K A-K-Q||9c0·9c0·9c0·9c2||36||414|
|26||3=3=2=5||A-K-Q A-K-Q A-Q A-K-Q-J||9c0·9c0·9c0·9c1||9||423|
|27||3=3=2=5||A-K-Q A-K-J A-K A-K-Q-J||9c0·9c0·9c0·9c1||9||432|
|28||3=3=2=5||A-K-J A-K-Q A-K A-K-Q-J||9c0·9c0·9c0·9c1||9||441|
|29||3=2=5=3||A-K-Q A-K A-K-Q-J A-K-J||9c0·9c0·9c1·9c0||9||450|
|30||3=2=5=3||A-K-Q A-K A-K-Q A-K-Q||9c0·9c0·9c2·9c0||36||486|
|31||3=2=5=3||A-K-Q A-Q A-K-Q-J A-K-Q||9c0·9c0·9c1·9c0||9||495|
|32||3=2=5=3||A-K-J A-K A-K-Q-J A-K-Q||9c0·9c0·9c1·9c0||9||504|
|33||3=2=3=5||A-K-Q A-K A-K-Q A-K-Q||9c0·9c0·9c0·9c2||36||540|
|34||3=2=3=5||A-K-Q A-K A-K-J A-K-Q-J||9c0·9c0·9c0·9c1||9||549|
|35||3=2=3=5||A-K-Q A-Q A-K-Q A-K-Q-J||9c0·9c0·9c0·9c1||9||558|
|36||3=2=3=5||A-K-J A-K A-K-Q A-K-Q-J||9c0·9c0·9c0·9c1||9||567|
|37||2=5=3=3||A-K A-K-Q-J A-K-Q A-K-J||9c0·9c1·9c0·9c0||9||576|
|38||2=5=3=3||A-K A-K-Q-J A-K-J A-K-Q||9c0·9c1·9c0·9c0||9||585|
|39||2=5=3=3||A-K A-K-Q A-K-Q A-K-Q||9c0·9c2·9c0·9c0||36||621|
|40||2=5=3=3||A-Q A-K-Q-J A-K-Q A-K-Q||9c0·9c1·9c0·9c0||9||630|
|41||2=3=5=3||A-K A-K-Q A-K-Q-J A-K-J||9c0·9c0·9c1·9c0||9||639|
|42||2=3=5=3||A-K A-K-Q A-K-Q A-K-Q||9c0·9c0·9c2·9c0||36||675|
|43||2=3=5=3||A-K A-K-J A-K-Q-J A-K-Q||9c0·9c0·9c1·9c0||9||684|
|44||2=3=5=3||A-Q A-K-Q A-K-Q-J A-K-Q||9c0·9c0·9c1·9c0||9||693|
|45||2=3=3=5||A-K A-K-Q A-K-Q A-K-Q||9c0·9c0·9c0·9c2||36||729|
|46||2=3=3=5||A-K A-K-Q A-K-J A-K-Q-J||9c0·9c0·9c0·9c1||9||738|
|47||2=3=3=5||A-K A-K-J A-K-Q A-K-Q-J||9c0·9c0·9c0·9c1||9||747|
|48||2=3=3=5||A-Q A-K-Q A-K-Q A-K-Q-J||9c0·9c0·9c0·9c1||9||T = 756|
Combinatorial calculations are now based on 9 (not 13) because only spot cards (2-10) are involved. Each ace, king, queen and jack is assigned by individual cases. Note how the presence of fixed high cards affects the combinatorial of each suit, as fewer spot cards are required to fill out the remainder indeed, very few (if any) in this extreme example. Also note the surprisingly low total compared to previous tables, because only 756 hands out of 635+ billion fit the constraints. The rest is routine. Obtain a random number from 0-755 to select the case, randomly fill a spot card or two, and randomly deal the other hands.
If a second hand is to be constrained for pattern and HCP, each possible makeup of the first hand must be paired with each possible makeup of the second hand. Considering that there are 560 specific hand patterns and up to 4658 ways to distribute high cards for a given total, this can get messy, but thats what computers are for. Hey, puter! I spilled my drink. Clean it up!
Fortunately, the process adapts well to computerization. There are 16 high cards, which neatly allows a 16-bit word to contain all possible arrangements. Ordering the representation by suit then rank works best, so the bitmap I use is: A-K-Q-J A-K-Q-J A-K-Q-J A-K-Q-J. Of the 65,536 bitmaps, 137 are thrown out as impossible (requiring 14+ cards) which leaves 65,399 possible arrangements. These are sorted by their HCP total and split accordingly into 38 lookup lists. The bitmap respresentation also makes it easy to check which arrangements are possible for the second hand. The first bitmap is logically Anded with future prospects, and only zero results are eligible; i.e., any common bit means impossible.
Another trick I use is an array of lookup tables, not just the usual two-dimensional combinatorials but indexed thirdly by a suits HCP bitmap. This way, the proper factor including the adjustment for the number of fixed high cards (if any) is obtained instantly. Further, this eliminates the overhead of checking for viability, as impossible cases simply return a factor of zero, killing that case with multiplication. This may not make sense to everyone, but for a computer CPU it is heaven.
The greatest shortcut of all is that the enumeration need only be done once. After that, all it takes is successive random numbers (0 to T-1) to produce true random deals from the given constraints.
Currently I allow listings up to 64 million cases (actually 64 MB). Each case takes 16 bytes* of data, so the size can reach 1 GB. Being an old-fashioned assembly programmer (16-bit x86), memory storage is out of the question, so the listing is written to a file at 64K intervals. An index is kept in memory to speed up access for each random number chosen.
*Storage includes the cumulative total which can reach 6+ sextillion (52c13·39c13) requiring 73 bits; two pattern indexes 0-559 (560 = off) requiring 10 bits each; and two high-card bitmaps (0FFFFh = off) requiring 16 bits each. These add to 125 bits (16 bytes = 128 bits).
Judging the randomness of a bridge deal or even hundreds of deals is impossible by appearance. Therefore, I ran various batches of 10,485,760 deals each to test and debug* the algorithms, using my deal statistics analyzer to tabulate the results. Click on the links to see the complete stats.
*Debug indeed, as for days I was getting 10 million deals of crap, until I found a faulty byte in a lookup table. Amazing how much one typo can ruin.
Club Length 0-13 Effectively no setting but useful to zero the balance scale. Even though Wests pattern was always chosen first and Norths second, with the dregs going to South and East, the evenness of the stats confirms that pattern dealing is sound in theory.
Nine Spades opp. 6-6 Minors A complete run of my second example. Odds against West having nine spades and East being 6-6 in the minors are over 9 million to 1. Pattern dealing spews out a valid random deal on every shot.
Balanced 28-30 opp. Major Transfer bidding practice for cardracks. This collection revived memories of the late Jacq van Gelder of South Florida, a clever anagram fanatic, who once christened me Heil! VIP Cardrack.
Flannery Misfits Need to cure partners of Flannery? Send them these hands for bidding practice. After bidding ad infinitum without ever finding a major fit, theyll switch to your weak 2 bid a heartbeat. Proselytized by PavCo works every time.
Flat 10-12 opp. 11-15 Three-Suiter This one barely fit my size limitation, requiring a table of some 62 million cases. To verify that order is irrelevant, I ran it a second time with the three-suiter defined first, and totals were identical.
© 2013 Richard Pavlicek