Debian Codegraph @

html/Optimization.html

raw
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&#64;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&#64;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&gt;17} {$whcp&lt;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&#64;thomasoandrews.com">deal&#64;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>