| 1 |
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| 2 |
"http://www.w3.org/TR/html4/strict.dtd"> |
| 3 |
<html> |
| 4 |
<head> |
| 5 |
<!-- $Id: Optimization.html 313 2009-06-11 05:44:13Z thomasoa $ --> |
| 6 |
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> |
| 7 |
<LINK REL="SHORTCUT ICON" HREF="/icon/bridge.ico"> |
| 8 |
<link rev="made" href="mailto:deal@thomasoandrews.com (Thomas Andrews)"> |
| 9 |
<link rel="stylesheet" type="text/css" href="look.css"> |
| 10 |
<title> |
| 11 |
Optimizing Dealing - Some Ideas |
| 12 |
</title> |
| 13 |
|
| 14 |
<link rev="made" href="mailto:deal@thomasoandrews.com (Thomas Andrews)"> |
| 15 |
|
| 16 |
</head> |
| 17 |
|
| 18 |
<body> |
| 19 |
<div class="toplevel"> |
| 20 |
<h1>Optimizing Dealing - Some Ideas</h1> |
| 21 |
<hr> |
| 22 |
<p> |
| 23 |
After doing some profiling, I found 'deal' spends most of its time |
| 24 |
in the random number generator. This is apparently a problem |
| 25 |
other people have encountered, and at least one of the publicly |
| 26 |
available dealers actually cheats around this somewhat by using |
| 27 |
a bad methodology. |
| 28 |
<p> |
| 29 |
To stay out of the random number generator as much as possible, |
| 30 |
I made improvements so that 'deal' only deals cards to a hand |
| 31 |
when information is requested about that hand. |
| 32 |
<p> |
| 33 |
For example, with the script: |
| 34 |
<pre class="codesample"> |
| 35 |
main { |
| 36 |
#west has 15-17 HCP and east has a 5-card heart suit |
| 37 |
reject unless {[balanced west]} # line A |
| 38 |
set whcp [hcp west] |
| 39 |
reject if {$whcp>17} {$whcp<15} |
| 40 |
accept if {[hearts east]>=5} # line B |
| 41 |
} |
| 42 |
</pre> |
| 43 |
Each time through the main loop, 'deal' starts with no cards dealt. |
| 44 |
When it reaches line (A), a question is asked about the west hand. |
| 45 |
No cards have been dealt yet, so 'deal' parcels out 13 random cards |
| 46 |
to west (requiring 13 calls to the random number generator.) |
| 47 |
'Deal' then checks whether the hand is in fact balanced, and if not, |
| 48 |
it rejects the hand. |
| 49 |
<p> |
| 50 |
If the hand is balanced, 'deal' computes the HCP, rejecting the deal |
| 51 |
if west isn't between 15 and 17 HCP. Only at line (B) do we request |
| 52 |
that east have 5 or more hearts, at which point "deal" gives 13 cards |
| 53 |
to east and then checks the conditional. If the hand is accepted, |
| 54 |
the rest of the deal is completed. |
| 55 |
<p> |
| 56 |
Under this implementation, you can often come close to tripling the speed of |
| 57 |
complex queries. |
| 58 |
<p> |
| 59 |
Other optimizations are possible. |
| 60 |
<p> |
| 61 |
Let's say you want to deal hands where south has a solid seven card |
| 62 |
or longer minor suit and no side aces or kings, and north holds: |
| 63 |
<span class="code">"S: AK H: K52 D: 98765 C: 962"</span>. To do this simulation |
| 64 |
now, we place north's card, and then deal the rest of south's cards, |
| 65 |
rejecting deals which don't satisfy our conditions. This might take a while. |
| 66 |
<p> |
| 67 |
Theoretically, we could do this much faster by picking a shape for south |
| 68 |
using relative probabilities, and deal him cards which fit that shape. |
| 69 |
So, for instance, the number of ways to assign random cards to north |
| 70 |
to give north a 3-2-7-1 shape is |
| 71 |
(11 choose 3) * (10 choose 2) * (8 choose 7) * (10 choose 1)=594000, |
| 72 |
while the number of ways for him to have 3-2-1-7 shape is (11 choose 3) * |
| 73 |
(10 choose 2) * (8 choose 1) * (10 choose 7)=7128000. |
| 74 |
<p> |
| 75 |
It should come as no surprise that it is more likely that south has seven clubs |
| 76 |
than that south has seven diamonds, given north's shape. |
| 77 |
<p> |
| 78 |
Since there are only 560 total possible shapes without <em>any</em> |
| 79 |
restrictions, we can certainly run through all possible shapes and determine |
| 80 |
their relative odds. Then we can pick one of these possible shapes |
| 81 |
randomly, with the proper probability distributions, and assign cards at |
| 82 |
random, suit by suit, to bring the south hand to the proper shape. At this |
| 83 |
point, we check to determine that the other properties are met. |
| 84 |
<p> |
| 85 |
This would certainly greatly improve the performance in certain "rare |
| 86 |
hand" situations. It's not clear how much it could improve more |
| 87 |
general randomizations. What if we simply need north to be balanced? |
| 88 |
Or for north to have a 5-card major? Would this sort of optimization |
| 89 |
improve things? |
| 90 |
<p> |
| 91 |
Also, this methodology makes it much harder to *prove* that the hand |
| 92 |
generator is correct. The code to handle the probability computations |
| 93 |
has to be impeccable. |
| 94 |
<p> |
| 95 |
Lastly, I can't see any way to automatically get the hand shape information |
| 96 |
needed for such optimizations; if I controlled the parser, I might be |
| 97 |
able to intelligently glean the information from the specification, but |
| 98 |
since I've chosen Tcl as my scripting language, I'm somewhat stuck in |
| 99 |
that regard. The user will almost certainly have to provide the |
| 100 |
optimization request directly. |
| 101 |
<p> |
| 102 |
<h2> Why optimize? </h2> |
| 103 |
There is a logical argument against such optimizations, on the other hand. |
| 104 |
What are we trying to learn if we are looking at a sample of one in a million |
| 105 |
hands? Let's say you play gambling 3NT, and partner opens 3NT with you holding |
| 106 |
<span class="code">S: Axxx H: KQx D: Q C: xxxxx</span>. |
| 107 |
If we try to simulate this, assuming partner has |
| 108 |
7+ solid clubs and no side aces, we might not get a proper hand for a |
| 109 |
very long time. On the |
| 110 |
other hand, the number of possible hands where partner has "fudged" his |
| 111 |
call with AKJTxxxx of diamonds or with only six clubs is considerably higher. |
| 112 |
In simulations where hands are not being found after tens of thousands of tries, |
| 113 |
it is often right to loosen the parameters. |
| 114 |
<p> |
| 115 |
On the other hand, if you are trying to settle an argument like, "Well, if |
| 116 |
you had your bid, that would have been a good slam," then the tighter |
| 117 |
parameters might be right, in which case optimizations might be necessary. |
| 118 |
<hr> |
| 119 |
<table><tr><td><a href="http://bridge.thomasoandrews.com/" class="image"> |
| 120 |
<img style="border:0;width:40px;height:56px" alt="Silhouette" src="graphics/StampSm.gif"></a><td> |
| 121 |
Thomas Andrews |
| 122 |
(<a href="mailto:deal@thomasoandrews.com">deal@thomasoandrews.com</a>) |
| 123 |
Copyright 1996-2010. Deal is covered by the |
| 124 |
<a href="http://www.gnu.org/copyleft/gpl.html">GNU General Public License.</a> |
| 125 |
<p> |
| 126 |
<a href="graphics/falling.jpg"><em>Plane Dealing</em></a> graphic |
| 127 |
above created using |
| 128 |
<a href="http://www.povray.org/">POV-Ray.</a> |
| 129 |
</tr></table> |
| 130 |
</div> |
| 131 |
</body> |
| 132 |
</html> |