DD results and system design (repost)
Matthew L. Ginsberg
answer is easy: The better system will get to the correct contract
more often. This observation in itself, however, hardly seems likely
to enable us to select between Bridge World Standard and the Leghorn
Diamond. Is there a more principled approach we can take?
There is, although it will take me some time to describe it. As a
start, suppose that we extend BWS so that some obscure sequence,
previously undefined, now has meaning. In a theoretical sense, we
have clearly improved the system; the meaning assigned to the
previously impossible sequence will be at worst worthless. At best,
we will have occasional use for the new gadget.
In some loose sense, the efficiency of a bidding system can be
measured by the number of meaningful sequences in that system. Of
course, this is _only_ in a loose sense; better to have a handful of
common sequences than a large number of defined sequences that have
meanings so specific that they are unlikely to arise in practice.
This observation, incidentally, explains the effectiveness of relay
systems. By ensuring that virtually every response to the relay has
meaning, the system designers increase the number of meaningful
sequences in the system as a whole.
It is possible to quantify this phenomenon. Suppose that we know
at the beginning of an auction that the final contract is going to
be 1H. How many routes are there to our eventual destination?
The answer is eight: 1H, 1C-1H, 1D-1H, and 1C-1D-1H, all of which may
or may not be preceded by an initial pass. We can count the sequences
by realizing that there are three questions we need to answer about
the sequence: Was there an initial pass? Did someone bid 1C? And did
someone bid 1D?
In general eight possible sequences will always correspond to three
yes/no questions of this form. If eight sequences are possible and
one is selected as corresponding to a particular deal, the first
question eliminates half of the sequences (reducing us to four), the
second reduces us to two, and the third corresponds to the specific
sequence in question.
Suppose that we denote the number of available sequences by s, and
that q is a number so that s = 2^q (the result of multiplying 2 by
itself q times). Then the s sequences give us the ability to answer q
questions. In the example in the previous paragraph, there are eight
sequences and 8 = 2^3 (2^3 = 2 * 2 * 2). The eight sequences
correspond to three questions. We will write q = log_2(s) as
shorthand for the fact that 2^q=s, and will say that the s sequences
allow us to transmit q "bits" of information. In this specific case,
we would write 3 = log_2(8). "Bits" is a computer term, and
corresponds to the fact that it takes q 0's and 1's to represent the
integer s in binary.
So here is a preliminary answer to our original question: The
efficiency of a bidding system in which there are s legal sequences is
given by log_2(s), the number of bits of information that can be
exchanged using that system.
By this measure, our bidding systems are not terribly efficient.
Consider a hand where you and your partner bid without opposition to
3H. There are 2^13 sequences that get you there (there are ten more
bids below 3H than there are below 1H, so the exponent is 13 instead
of 3); how many are possible in your system?
Ideally, all of the sequences would be possible, and they would all be
equally likely. That means that for each call between 1C and 3D,
there would be a 50-50 chance that the call appeared in a particular
auction to 3H. The average length of such a sequence is seven bids --
half of the twelve calls from 1C to 3D, together with the final 3H
bid.
At the table, a typical sequence getting to 3H is nothing like this
long. Maybe 1H-2H-3H. A rejected game try might be 1H-2H-3C-3H. A
sophisticated sequence, playing two-way game tries where 2S is a
transfer that precedes a short-suit try, might be 1H-2H-2S-2N-3C-3H.
Six bids. Just below what the _average_ sequence length should be.
On the face of it, sequences ending in 3H are probably about four bids
long on average. To count the number of such sequences, we need to
pick three of the intervening bids (1C through 3D), and include them
in the sequence. How many ways are there to do this? Well, there are
twelve choices for the first bid, and then eleven for the second if we
don't worry about the order. After all, if we pick 2D and then 1S, we
can just take the associated sequence to be 1S-2D-3H. There are ten
choices for the third bid. Of course, if we pick 2D, 1S and 2C,
that's the same as picking 1S, 2C and 2D. So the order of the three
bids selected doesn't matter, and we have to divide the number of
possibilities (twelve times eleven times ten) by the number of ways to
order three preselected bids (six). All told, that leaves 220 (12 *
11 * 10 / 6) "meaningful" sequences ending at 3H. Including an
initial pass brings this total to 440, of the 2048 theoretically
available. It feels like the "efficiency" of our bidding is around
440/2048, or about 21.5%.
If our bidding systems waste space in such a profligate manner, how is
it that they seem to get us to reasonable contracts most of the time?
The next thing we will do is to answer this question. We will do so
by addressing two secondary issues: How many bits of information are
available to be exchanged on an average bridge hand, and how many bits
_need_ to be exchanged in order to reach a good contract? As we will
see, the reason that we are able to bid both effectively and
inefficiently is that we typically need to exchange only a fraction of
the information that we _could_ exchange.
The answers to both of these questions will revolve around an
examination of a large number of hands played at double dummy. For
any specific hand, we can use the double dummy analysis to determine
what par is; it might well be 5D played by NS with a result of -100.
Since we are trying to deal with practical bidding here, we will
modify the definition of par slightly, assuming that the opponents
double every time the final contract goes down two or more. If it
only goes down one, we will assume that it is undoubled.
Of course, if we know in advance what par is on a given board, there
isn't much need for a sophisticated bidding system! So let's assume
that we don't know what contract we will bid to, but our opponents
will do the right thing once we get there. Thus if we can take ten
tricks in spades and our opponents ten in diamonds, the opponents will
presumably bid 4D if we let them (we get -130), but will bid 5D if we
push them there by bidding our spade game (we get +100). If we hold
the diamonds instead, we get -620 if we stay out of the auction
(defending 4S) but -100 if we are willing to bid 5D.
What we have, then, is what mathematicians call a _function_. The
function accepts as an argument the level that we are willing to bid
to but not beyond, and returns our score if we bid to that contract
and our opponents then bid perfectly. There will be at least one
contract for which this function takes a maximal value, and that
contract is the contract to which we would like to bid. In the
example of the previous paragraph, the appropriate contract was either
4S or 5D depending on whether we were NS or EW.
Let us now modify the above function so that instead of returning our
actual score, it returns the IMPs we will lose compared to a pair
achieving the par result. (Since our opponents are assumed to bid
perfectly once we select our level, we can never do _better_ than
par.) So if we hold diamonds in our example hand, passing gets us -11
IMPs (-620 instead of -100). If we hold spades, passing gets us -6
(-130 defending 4D instead of +100 defending 5D).
We will now assume that the goal of our bidding system is to get us to
any contract for which the function returns zero, indicating that
bidding this contract will not cost us any IMPs relative to par. If
we can make 3H and our opponents cannot make anything, we are happy to
bid 1H, 2H or 3H; they all score the same +140. If we can make 2NT or
3C, we are happy to bid any of 1NT, 2NT, 1C, 2C or 3C because there is
no IMP difference between the +120 available in NT and the +110
available in clubs. We will say that a contract is _acceptable_ if
the function assigns it zero IMPs (relative to par, remember), and
will say that our _safe level_ is the highest acceptable contract. So
in the hand where we can make 2NT or 3C, the safe level is 3C. In the
hand where we can make 4S and our opponents 4D, the safe level is 4S
for us and 5D for the opponents, even though this last contract goes
down.
We can now answer the first question we raised some time ago: How
many bits of information can be exchanged on a particular deal?
To answer this, we will assign numbers to each possible contract.
Pass is zero, 1C is one, 1D is two, and so on. 7NT, the highest
contract, is 35. Now if c is an acceptable contract for us on any
given deal, the number of sequences ending in c is 2^c. Thus there is
2^0 = 1 sequence ending at P, 2^1 = 2 sequences ending at 1C (either
partner can bid 1C), 4 sequences ending at 1D, and so on. The number
of bits that can be exchanged using these sequences is simply given by
c itself. So the number of bits that we can exchange on this
_specific_ hand is given by the log_2 of the number of sequences that
reach any of our acceptable contracts.
What about in general? To find out how many bits we can exchange on
average, we need simply generate a lot of hands at random, and see how
we do. On some hands, we'll have to stay quiet and won't get to
exchange any information at all; on others, we'll be able to make a
grand slam and can exchange a great deal. The following table
summarizes the results after examining 132,528 hands:
none unfav fav both
P 36.93 44.69 31.18 41.03
1C 17.27 18.07 18.47 20.83
1D 17.05 17.68 18.32 20.58
1H 17.27 18.33 19.67 21.70
1S 16.78 17.85 19.46 21.24
1N 11.10 12.21 16.47 15.25
2C 12.95 12.78 14.47 15.34
2D 13.28 12.93 14.95 15.49
2H 14.87 14.62 16.33 16.80
2S 15.40 14.75 16.70 16.59
2N 6.92 6.47 8.99 7.82
3C 10.03 8.91 11.02 10.65
3D 10.36 8.96 11.24 10.62
3H 10.43 9.18 11.38 10.67
3S 10.10 9.01 10.92 10.31
3N 9.48 8.32 10.70 9.60
4C 5.65 4.57 6.71 5.92
4D 5.60 4.59 6.59 5.87
4H 11.01 9.29 12.48 11.25
4S 11.17 9.49 12.90 11.37
4N 5.54 5.25 5.91 5.57
5C 2.81 2.13 3.96 3.07
5D 2.85 2.13 4.00 3.07
5H 4.82 4.05 5.95 5.00
5S 4.39 3.92 5.25 4.56
5N 2.18 2.17 2.23 2.19
6C 1.31 1.07 1.86 1.47
6D 1.36 1.16 1.89 1.53
6H 2.28 1.97 2.77 2.40
6S 2.26 2.05 2.82 2.47
6N 1.73 1.74 1.75 1.74
7C 0.39 0.28 0.86 0.58
7D 0.39 0.29 0.91 0.61
7H 0.65 0.51 1.10 0.81
7S 0.65 0.59 0.89 0.73
7N 0.69 0.69 0.70 0.69
The first thing we do is to give the probability that each bid is
acceptable. Thus the first column indicates that pass is acceptable
on 36.93% of the hands -- provided that neither side is vulnerable.
The second column is for unfavorable vulnerability (pass is more
likely now!), the third for favorable vulnerability, and the fourth
for both vulnerable. The columns do not add to 100% because there is
likely to be more than one acceptable result on any particular deal.
To understand a typical entry, consider the 36.93% acceptability of
pass at love all. Half the time, passing will be wrong because it is
our hand. Of the remaining half, passing is wrong 13.07% of the time
because we are supposed to sacrifice against a game, partial, or slam.
At unfavorable vulnerability, sacrificing is right only 5.31% of the
time; at favorable, it's right on almost one hand in five.
On any given hand, we know that the number of bits of information that
can be exchanged is the log_2 of the number of sequences reaching an
acceptable contract. The average number of bits that can be exchanged
is as follows, as a function of vulnerability:
none unfav fav both
bits available 15.13 13.89 16.52 15.35
About 15 bits of information can be exchanged on any particular hand.
What about our second question? How many bits are _needed_?
To understand the answer to this, suppose that we have a hand where we
can indeed make 2NT or 3C. Now we don't really care if we end up in
1NT, 2NT, 1C, 2C or 3C. In fact, if we were trying to determine our
safe level on this hand, we could answer with any of these contracts
and be completely content, since we would then be led to make an
acceptable bid. Here is a table similar to the one above, giving the
chances that the safe level is any particular value as a function of
vulnerability:
none unfav fav both
P 2.40 6.33 0.89 2.34
1C 0.86 1.45 0.42 0.83
1D 1.23 1.80 0.61 1.19
1H 1.70 2.23 1.02 1.68
1S 2.29 2.76 1.46 2.20
1N 1.53 1.50 1.61 1.52
2C 2.48 2.63 1.86 2.37
2D 3.23 3.41 2.62 3.11
2H 4.29 4.36 3.74 4.16
2S 5.83 5.88 5.26 5.75
2N 2.64 2.59 2.66 2.64
3C 4.31 4.22 4.05 4.25
3D 5.29 5.10 4.99 5.21
3H 6.23 5.96 6.02 6.16
3S 7.19 6.85 7.07 7.15
3N 3.67 3.64 3.73 3.68
4C 3.59 3.14 3.71 3.54
4D 4.07 3.64 4.28 4.05
4H 5.59 5.01 6.01 5.59
4S 6.41 5.51 7.28 6.39
4N 3.26 3.11 3.37 3.26
5C 1.89 1.49 2.47 1.95
5D 2.28 1.74 2.98 2.29
5H 3.32 2.72 4.07 3.32
5S 3.46 3.06 4.02 3.50
5N 2.16 2.15 2.18 2.16
6C 0.95 0.78 1.28 1.01
6D 1.17 0.98 1.49 1.24
6H 1.34 1.15 1.64 1.41
6S 1.54 1.36 1.95 1.69
6N 1.72 1.72 1.73 1.72
7C 0.32 0.22 0.65 0.45
7D 0.37 0.27 0.81 0.55
7H 0.35 0.26 0.75 0.51
7S 0.35 0.29 0.59 0.44
7N 0.69 0.69 0.70 0.69
Since the safe level is uniquely determined from the deal in question,
these figures _do_ add to 100%. In the example we are considering, we
would be happy with a safe level of 1C, 1NT, 2C, 2NT or 3C -- a
combined percentage of 11.82%.
Let's say that instead of 11.82%, we were looking for a safe level
corresponding to 12.5%, or 1/8. This corresponds to three bits of
information, since in order to determine that a hand is in a class
that is one eighth as large as the entire sample, we need to ask three
yes/no questions and get specific answers to each. In general, if we
denote by p the probability that a _random_ hand has a safe level that
corresponds to an acceptable contract on _this_ hand, the number of
bits we need to exchange to find an acceptable contract is log_2(1/p).
For p = 11.82%, we see that the 2NT/3C hand can be identified using
3.08 bits of information.
We can now go through our library of 132,528 hands and see how many
bits of information need to be exchanged on each. Here are the
results, as a function of vulnerability as usual:
none unfav fav both
bits avail 15.13 13.89 16.52 15.35
bits needed 3.83 3.65 3.89 3.75
ratio 3.95 3.81 4.25 4.09
In general, we _could_ exchange about four times as much information
as we _need_ to. A bidding system needs to have an efficiency of
about 25% in order to be effective -- and, as we argued quite some
time ago, that seems to be about how effective our bidding systems
typically are.
Before moving on, let me point out that the above figures are in some
sense only a bound on how effective a bidding system might be. There
are many impediments in practice to our exchanging a maximal amount of
information: The opponents may interfere, the information may be
available to one partner only, and the type of information that is
useful on one hand may be worthless on another. The above
calculations make no allowances for any of these factors.
Nicholas E. France
L. Ginsberg)
Mr. Ginsberg requested help in how to go about developing a
"scientific" bidding system using his double dummy results. Their
seems to be two problems that need to be overcome and neither of them
seem easy to solve.
First, since we are assuming inperfect information in the bidding
system, game theory would suggest that in game as complex as bridge no
one pure strategy is best. In many instances, a combination of pure
strategies is best. To do this, we first have to make an assumption of
the strategies that are available to the opponents and then find what
mixture of pure strategies will guarantee us our best result.
Second, The definition of efficient bidding system is open to
discussion. Mr. Ginsberg defines it as "the number of meaningful
sequences in that system". I would define it as a system that gets to
the optimal contract in the least number of bids. In many instances,
this would be the complete opposite of Mr. Ginsberg's definition.
I believe the best use of the double dummy program is in showing what
the best choice of bids is in a specific instances. As an example,
Most American systems play 1H-3H as a limit raise with 4+ trump
support. I almost never decline the invitation. The double dummy
program could help in deciding when the invitation should be turned
down. A second example would be to decide whether or not to change to
Bergen raises of major suits as opposed to the above limit type raise.
Mr. Kaplan in the introduction to Mr. Bergen's book, stated that he
thought Bergen raises would get you too high in more situations than
were necessary. The double dummy program would be effective in
resolving something like this.
Other people have pointed out other effective uses of the double dummy
program. (i.e. Is the lead of an Ace against the slam a good choice.)
If Mr. Ginsburg is going to proceed in developing a good system. He
needs to make a lot of assumptions as to how the opponents will be
bidding. The problem is that there does not seem to be a system that
is used by the majority of bridge players in a consistant manner.
I wish Mr. Ginsburg all the success in the world but this time I think
he is trying to do more than his program can accomplish
Kit Woolsey
importance of telling the opponents about our hands, I believe there is
still a major difficulty involved with using the DD engine to evaluate
systems. It is the system definition. We aren't talking just about
12-14 NT vs. 15-17 NT. In order for a system to be evaluated by the DD
engine, it would have to be a completely defined system which took into
account every possible contingency (both bidding sequence and hand type)
which might occur.
Such definitions have been done, of course -- the bridge playing programs
need to have this. However these programs do not bid particularly well,
as we all know. I think if we tried to use the DD engine to compare
system A (a weak NT system) with system B (a strong NT system), all the
results would show would be which system was programmed more cleverly and
more thoroughly. It would not show which bidding structure was better.
Kit
Matthew L. Ginsberg
that makes it clear that I am either confused (always a possibility),
or still have not managed to explain clearly what I intend to do (as
soon as I stop posting clarifying messages).
Kit Woolsey wrote:
In order for a system to be evaluated by the DD engine, it would have
to be a completely defined system which took into account every
possible contingency (both bidding sequence and hand type) which might
occur.
Chip Martel echoed this concern in private e-mail, arguing that the
space of possible bidding systems was too large to search in any
practical way. Eddie Grove expressed similar doubts.
I don't understand why this should be true, because I believe it is
possible to evaluate one's "current position" in an ongoing auction
WITHOUT knowing the details of the bidding system you will use from
this point onward. This evaluation is based on a comparison of the
number of bits one has to exchange with partner in the subsequent
auction, and the number of bits one expects to _need_ to exchange.
Now, there are a variety of reasons that you can't exchange all the
bits you have room to. The opponents may interfere. The information
may be available to one partner only. And so on. But it strikes me
as a priori reasonable that you will, on average, get to exchange a
fairly constant fraction of the maximum information that you might
exchange. This fraction is not really likely to depend on level (if
you're higher, the opponents are less likely to interfere, but there
is less information available to be exchanged in any case), particular
hand, etc.
So what I propose to do is to compare systems using the ratio of the
bits needed to the bits available. Given the opening bids only, I can
evaluate Precision and say, "After the opening bid in Precision, there
are typically 13.2 bits available to be exchanged and 3.18 required,
a ratio of 0.241." Looking at Standard American, I might show that
there are 12.8 bits available (SA bids 1C less frequently, so will
have fewer bits available) and 3.16 needed, a ratio of 0.247.
This would mean that the opening bids in Precision are more efficient
than the opening bids in SA. Of course, we will still need to find
effective followups, but we can do that _after_ settling on the
meanings of the opening bids. What I propose to do is to select
opening bids based on the required efficiency of the bidding that will
follow.
Chip also wrote:
Frequent use of low bids leaves lots of room for your side, but also
makes it easy for the opponents to get in and describe their hands
... [and preempt].
With regard to allowing the opponents the opportunity to describe
their hands, my intention was to cover that in my last post, saying
that I would evaluate one's standing at a particular point in an
ongoing auction by fixing estimates for the efficiencies of our
methods and those of the opponents. Given those estimates, it is
possible to compute how many IMPs we will lose per board due to
bidding inaccuracy. Making our bidding more accurate by 0.1 IMP while
allowing the opponents to improve theirs by 0.5 IMP is clearly a
losing proposition. So Chip's first point is covered directly by the
techniques I am using.
The second is more subtle, and has two distinct aspects. For the
first, let me quote Chip again:
it should be at least somewhat resistant to your opponents taking away
your space (big clubbers with relays tend to do a lot better in
bidding contests with silent opponents than at the table).
The system I am designing _is_ resistant to the opponents taking away
space, in that it is trying to find a way to reduce the required
efficiency of the subsequent auction. That is, I would argue,
_exactly_ what "resistant to the opponents taking away space" means.
In practice, of course, this will depend on the ability to bid as
efficiently over interference as in an unobstructed auction. For a
system designed (and memorized!) by machines, that should not be an
issue.
The second aspect of interference is the argument that it is important
to get the bidding to a high level early because this will make it
difficult for your opponents to interfere, and _thereby_ improve the
efficiency of your subsequent auction (by removing a source of
inefficiency).
This is an interesting observation, and I think it has merit. But I
also believe that it is "2nd order" in that the differences between
the observed efficiencies of human bidding systems (.25 or so) and the
available efficiencies of machine-designed systems are going to be
large enough to swamp the above effect. Of course, that's just my
belief.
Chip has two further points to make. One has to do with the fact that
you don't want the auction to guide the defense. As I've said before,
I have no way to deal with that. How important it is appears to be a
matter of some debate in the rgb community. Chip's last point is that
"for humans there is the practical matter of remembering what you are
playing." This is indeed a problem. I'll have a little to say about
it in a future post, but not a lot.
Finally, Grove also wrote:
I find it hard to believe that you are as clueless as these recent
postings make you appear ... If you plan to make an impact in the
future, don't flush your reputation down the drain with that kind of
nonsense.
I plan to make an impact by designing a bidding system so much more
effective than existing methods that high level competitors have no
_choice_ but to use it. I plan to make an impact by using that system
to relieve Zia of his spare million pounds.
Matt Ginsberg
Nick Straguzzi
lnre...@ix.netcom.com(Nicholas E. France ) wrote:
>I wish Mr. Ginsburg all the success in the world but this time I think
>he is trying to do more than his program can accomplish
There's an old saying: The reasonable man adapts to fit his environment. The
unreasonable man attempts to adjust his environment to fit him. Therefore,
all human progress depends on the unreasonable man.
Matt, thankfully for we supporters of computer bridge, is an unreasonable man.
:-)
Nick
|---------------------------------------------------------------------
| Nick Straguzzi |
| Mullica Hill, NJ | "Got no use for the tricks of modern times"
+---------------------+ -- Al Stewart
| nstra...@snip.net |
+---------------------------------------------------------------------