Main   Study 8H11 by Richard Pavlicek  

Dealing with Constraints

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, you’ve 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 don’t succeed…
Pattern DealingHCP ConstraintsPattern and HCP ConstraintsTesting the Algorithms

Pattern Dealing

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:


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:

West Hands with 9 Spades
CasePatternCalculationNumber of HandsCumulative Total
159=0=0=413c9·13c0·13c0·13c4511225T = 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 that’s the only constraint, the rest is easy. Suppose West’s 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 you’re done — a truly random deal with West having nine spades.

Constraining Two Hands

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:

West 9 Spades and East 6-6 Minors
CaseWestEastCalculationCombinationsCumulative Total
309=0=0=40=1=6=613c9·13c0·13c0·13c4·4c0·13c1·13c6·9c6957970213200T = 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. TopMain

HCP Constraints

Applying HCP constraints to random dealing is difficult, because HCP in theory is not a “number” like a hand’s spade length, but various combinations of specific cards to comprise that number. I am always looking for shortcuts, but I don’t 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:

North Hands with 3 HCP
CaseHigh CardsCalculationNumber of HandsCumulative Total
1S K36c1212516777001251677700
2S Q S J36c116008052961852482996
3S Q H J36c116008052962453288292
4S Q D J36c116008052963054093588
5S Q C J36c116008052963654898884
6S J H Q36c116008052964255704180
7S J H J D J36c102541868564509891036
8S J H J C J36c102541868564764077892
9S J D Q36c116008052965364883188
10S J D J C J36c102541868565619070044
11S J C Q36c116008052966219875340
12H K36c1212516777007471553040
13H Q H J36c116008052968072358336
14H Q D J36c116008052968673163632
15H Q C J36c116008052969273968928
16H J D Q36c116008052969874774224
17H J D J C J36c1025418685610128961080
18H J C Q36c1160080529610729766376
19D K36c12125167770011981444076
20D Q D J36c1160080529612582249372
21D Q C J36c1160080529613183054668
22D J C Q36c1160080529613783859964
23C K36c12125167770015035537664
24C Q C J36c11600805296T = 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 H Q and C 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.

Constraining Two Hands

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:

North 2 HCP and South 0-1 HCP
CaseNorthSouthCalculationCombinationsCumulative Total
1S Q36c12·24c1331243677807888003124367780788800
2S QS J36c12·24c1233847317625212006509099543310000
3S QH J36c12·24c1233847317625212009893831305831200
4S QD J36c12·24c12338473176252120013278563068352400
5S QC J36c12·24c12338473176252120016663294830873600
6S J H J36c11·25c13312436778078880019787662611662400
7S J H JD J36c11·25c12312436778078880022912030392451200
8S J H JC J36c11·25c12312436778078880026036398173240000
9S J D J36c11·25c13312436778078880029160765954028800
10S J D JH J36c11·25c12312436778078880032285133734817600
11S J D JC J36c11·25c12312436778078880035409501515606400
12S J C J36c11·25c13312436778078880038533869296395200
13S J C JH J36c11·25c12312436778078880041658237077184000
14S J C JD J36c11·25c12312436778078880044782604857972800
15H Q36c12·24c13312436778078880047906972638761600
16H QS J36c12·24c12338473176252120051291704401282800
17H QH J36c12·24c12338473176252120054676436163804000
18H QD J36c12·24c12338473176252120058061167926325200
19H QC J36c12·24c12338473176252120061445899688846400
20H J D J36c11·25c13312436778078880064570267469635200
21H J D JS J36c11·25c12312436778078880067694635250424000
22H J D JC J36c11·25c12312436778078880070819003031212800
23H J C J36c11·25c13312436778078880073943370812001600
24H J C JS J36c11·25c12312436778078880077067738592790400
25H J C JD J36c11·25c12312436778078880080192106373579200
26D Q36c12·24c13312436778078880083316474154368000
27D QS J36c12·24c12338473176252120086701205916889200
28D QH J36c12·24c12338473176252120090085937679410400
29D QD J36c12·24c12338473176252120093470669441931600
30D QC J36c12·24c12338473176252120096855401204452800
31D J C J36c11·25c13312436778078880099979768985241600
32D J C JS J36c11·25c123124367780788800103104136766030400
33D J C JH J36c11·25c123124367780788800106228504546819200
34C Q36c12·24c133124367780788800109352872327608000
35C QS J36c12·24c123384731762521200112737604090129200
36C QH J36c12·24c123384731762521200116122335852650400
37C QD J36c12·24c123384731762521200119507067615171600
38C QC J36c12·24c123384731762521200T = 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. TopMain

Pattern and 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:

East 5-3-3-2 with 34 HCP
CasePatternHigh CardsCalculationHandsTotal
15=3=3=2S A-K-Q-J H A-K-Q D A-K-Q C A-Q9c1·9c0·9c0·9c099
25=3=3=2S A-K-Q-J H A-K-Q D A-K-J C A-K9c1·9c0·9c0·9c0918
35=3=3=2S A-K-Q-J H A-K-J D A-K-Q C A-K9c1·9c0·9c0·9c0927
45=3=3=2S A-K-Q H A-K-Q D A-K-Q C A-K9c2·9c0·9c0·9c03663
55=3=2=3S A-K-Q-J H A-K-Q D A-K C A-K-J9c1·9c0·9c0·9c0972
65=3=2=3S A-K-Q-J H A-K-Q D A-Q C A-K-Q9c1·9c0·9c0·9c0981
75=3=2=3S A-K-Q-J H A-K-J D A-K C A-K-Q9c1·9c0·9c0·9c0990
85=3=2=3S A-K-Q H A-K-Q D A-K C A-K-Q9c2·9c0·9c0·9c036126
95=2=3=3S A-K-Q-J H A-K D A-K-Q C A-K-J9c1·9c0·9c0·9c09135
105=2=3=3S A-K-Q-J H A-K D A-K-J C A-K-Q9c1·9c0·9c0·9c09144
115=2=3=3S A-K-Q-J H A-Q D A-K-Q C A-K-Q9c1·9c0·9c0·9c09153
125=2=3=3S A-K-Q H A-K D A-K-Q C A-K-Q9c2·9c0·9c0·9c036189
133=5=3=2S A-K-Q H A-K-Q-J D A-K-Q C A-Q9c0·9c1·9c0·9c09198
143=5=3=2S A-K-Q H A-K-Q-J D A-K-J C A-K9c0·9c1·9c0·9c09207
153=5=3=2S A-K-Q H A-K-Q D A-K-Q C A-K9c0·9c2·9c0·9c036243
163=5=3=2S A-K-J H A-K-Q-J D A-K-Q C A-K9c0·9c1·9c0·9c09252
173=5=2=3S A-K-Q H A-K-Q-J D A-K C A-K-J9c0·9c1·9c0·9c09261
183=5=2=3S A-K-Q H A-K-Q-J D A-Q C A-K-Q9c0·9c1·9c0·9c09270
193=5=2=3S A-K-Q H A-K-Q D A-K C A-K-Q9c0·9c2·9c0·9c036306
203=5=2=3S A-K-J H A-K-Q-J D A-K C A-K-Q9c0·9c1·9c0·9c09315
213=3=5=2S A-K-Q H A-K-Q D A-K-Q-J C A-Q9c0·9c0·9c1·9c09324
223=3=5=2S A-K-Q H A-K-Q D A-K-Q C A-K9c0·9c0·9c2·9c036360
233=3=5=2S A-K-Q H A-K-J D A-K-Q-J C A-K9c0·9c0·9c1·9c09369
243=3=5=2S A-K-J H A-K-Q D A-K-Q-J C A-K9c0·9c0·9c1·9c09378
253=3=2=5S A-K-Q H A-K-Q D A-K C A-K-Q9c0·9c0·9c0·9c236414
263=3=2=5S A-K-Q H A-K-Q D A-Q C A-K-Q-J9c0·9c0·9c0·9c19423
273=3=2=5S A-K-Q H A-K-J D A-K C A-K-Q-J9c0·9c0·9c0·9c19432
283=3=2=5S A-K-J H A-K-Q D A-K C A-K-Q-J9c0·9c0·9c0·9c19441
293=2=5=3S A-K-Q H A-K D A-K-Q-J C A-K-J9c0·9c0·9c1·9c09450
303=2=5=3S A-K-Q H A-K D A-K-Q C A-K-Q9c0·9c0·9c2·9c036486
313=2=5=3S A-K-Q H A-Q D A-K-Q-J C A-K-Q9c0·9c0·9c1·9c09495
323=2=5=3S A-K-J H A-K D A-K-Q-J C A-K-Q9c0·9c0·9c1·9c09504
333=2=3=5S A-K-Q H A-K D A-K-Q C A-K-Q9c0·9c0·9c0·9c236540
343=2=3=5S A-K-Q H A-K D A-K-J C A-K-Q-J9c0·9c0·9c0·9c19549
353=2=3=5S A-K-Q H A-Q D A-K-Q C A-K-Q-J9c0·9c0·9c0·9c19558
363=2=3=5S A-K-J H A-K D A-K-Q C A-K-Q-J9c0·9c0·9c0·9c19567
372=5=3=3S A-K H A-K-Q-J D A-K-Q C A-K-J9c0·9c1·9c0·9c09576
382=5=3=3S A-K H A-K-Q-J D A-K-J C A-K-Q9c0·9c1·9c0·9c09585
392=5=3=3S A-K H A-K-Q D A-K-Q C A-K-Q9c0·9c2·9c0·9c036621
402=5=3=3S A-Q H A-K-Q-J D A-K-Q C A-K-Q9c0·9c1·9c0·9c09630
412=3=5=3S A-K H A-K-Q D A-K-Q-J C A-K-J9c0·9c0·9c1·9c09639
422=3=5=3S A-K H A-K-Q D A-K-Q C A-K-Q9c0·9c0·9c2·9c036675
432=3=5=3S A-K H A-K-J D A-K-Q-J C A-K-Q9c0·9c0·9c1·9c09684
442=3=5=3S A-Q H A-K-Q D A-K-Q-J C A-K-Q9c0·9c0·9c1·9c09693
452=3=3=5S A-K H A-K-Q D A-K-Q C A-K-Q9c0·9c0·9c0·9c236729
462=3=3=5S A-K H A-K-Q D A-K-J C A-K-Q-J9c0·9c0·9c0·9c19738
472=3=3=5S A-K H A-K-J D A-K-Q C A-K-Q-J9c0·9c0·9c0·9c19747
482=3=3=5S A-Q H A-K-Q D A-K-Q C A-K-Q-J9c0·9c0·9c0·9c19T = 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 that’s what computers are for. Hey, ‘puter! I spilled my drink. Clean it up!

Useful Tricks

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: S A-K-Q-J H A-K-Q-J D A-K-Q-J C 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 suit’s 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). TopMain

Testing the Algorithms

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 West’s pattern was always chosen first and North’s 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, they’ll switch to your weak 2 D 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. TopMain

© 2013 Richard Pavlicek