[helene_t]

tysen2k, on Jun 22 2010, 07:35 PM, said:

In the extreme case of 1 bidding round, opener makes a bid and partner has to place the final contract. I think it would be very interesting to find out how opener would design the bids to give the maximum amount of valuable information. Extending it to 2 bidding rounds would be much more reasonable and produce an efficient system given that there is no interference.

I think that is a good idea. Good to see you here again, Tysen

Han is of course right that 2 rounds is much more complex than one round. But even if the scope of the project is to develop a system that could cope with an unlimited number of rounds, it may still be a reasonable starting point to construct the opening scheme on the assumption that responder will have to place the contract immediately. Then responder may not necessarily place the contract, but make a descriptive bid that allowed opener to place the contract as effectively as possible. Etc.

HotShot: Basically, a good system is a system that wins a lot of MPs (or IMPs or w/e) in the tourneys that we let them play. So after then hands have been bid, they will be played by a DD solver or by looking them up in BridgeBrowser or in some other way. This is straight forward. It is a little more tricky if we restrict us to uncontested auctions, since for example if opps are cold for 7NT while we can make size tricks in hearts, passing the board out would lead to the maximum score but we would say that opening 4♥ or something would be better. So one could restrict the training DB to deals where it is in some sense plausible that opps won't interfere.

Richard/Han: Why would you penalize complex systems? Akaike's criterion is meant to avoid overfitting. This may or may not be relevant depending on how we construct construct the systems. Or is it that you think that simplicity is a virtue in itself, regardless of the overfitting issue?

[hanp]

I would think about penalizing large systems because as a bridge player, I would be more interested in a system that can be written in 10 pages than a system that uses 100 pages, especially if the difference in performance is small.

For example, a 1C opening that can be described as "4+ clubs, 12+ HCP" or "15+ HCP" or "less than 12 HCP" would be preferable to me over a 1C opening that takes 15 minutes to read.

Also, it might be preferable to find a system that uses similar rules for many different auctions instead of a huge dictionary containing millions of auctions and their meanings.

[junyi_zhu]

helene_t, on Jun 22 2010, 10:08 PM, said:

tysen2k, on Jun 22 2010, 07:35 PM, said:

In the extreme case of 1 bidding round, opener makes a bid and partner has to place the final contract.  I think it would be very interesting to find out how opener would design the bids to give the maximum amount of valuable information.  Extending it to 2 bidding rounds would be much more reasonable and produce an efficient system given that there is no interference.

I think that is a good idea. Good to see you here again, Tysen

Han is of course right that 2 rounds is much more complex than one round. But even if the scope of the project is to develop a system that could cope with an unlimited number of rounds, it may still be a reasonable starting point to construct the opening scheme on the assumption that responder will have to place the contract immediately. Then responder may not necessarily place the contract, but make a descriptive bid that allowed opener to place the contract as effectively as possible. Etc.

HotShot: Basically, a good system is a system that wins a lot of MPs (or IMPs or w/e) in the tourneys that we let them play. So after then hands have been bid, they will be played by a DD solver or by looking them up in BridgeBrowser or in some other way. This is straight forward. It is a little more tricky if we restrict us to uncontested auctions, since for example if opps are cold for 7NT while we can make size tricks in hearts, passing the board out would lead to the maximum score but we would say that opening 4♥ or something would be better. So one could restrict the training DB to deals where it is in some sense plausible that opps won't interfere.

Richard/Han: Why would you penalize complex systems? Akaike's criterion is meant to avoid overfitting. This may or may not be relevant depending on how we construct construct the systems. Or is it that you think that simplicity is a virtue in itself, regardless of the overfitting issue?

I think Man-made systems are actually quite good in many basic areas. The key problem for computer to bid well is not only the hand evaluation problems computers may face. One basic problem is how computer can devise a good sequence and achieve the right and useful information to make important decisions. This is not a problem of language, but more close to a problem of writing a novel or painting, which needs some careful planning and insights. A lot of people can speak English, but few can use it accurately to achieve their goals. In this sense, bidding is not only information sharing and hand evaluation, but also careful planning, insights of rare situations where you can make money to make a difference and others may ignore and bid a second best or third best contract. Of course, neural network may help discover some insights of hand evaluations at early stage of bidding that we may ignore, but so far, I don't find many from the limited literature research I did.

[hrothgar]

helene_t, on Jun 23 2010, 01:08 AM, said:

Richard/Han: Why would you penalize complex systems? Akaike's criterion is meant to avoid overfitting. This may or may not be relevant depending on how we construct construct the systems. Or is it that you think that simplicity is a virtue in itself, regardless of the overfitting issue?

1. I do believe that simplicity is a virtue in its own right. I was always taught to start with the simplest / most parsimonious model and only introduce more complicity when absolutely necessary.

2. Neural Networks are (essentially) just a complicated applied example of regression. Training is nothing more than using gradient descent to minimize the sum of the squared residuals. It seems right and proper to introduce methods to protect against overfitting.

3. The notion of bias - variance trade off seems very appropriate to this type of modeling. I'd like to be able to understand the extent to which your results depend on the specific training database you're using.

[tysen2k]

I think that the value that we would get out of this exercise is not necessarily a new bidding system that you would try to use out of the box, but rather some additional insight into system design. You look at the developed definitions, see if you can understand the rationale behind them, then use that rationale in a simpler context that humans could use.

I see it as giving some insight into the high-level questions of "how do I balance shape vs. strength in my priorities?" and "how much priority should I give to the majors over minors?"

[NickRW]

helene_t, on Jun 22 2010, 10:08 PM, said:

...Why would you penalize complex systems?...

Well, restricting to 1 or 2 rounds would have to be a simplification for early stages. And, if you were interested in creating a system to be played by computers against computers, then, sure, lots of complexity might be OK.

However, if you want a system that humans might take up in any numbers, then it, or at least a cut down version, has to be fairly simple. For example, Precision took off, when it did, partly due to the hype and partly due to the fact that the basic system was essentially fairly natural - unlike some other big club offerings. Or to give another example, my daughter and I have 20 pages of densely packed, type written notes just on our system over 1NT - but it has taken well over - I dunno - probably 100 man hours to craft and learn - maybe 200 - I really don't know - a lot anyway - and we're still working on the more obscure bits - most folks cannot or will not put in anything like as much work for the sake of gaining on about 4% of the 1NT boards compared to our previous methods. Worse still, nobody else I know plays it - so it is effectively a one off piece of learning not reusable.

Nick

[tysen2k]

helene_t, on Jun 22 2010, 03:08 PM, said:

Good to see you here again, Tysen

Yes, I know it's been quite a while...

Quote

it may still be a reasonable starting point to construct the opening scheme on the assumption that responder will have to place the contract immediately. Then responder may not necessarily place the contract, but make a descriptive bid that allowed opener to place the contract as effectively as possible. Etc.

I was thinking along the same lines...

Tysen

[bab9]

hanp, on Jun 22 2010, 01:42 PM, said:

The original thread was about bidding systems designed by a computer, not about bots that can bid. The two things are of course closely related, but not quite the same. If your goal is to get a good bridge playing computer program, your standards are much higher than if you want the program to develop a system that performs well under some tests.

For example, if we look only at uncontested 1NT structures, then we could give the bots a quite limited dictionary. Every bid by responder might mean only one of these:

1. Bid the next step.

2. If your hand satisfies [this], do [that], .... .

3. To play.

To simplify further, we might only tell the bots their shape plus their number of highcard points. Purist might object, but if the goal is to come up with bidding systems rather than optimal hand evaluation methods, such a simplification could be quite valuable. (at least in the beginning)

Once we have two functioning structures, we can test them against eachother by only dealing 1NT openings for opener (using whatever standards you like).

It took decades to develop a computer chess program able to bet a grand master. To expect a first generation bridge bidding system to out perform a man-made system is a bit unrealistic.

However, a computer generated bidding system can give new insights in system construction and possible alternative meaning for bids. To artificially simply a potential system at this stage my limit potential future insights. It may also result in the local minima/maxima others have indicated.

To look at the simplified situation of first 1/2 rounds of bidding is a great idea, especially as it may help in the eventual coding of a complete system.

While the system may eventually be implemented by bots, the bidding insights obtained in the meantime will help make better man-made bidding systems and conventions.

[tysen2k]

I made a bit of progress into having a system that's completely computer designed. I designed it by using some information theory concepts and used a neural network to define bids that minimize the entropy of perfect contract distributions. I know that's kind of a high-level description... I can go into more detail if desired.

I'm trying to figure out a good way of presenting the system. Since it was designed by a NN, it's not too easy to put into human terms. So the real system is more detailed than this, but if I were a human trying to play as close to this system as possible, but still have it easy to memorize, then I would play this:

For all bids, points don't matter. All that matters is the suit shapes, so bids are essentially 0-37. The only exceptions are preempts. I decided not to try and define preempts, mostly for simplicity. But basically you should decide what your favorite preempt structure is and then use that. Simply preempt instead of making one of these bids here. You can even start using 2C as a preempt because the network decided that it didn't want to assign a constructive meaning to it.

Pass - all hands with 4+ spades
1C - all balanced hands with 2-3 spades, plus 6322 and 5422 hands with long hearts
1D - 5+ diamonds, unbalanced, 0-3 spades
1H - 5+ clubs, unbalanced, 0-3 spades, 0-4 hearts, 0-4 diamonds
1S - 5+ hearts, 0-3 spades, must have singleton/void somewhere
1N - 6+ clubs with two singletons/voids

One disclamer is that the model doesn't consider right-siding of contracts. It always assumes it will declared by the player that can take the most tricks.

I think I'll create a nice, graphical way you can see the whole solution which has more detail, including a little dependence on strength, but that dependence was minimal. I think I'd like to call this system the "Silent Spade."

So the interesting things about this system from my point of view is that:

• Shape dominates points
  
• Having pass eliminate all 4+ spade hands helps out all other bids
  
• Opening with balanced trash is not all that bad
  
• It doesn't mind a forcing pass, but all bids should have shape meaning.
  
• The higher the opening bid, the more shapely the hand must be

Tysen

[NickRW]

tysen2k, on Jun 29 2010, 09:38 PM, said:

I made a bit of progress into having a system that's completely computer designed.  I designed it by using some information theory concepts and used a neural network to define bids that minimize the entropy of perfect contract distributions.  I know that's kind of a high-level description... I can go into more detail if desired...

Not to be picky, but I think you need to go into quite a bit more detail than that. Earlier we were talking about limiting the number of rounds of bidding, perhaps down to even just one - with opps silent. An enormous simplification - and the fact that you've come up with essentially constructive meanings (albeit pointless, if you'll pardon the pun ) suggests that some sort of such limitation has been applied - but you don't say what.

Or are the replies, such as may have been allowed, all kinda assumed to be optimal - which is what your earlier information theory work assumed - and somehow you've got information theory in use here.

Not even really sure how information theory fits in with neural nets anyway! I'm reasonably well up on much of this stuff but, "information theory concepts and used a neural network to define bids that minimize the entropy of perfect contract distributions" kinda leaves even me saying WTF?

Nick

[tysen2k]

NickRW, on Jun 29 2010, 03:41 PM, said:

Not to be picky, but I think you need to go into quite a bit more detail than that.

Yeah, sorry, I should have at least put in a little more detail into it. I just didn't want the entire post to be about the process since it would require a long explanation. I'll write some more detail up soon.

Tysen

[tysen2k]

Okay, a bit more information on how I came up with these opening bids. I rate the openings by how much “information” is given in the bid compared to how much bidding space is taken. I used the entropy concept (defined below) from information theory around the distribution of best contracts. The basic story is that a bid is a “good” bid if it helps concentrate its distribution of best contracts. So a bid defined as having a lot of spades will tend to have a high percentage of 2S/3S/4S… and so that is a good bid, provided of course that it’s not too specific because that will leave a lot of junk left over for the other bids to handle.

An example. Start with a large sample of double dummy hands. Before any bidding begins and you have a random hand, your distribution of perfect contracts looks like this:

 P  2.2%
1C	0.8%
1D	1.2%
1H	1.7%
1S	2.2%
1N	1.5%
2C	2.7%
2D	3.3%
2H	4.2%
2S	5.8%
2N	3.0%
3C	4.6%
3D	5.3%
3H	6.2%
3S	7.3%
3N	3.6%
4C	3.2%
4D	3.9%
4H	5.7%
4S	6.5%
4N	3.3%
5C	1.9%
5D	2.3%
5H	3.2%
5S	3.7%
5N	2.0%
6C	0.9%
6D	1.1%
6H	1.5%
6S	1.5%
6N	1.7%
7C	0.2%
7D	0.3%
7H	0.3%
7S	0.5%
7N	0.7% 

In information theory, entropy represents how much uncertainty there is around the distribution. Before any bidding starts there is quite a bit of uncertainty as to the best contract. To get the entropy, you multiply the chance of each bid happening by the logarithm of that chance and then add them all up. If you use base 2 for the log, then the number you get will in units of bits. So you take 2.2% * log(2.2%) + 0.8% * log(0.8%) +… and so on. I get 4.83 bits as my starting entropy.

Then you use whatever means you want to decide how each hand bids (it doesn’t have to be a NN). Measure the entropy of each bid definition and weight them according to how often that bid is actually made. For example, my network’s 1S opener now has the following distribution of best contracts:

 P  0.1%
1C	0.1%
1D	0.1%
1H	0.9%
1S	0.3%
1N	0.1%
2C	1.0%
2D	1.0%
2H	5.3%
2S	1.6%
2N	0.7%
3C	2.6%
3D	2.2%
3H	10.1%
3S	2.0%
3N	2.1%
4C	3.9%
4D	2.0%
4H	18.7%
4S	2.5%
4N	2.9%
5C	0.3%
5D	3.4%
5H	15.0%
5S	0.9%
5N	1.5%
6C	0.9%
6D	1.7%
6H	9.1%
6S	0.8%
6N	2.8%
7C	0.7%
7D	0.7%
7H	1.4%
7S	0.1%
7N	0.2%

And its entropy is 4.13. Concentrating the best contracts into as few as possible is basically what we’re trying to accomplish here. The concetration into heart contracts has reduced the entropy.

But unfortunately this is only half the story. The entropy tells us how many bits of information we need to land in the right contract, but we usually will not have enough time/space to fully exchange the needed info. We need a measure of how many bits of information are available for us to use during bidding. We’re only defining opening bids here, so how will we know how good the opening bids are without defining all of the follow-ups, rebids, etc.? Most of this concept comes from Matt Ginsberg, and he and I describe it in several RGB posts several years ago. I also used a similar concept in my bidding system design contest I held, but I’ve modified it slightly. This is a way where you can quantitatively measure the information passed by your openings without having to define what your follow-ups are.

If your best contract is 1H, how much info can you exchange to get there? Well if you start with an opening pass, there are exactly 4 bidding sequences:
P-1H
P-1C; 1H
P-1D; 1H
P-1C; 1D-1H

4 sequences is 2 bits of information (2^2 = 4). To get to 1S after an opening pass there are 8 sequences or 3 bits. Basically each level gives you 1 more bit. But our bidding is never 100% efficient and there are a number of reasons. First, we can’t define rules that allow us to use the space 100% effectively because we have to use features like card length, points, honor placement, etc. and we only know our own hand, not the other 3 players. Second, our opponents will sometimes bid, taking away our bidding space. So you have to set your efficiency to some low number (I actually used 10%). That means to stop in 1S, I don’t have 3 bits of info available, I only have 0.3.

Each best contract will have a certain number of bits needed to find it (the entropy) and there will be a certain number of bits available. Usually we have fewer bits available than we need, so we’ll miss the contract some of the time. Plus our opening might have overbid. If we open 1S and the best contract is 1H then we’ll never reach it. So to sum it all up, basically what I’m doing is trying to find a set of opening bids that if I compare the amount of info each bid gives and the amount of info I need/have on follow-ups, I can maximize the chance that I’ll find the best contract.

To make it feasible to get a solution I did partially eliminate competitive bidding. The model does expect that it will occasionally get interference (it has low efficiency and so might not have enough bits of information in future rounds of bidding). However, it does not go out of its way to make it hard for the opponents to bid. But hopefully your preempts will take care of most of this problem. I purposely used a low efficiency of follow up bids to counter the fact that these definitions aren’t trying to interfere.

In the end, it’s not perfect, but no measuring method ever will be. But it is a way to quantitatively define how good your openings are. I haven’t seen a better method to rate bids, but I’d love to hear about one.

This was a fun experiment, and take it for what you will. It was also fun to watch the preferences evolve over time. The initial conditions are totally random bids. Then it realizes that if all the opening bids are pretty much random, then it might as well start with a pass so that it has the most bidding space with its follow-ups. So it starts to evolve towards passing almost all the time. But then it realizes that it’s not getting any differentiation with always passing… so it begins exploring other bids, starting with 1C, then 1D, etc.

Tysen

[NickRW]

tysen2k, on Jun 30 2010, 12:27 AM, said:

Okay, a bit more information on...

Thanks. I am at least vaguely tracking with you now. To my rather practically oriented mind, your one liner description earlier, that I couldn't quite decipher, means roughly what I thought it should mean!

I am dredging through the memory banks now - but didn't Matt Ginsberg start with assuming an efficiency of something like 25%. And then he thought, after spending a lot of cpu cycles, that this figure was a little high - or you did - and something like 20% was used???? I vaguely recall something like that.

You see, where I am coming from on this, is that (though I think the "Silent Spade" is sexy), there is something fishy about the result. Your system is basically finding no constructive meaning for anything above 1NT - which is weird to me. For example, a conventional 2♣ opening meets (mostly) "pass" from opps - and in such auctions you are getting a lot better than 10% efficiency. So I find it surprising that no opening (or pass) is allocated a forcing from strength meaning - especially when it only wants to allocate 5 of the possible bids.

I realise that your time may be as limited as everyone else's - but what happens if you up the efficiency to 20% - or (maybe better, if more complex) up it in proportion to the minimum hcp guaranteed?

Nick

[gwnn]

tysen when are you gonna show HCP as well as shape? i don't get it.

[NickRW]

gwnn, on Jun 30 2010, 01:05 AM, said:

tysen when are you gonna show HCP as well as shape? i don't get it.

That was kinda what I was saying dude!

[gwnn]

well dude I mean speak English or something

[tysen2k]

NickRW, on Jun 29 2010, 05:54 PM, said:

but what happens if you up the efficiency to 20%

Actually I started off with a 20% efficiency. It had the opposite effect of what you are hoping for. It wanted to keep its opening bids even lower because it thought that the responses would be much better. It didn't want to eat up any bidding space at all and reluctantly bid up through 1S.

Tysen

[tysen2k]

Here is the system in all its glory:



Okay, we’re looking at 4 dimensions here: spades, hearts, diamonds, and HCP. Clubs can be figured out once you’ve defined the other 3 suits. There are several 7x7 blocks of bids that each contain the same number of hearts and diamonds. For example, the 7x7 block in the bottom left are all the hands with 0 hearts and 6 diamonds. Within each block are all the subdivisions by number of spades and HCP. The colors correspond to the opening bid spelled out in the legend.

I figured this is a nice and compact (and colorful!) way to show all the possible hands.

Tysen

[bab9]

It is interesting that the system wants to bid 1NT with unbalanced hands. Has the information presented been based on 10% or 20% efficiency?

[rbforster]

Nice graphic, Tysen!