Main
Article 7Z71 by Richard Pavlicek
[This 1999 article is obsolete and theoretically flawed. See Dealing with Constraints for a current study.]
This article is not about random* number generators — I will leave that to the mathematicians. For my purposes I will assume an adequate source of random numbers. The topic I am concerned with is the creation of random bridge deals with constraints; that is, deals in which one or more hands are required to have specific HCP totals and/or suit lengths. The pursuit of an efficient algorithm has proved to be challenging.
*Technically, the word should be “pseudorandom.” It is impossible to obtain truly random numbers from any defined method. Obviously, the method used by a computer must be defined, which proves it can never be random. Nonetheless, I will continue to use the word “random” for convenience.
Creating a random bridge deal without constraints is simple. All it involves is the shuffling of an array of 52 elements, which can be done with various algorithms that are as perfect as the source of random numbers. But what if the deal has constraints? For example, say West must have 11-15 HCP with five or six spades and four hearts, and East must have 10 HCP with at least four diamonds. The ideal method would be to create a random deal without constraints, then check to see if it fits the requirements. If not, throw it out and deal again. While undeniable perfect, this method suffers because it may take too long, especially if the constraints are extreme. Therefore, I will dismiss this strategy.
So what is the best way to do it? It is easy to move cards around to meet the desired constraints, but this spoils the randomness. The object is to create a deal that is random for its constraints and not biased by deliberate construction. Ideally, the probability of any particular deal should be same as if it were found with the “keep dealing until it fits” algorithm. I’m not even sure this is possible in the truest sense, but my algorithms come pretty close.
The difficulty of this task is the interdependence of HCP and suit lengths. The probability of receiving particular high cards is dependent on the shape of the hand, and vice versa. Any attempt to isolate the two quantities will result in faulty randomization. Consider the example West hand I gave. Surely, if West is 5-4 in the majors, his high cards are more likely to be there, and slightly more likely in spades than in hearts. But the method to fulfill this is not obvious.
I have considered many approaches to this problem and settled on the following general plan:
| 1. Resolve the pattern of length-constrained hands. 2. Fill the HCP requirements. 3. Fill the hands, those with constraints first. |
If one or more hands have suit-length constraints, the problem is how to randomly assign the additional slots (if required) to create full hand patterns. Consider the two example hands I described previously, which would look like this in table form:
| Suit | West | East | ||
|---|---|---|---|---|
| Min | Max | Min | Max | |
| Spades | 5 | 6 | 0 | 8 |
| Hearts | 4 | 4 | 0 | 9 |
| Diamonds | 0 | 4 | 4 | 13 |
| Clubs | 0 | 4 | 0 | 9 |
Note how the maximum lengths are determined. West’s major suits are fixed by the conditions, and the other maximums are forced by the 13-card limit of each hand and each suit.
To complete the patterns, West requires four more slots, and East nine — I will call these soft spaces since they are not yet tied to a specific suit. Obviously, these soft spaces must be obtained from the unassigned slots in each suit. Let’s consider the fair way to decide a soft space for West (remember, I am just deciding the pattern, not the actual cards). There are 39 available slots (8 in spades, 9 in hearts, 9 in diamonds and 13 in clubs) so if I drew one at random the odds of choosing a particular suit would be in the proportion, 8:9:9:13. West cannot receive a heart, so considering spades, diamonds and clubs, the proportion is 8:9:13.
A selection by this proportion is eminently fair, but it makes a dubious assumption about our intentions. When we specify five or six spades, does it mean (1) allow a sixth spade by the normal chances, then cut off further spades, or (2) weight the chances of receiving a sixth spade according to the amount of excess room in each suit? The previous method assumes (1), but that’s probably not the desired effect; it is likely to award the sixth spade too often. The stated conditions probably intend a lower chance of a sixth spade, and five spades should be more common than six.
Therefore, to interpret the constraints as intended, it is necessary to consider the amount of excess space in each hand. To aid in the calculations, I create a matrix of the excess space (maximum minus minimum) for each player in each suit.
| Excess Space Matrix | |||||
|---|---|---|---|---|---|
| Suit | W | N | E | S | Available |
| Spades | 1 | 8 | 8 | 8 | 8 |
| Hearts | 0 | 9 | 9 | 9 | 9 |
| Diamonds | 4 | 9 | 9 | 9 | 9 |
| Clubs | 4 | 13 | 9 | 13 | 13 |
To assign a slot fairly, I consider the weight factor (determined by the excess space in that suit) and the total number of slots available in that suit. The relative probability (RP) — hey, that’s me — for each suit is found by the formula:
RP = (weight) × (available cards)
This arbitrary weighting method solves one problem, but unfortunately creates another. Consider the case where each suit has the same constraints, say 2-5 cards, which means an excess of 3. After a slot is added, both the excess space (i.e., the weight) and the available cards drop, thereby reducing the chances of further slots in that suit in a ratio that defies the laws of probability theory. The result is that hands tend to even out, i.e., in my example it would produce too many 4-3-3-3 patterns. After a little experimentation, I found that the best fix is to keep the weight factor of each suit constant as long as the hand still has space to receive a card in that suit.
As a further tweak to this algorithm, I allow the user to adjust the weight of any suit. For example, when specifying four or more diamonds, the probability of additional diamonds (beyond four) can be increased or decreased if the default method does not produce the desired results.
Let’s see how the formula applies to West:
RP  = 1 × 8 = 8RP  = 0 × 9 = 0RP  = 4 × 9 = 36RP  = 4 × 13 = 52 |
Note how this method makes it less likely for West to receive another spade. West is most likely to receive a club because all the clubs are available, and second most likely to receive a diamond. Obviously, there is no chance to receive a heart.
Once the relative probabilities are found, it is easy to make a fair random draw. The relative probabilities are summed (8 + 0 + 36 + 52 = 96) and I obtain a random number (N) less than the total (0 to 95). The suit is then determined as follows:
| If N < 8 the suit is spades. Else, if N < 8 + 0 the suit is hearts. Else, if N < 8 + 0 + 36 the suit is diamonds. Else, the suit is clubs. |
Note how this logic makes it impossible to select a suit that had no chance, as hearts in this case.
West gains a slot in whichever suit was chosen, and the following updates are made:
| 1. West’s soft space is reduced by 1. 2. West’s excess in the chosen suit is reduced by 1. 3. West’s excess in any other suit is reduced by 1 if it exceeds the new amount of soft space. 4. The available cards in the chosen suit are reduced by 1. 5. Each other hand’s excess in the chosen suit is reduced by 1 if it exceeds the available cards. |
This prepares the matrix for the next draw, and the process is repeated until West’s soft space is zero, which finishes the West pattern. I then move on to the next hand with constraints (East in my example) and complete it in the same way. Hands without explicit suit-length constraints (North and South in this case) are skipped because they can receive cards freely in any suit; hence, this step is unnecessary.
At first I thought this algorithm would resolve any matrix, but I overlooked an anomaly. Suppose West is required to have a minimum of five spades, North five hearts, and East five diamonds, and South a maximum of four clubs. The matrix for such a deal would look like a game of Crazy Eights:
| Excess Space Matrix | |||||
|---|---|---|---|---|---|
| Suit | W | N | E | S | Available |
| Spades | 8 | 8 | 8 | 8 | 8 |
| Hearts | 8 | 8 | 8 | 8 | 8 |
| Diamonds | 8 | 8 | 8 | 8 | 8 |
| Clubs | 8 | 8 | 8 | 4 | 13 |
Consider the club suit. West, North and East have no obligation to absorb clubs, so when I get to South I may have more than four club slots remaining, which would overflow the South pattern. To correct this, I check the matrix for forced slots in each suit before doing each hand. For example, if I came to East and there were six club slots left, East would be obliged to take two. (Note that East could take more if drawn randomly, but two are forced.) Also, to improve the randomization, I do the hands in a random sequence.
Until now, I have not placed any actual cards, but only completed the pattern of hands with suit-length constraints. Each hand is just an empty shell. If the hand had suit-length constraints, the shell is partitioned into suits; otherwise, the shell is simply 13 empty slots open to any suit.
The next step is to distribute the HCP to hands that have a minimum or an explicit maximum requirement. Note that this does not include hands with implicit maximums. For example, if West is required to hold 15 to 17 HCP, it forces an implicit maximum of 25 HCP on all the other hands, but this must be satisfied perforce after West gets its points.
Distributing the high cards is not a simple task when a hand has suit-length constraints. A straight random draw is unfair because high cards are more likely to be held in longer suits than shorter suits. Clearly, it is necessary to weight the chances by suit length.
Further, if a range of HCP is specified, how do you decide the exact number? My method is to convert each range into a precise goal by considering the relative chance of each possibility. This is easily shown with a table of HCP expectancies:
| Point-Count Expectancies* | |||
|---|---|---|---|
| HCP | Percent | HCP | Percent |
| 0 | 0.3639 | 16 | 3.3109 |
| 1 | 0.7884 | 17 | 2.3617 |
| 2 | 1.3561 | 18 | 1.6051 |
| 3 | 2.4624 | 19 | 1.0362 |
| 4 | 3.8454 | 20 | 0.6435 |
| 5 | 5.1862 | 21 | 0.3779 |
| 6 | 6.5541 | 22 | 0.2100 |
| 7 | 8.0281 | 23 | 0.1119 |
| 8 | 8.8992 | 24 | 0.0559 |
| 9 | 9.3562 | 25 | 0.0264 |
| 10 | 9.4051 | 26 | 0.0117 |
| 11 | 8.9447 | 27 | 0.0049 |
| 12 | 8.0269 | 28 | 0.0019 |
| 13 | 6.9143 | 29 | 0.0007 |
| 14 | 5.6933 | 30 | 0.0002 |
| 15 | 4.4237 | 31-37 | 0.0001 |
*Calculated by Col. Roy L. Telfer and first published in Probabilities in Contract Bridge, 1963. (An impressive accomplishment before computers.)
For example, if a hand required 15-17 HCP, I would find the total (T) of the three percentages:
T = 4.4237 + 3.3109 + 2.3617
This equals 10.0963, or 100,963 parts in a million to consider it as a whole number. I then select a random number (N) from 0 to T-1, which will serve as an index to select the exact HCP:
| If N < 44237 the HCP is 15. Else, if N < 44237 + 33109 the HCP is 16. Else, the HCP is 17. |
Observe how this makes the hand more likely to hold 15 HCP than 16 or 17, and more likely to hold 16 than 17, in the same proportion as if the hand were dealt in real life.
This method of deciding the exact HCP works great in practice, though it is theoretically imperfect for two reasons: I am not considering the specific hand pattern, and I am using rounded numbers (the gods of randomization do not like decimal places). Ideally, these flaws could be eliminated with a specialized table for each hand pattern and exact coefficients instead of percentages, but this is overkill for the slight improvement it would yield. Further, the differences in the percentage tables for various hand patterns are negligible, except for extreme shapes.
What about the huge hands? Note in the table that 31-37 HCP are grouped together since these cases total only about 0.0001 percent when combined. Hence, in my selection method the entire group is weighted as one chance. If the group is selected, I must then decide which value to use. I do this by weighting each value, up to the maximum allowed, as four times the chance of the next value. For example, if you specified 32-36 HCP (you’re a dreamer), the chance of receiving 32 would be four times greater than 33; the chance of 33, four times greater than 34, etc. Again, this is imperfect, but the odds are reasonably close to reality — and does anybody really care about these hands?
Once I have a specific HCP goal for each hand that requires it, it is time to start distributing the high cards. If more than one hand is involved, I do this in tandem: Try to hit the target of each hand with a limited number of random draws, then if it fails, toss a few cards back from each hand and recycle through the hands until the goals are met. This usually resolves quickly with only 16 cards in circulation.
The reason for the tandem process is to prevent a possible lockup. For example, if I sealed off each hand as it was completed, it might happen that all the kings and jacks are gone and the next hand requires an odd number of points. Obviously, you can’t make an odd number out of just aces and queens, so it would fail. Working with all of the hands together eliminates this snag (not in theory, of course, but the chance of failure is infinitesimal). Also, note that deliberate placements are never made; if one cycle fails, the cards returned are chosen at random.
If a hand has suit-length constraints, its drawing for high cards is always weighted by the available-space theory. That is, the relative probability (RP) for each suit is determined by the formula:
RP = (unfilled length) × (available cards)
For example, if I were drawing the first high card for a hand with 5=4=3=1 shape, the relative probabilities for each suit would be:
| RP = 5 × 4 = 20 RP = 4 × 4 = 16RP = 3 × 4 = 12RP = 1 × 4 = 4 |
The weights are summed (20 + 16 + 12 + 4 = 52) and I obtain a random number (N) from 0 to 51. The suit is then determined in the usual way:
| If N < 20 the suit is spades. Else, if N < 20 + 16 the suit is hearts. Else, if N < 20 + 16 + 12 the suit is diamonds. Else, the suit is clubs. |
Once the suit is known, I select a high card at random from that suit, give it to the hand, and update all the counts. This is continued until the point-count total equals or exceeds the goal. If the goal is exceeded, the newly received high card is kept, and random high cards are returned until the total is at or below the goal. If it drops below the goal, the loop is repeated a limited number of times hoping to hit the target. If the limited number of tries fails, I go back to the “tandem cycle” with each hand tossing back a few cards.
It’s all downhill from here! Once the HCP situation is resolved, filling out the hands is straightforward. The hands are filled in a logical order:
| 1. Hands with HCP and suit-length constraints. 2. Hands with HCP constraints. 3. Hands with suit-length constraints. 4. Hands with no constraints. |
The reason for filling HCP-constrained hands first is because their point count has already been decided, and they cannot receive any more high cards. (If a high card is drawn, it is simply rejected.) If one of these hands were done last, it could be stuck with an unwanted high card and ruin the whole process.
The method of filling a hand depends on whether it has suit-length constraints. If so, its pattern is already defined, and the filling is done by suits. Each suit is filled to capacity by a straight random draw from the available cards in that suit.
If a hand does not have suit-length constraints, it is filled by a straight random draw from all the available cards (in any suit). Further, if this is the last hand, there is no need to bother with any draws; it simply gets the remaining cards.
If my algorithms cannot complete a deal, they will exit with an error message and no deals are returned, even if there were successful deals before the failure. It’s like the old-fashioned Christmas lights — if one goes out, they all go out. A failure is almost always due to impossible conditions, though in rare cases it could be the result of extreme constraints. For example, say you requested hands with 25 HCP and six spades. These are certainly possible, but my algorithms always decide the pattern first. Hence, if this happened to produce 6-6-1-0, it would be impossible to fit 25 HCP. Rather than adjust for such bizarre cases, I say: Get serious!
These algorithms are implemented in two programs at my web site, the Wheeler Dealer and the Bidding Practice Dealer. Each is written in Perl, as commonly used with Common Gateway Interface programming.
My source for random numbers is the generator supplied with Perl 5.0, which claims to be much improved over earlier versions. I have done a few tests to verify its randomness and could not detect any bias, so the claims seem to be valid, though I doubt it would meet cryptographic standards.
I welcome any feedback — comments, suggestions to improve the algorithms, etc. Please contact me by e-mail (richard@rpbridge.net). Thank you.
Top Main
© 1999 Richard Pavlicek