[bab9]

Does anyone know if there is a bidding system that has been created by a computer? If so, what is it called, and where can I find information on it?

[blackshoe]

COBRA.

Computers aren't creative. A computer didn't create this, a human did. But he created it for a computer to use.

[the hog]

Cobra, designed by Lindelhof.

[hanp]

I've made a very small start on writing a computer program that would build a bidding system. The idea is to start with something very simple (preferably nothing) and to apply evolution to it.

At every stage we make many small changes to the existing systems, and then let the new programs bid against eachother. The programs that do well multiply, those that do badly die off, and again small changes are made to the new programs.

So far I've only wrote the code for the simple situation where one partner gets dealt a 15-17 1NT opening, and the other partner can either pass or bid 3NT. The opponents are silent.

I doubt that our project will lead to a competitive bridge system, but hopefully it will be interesting.

[helene_t]

I wrote a program that optimized a system in which only notrump bidding was allowed (!), using evolutionary principles as Han described. I don't remember the exact notrump ranges it came up with, just that it opened much lighter in 3rd/4th seat than 1st/2nd.

I have been thinking about how to generalize this to something more realistic. The problem is how to parametrize the system. When only notrump bidding is allowed, then the system can basically be described by a handful of parameters:
- 1NT opening is at least X1 hcps.
- 2NT opening is at least X2 hcps.
- 3NT opening is at least X3 hcps.
- Invite after 1NT opening is at least X12 hcps.
- Game after 1NT opening is at least X13 hcps.
- Accept invite is at least X123 hcps.
- Game after 2NT opening is at least X23 hcps.

This is just 7 parameters. Distinguish between 1st/2nd and 3rd/4th seat makes 14 and with slam bidding added (I didn't do that but it would be doable) would make it something like 60 parameters I think. But if we allow suit bids also the combinatorics explode, also because the scope for rules that rely on suit length also (and maybe even suit quality, control, stoppers) is much larger than the scope for rules that depend on HCPs only.

One way to simplify it a little is to say that the meaning of a call depends only on
- what information have I already shown?
- what information has partner already shown?
- what is the last bid (and has it been doubled/redoubled)?
- will partner get another turn if I pass?

But even so, the scope for rules is enormous.

Should a bidding system be modeled as a decision tree?

Or should it be modeled as some kind of loss function, so that you chose among all legal calls the one that has the smallest loss?

Or maybe, since we want to use evolutionary principles to optimize it, make a neural network where there is a simple link from genetic alleles to parameters of individual neurons?

[Fluffy]

why use HCP if you are using computers?

[gwnn]

Are you suggesting ZARs Fluffy?

[helene_t]

Fluffy, on May 25 2010, 12:37 PM, said:

why use HCP if you are using computers?

Yeah good point.

In principle it wouldn't make the algorithms more computationally expensive to use some long-haired evaluation method, for example based on http://forums.bridge...showtopic=32125

For the purpose of getting some experience with the basic algorithm design I wanted to keep the code clean so just used HCPs.

[hrothgar]

Cluster analysis provides an interesting analogy:

Cluster Analysis is a type of unsupervised learning in which you partition a set of observations into N subsets.

One broad class of clustering algorithms is based on divisive methods. You start with one large data set and then start chopping them into dissimilar pieces. There are other clustering algorithms that are based on agglomerative methods. You start with a large cloud of singletons and start grouping them with like minded individuals.

In much the same vein, Helene and Han both seem to be looking at the early branches of the auction. Personally, I think that it would be useful to flip the problem on its head and try to construct a rules set for terminating an auction. The problem seems much more constrained and therefore simplier.

In its purest form, you might consider a problem like the following:

1. Relay Responder has just bid 4♦
2. The relay captain knows responder's precise shape as well as the number of slam points held.
3. The captain needs to determine whether to sign off in game or explore for slam.

If you can't solve this problem, I don't think you're going to get to far working from the other end...

[Fluffy]

gwnn, on May 25 2010, 11:40 AM, said:

Are you suggesting ZARs Fluffy?

not ZARs, but rather a potential trick taking average on a simulation from partner's and opponent's likelly holdings, of course this is so slow, but if you can use computer experience to get a better evaluation method, you are gaining something.

[bluecalm]

Interesting projects you get there guys.
While I don't believe that it's possible to build good complete bidding system using evolutionary methods (at this stage) I am sure many interesting results can be achieved. Mainly answering judgment questions. I would love to hear more about any results achieved this way

[zenko]

Frankly I am surprised that this aspect of bridge theory is still in such a rudimentary phase, especially taking in account how many programmers play bridge.

To build whole "system" might be too overwhelming task at the moment, plus I am not sure what's the objective of that, a system is like car, among other things it needs to suit driver's/player's personality well.

Instead, I would suggest starting by solving some more isolated issues, for example effectiveness of opening 1NT with 5 card major, or even more narrow, say if you open 1NT with 5 card major, is it better to allow any 5M332 distribution or to require a tripleton on the other major (which is what Eddie Kantar recommends).

I am sure there are plenty of other bidding questions that can be answered with decent software and enough computing power (Namyats, Flannery, natural weak 2s or multi, etc).

[helene_t]

Hi Zenko,

There have been many such studies. These forums are full of simulation studies, evaluating the merits of various treatments.

This thread is about something several orders of magnitude more complex: to allow the computer to build a bidding system from scratch, with little or no human guidance.

[rbforster]

I had some ideas about taking limited parts of the bidding tree, such as pass-or-correct situations or best partscore bidding, and trying to have the computer optimize for conventions you should use to find the best fit. This is assuming a situation where your combined values are known to be not even enough to invite. An example might be scrambles over a weak assumed-fit preempt or, more constructively, the precision start 1♣-1♦-not 1♥ if you play 1♥ shows all forcing hands. You could try situations like (1N)-X-(P) too, where X shows a range of hands wanting to interfere over their NT, and where you'd like to know the best way to advance the double.

I think the combinatorics of assigning each reasonably common hand shape to a certain path down the bidding could be manageable (although large), and together with some careful calculations of conditional joint probabilities and a law-level fit function, you could optimize the shape assignment so that you achieved the best average fit. Then looking at which hands made which bids at each stage would tell you the convention(s) you want to use.

[blackshoe]

Now that I think about it, there was a neural networking program for bridge a while back. Bridge Partner? Something like that. The idea was that you'd play with the program, and it would (eventually) learn your system. I didn't have the patience for it.

[mycroft]

Why do I have images of Chthonic? "a 1C opener shows one of these 157,478,389,445 hands..."

[helene_t]

mycroft, on May 26 2010, 11:14 PM, said:

Why do I have images of Chthonic? "a 1C opener shows one of these 157,478,389,445 hands..."

Yeah, humans are just as unable to provide full disclosure as are waffle irons, but at least waffle irons don't pretend otherwise

[bab9]

helene_t, on May 25 2010, 11:20 AM, said:

This thread is about something several orders of magnitude more complex: to allow the computer to build a bidding system from scratch, with little or no human guidance.

As part of building a bidding system, should it be based on:

- double dummy results
- actual results by experts
- something else?

From what I briefly looked at, COBRA seemed to be double dummy based, and ZAR points (while not a system, it appears to be a different way to evaluate a hand) seemed to use actual results.

I understand that creating a computer based bidding system is a complex task. One reason for starting this thread was to see how computers might encode bids to determine the correct contact, and possibly the best hand to play it from; even if the system was artifically based on no bidding interference.

I would be curious to see if a computer would still come up with:

- transfers
- waiting bids
- relays
- bids with multiple meanings and/or HCP ranges.
- slam bidding using cue bids or control counts.

(doubles would have to wait until bidding interference was introduced).

Given that people have done a number of their our simulations, has anyone correlated all the results into one location?

[helene_t]

I will try to make a bidding system in which a decision tree is created on the fly each time a bidding decision is to be made.

Such a decision tree will make binary splits, based on either length in a particular suit (say: spades>4 go right, <=4 go left), or HCPs (say: HCPs>10 go right, <=10 go left).

There will be a one-to-one relation between legal "possible" calls and terminal nodes. By "possible" I mean that for example pass when partner is unlimited, or 7NT when our combined assets are limited to 23 HCPs, are not included.

The reason why no two terminal nodes will map to the same legal call is that it must be simple to decode the calls. With a one-to-one relation, the full information available to partner will always be of the simple form (c1<clubs<c2) & ...... & (p1<hcps<p2).

The decision tree is build up in a two-stage procedure. First, a tree is constructed in a way similar to what is used in the induction tree procedure in AI: start by identifying the (variable/cutoff) combination that conways the most useful information to partner. For example, if partner is likely to have four spades and we haven't found a heart fit, it is useful information to partner that I have at least four spades. Subsequently, for each of the two subsets identified by the root node, the algorithms is applied again, until some stopping criterion (say information exhausted or a depth of 8 is reached).

That tree will be too deep so it will need to be pruned, and terminal nodes will need to be assigned to calls. How this procedure works I am not quite sure. An idea is to start with the cheapest call and see if there is a node in the tree that would make that call useful in a nonforcing meaning, i.e. partner is likely to be able to decide that that call designates an acceptable contract. If no such node is found, one looks for a node that in some sense has an information content that is suitable for that call, i.e. the cheapest call must cover some 40% of all combinations, the second one (100-40)*40% etc. Among several candidates the node is chosen that has the lowest likely safety level.

This will quite easily generalize to contested auctions (you just have to factor in the information conveyed by opps when assessing what information partner is likely to need, for example if opps have shown length in spades we are not looking for a spades fit ourselves).

So which opening structure will this lead to? Suppose the algorithm is parameterized such that HCPs are deemed very important in the early stage. Then the root node and maybe both of the second-layer nodes split on HCPs. Probably the weakest of the four subtrees will map to "pass" since if you can tell partner you are weak, he is likely to be able to decide that passout is acceptable. Low-level suit bids will map to intermediate-strength hands with length in that suit, again because p will often be able to decide that 1♣ is an acceptable contract if it promises 5+ clubs. So the opening scheme might be something like:

pass: <14 HCPs.
1suit: 15-19 HCPs, 4- higher ranking suits, 5+ in the suit.
1NT: 15-19 no 5-card suit
2♣: 20+ HCPs.

A more major-oriented parameterization, i.e. a 4+ card major is deemed more useful info than a 5+ card minor, and at the same time with less emphasis on HCPs, may come up with something like:

Pass: 0-16, no 4-card major, no 6-card minor
1♣: 4+ spades, any strength
1♦: 4+ hearts, any strength

I envision one problem with this algorithm: since low-level openings (pass, 1♣) are assigned early the system will tend to over-emphasize the prospect of partner being able to pass out or pass a 1♣ opening, something that isn't really necessary since even if 1♣ is the optimal contract, we will usually have a safe spot at for example 2♣. Maybe the algorithm should be tuned to avoid making low-level nonforcing calls that are "unnecessary", for example by always factoring in the information/biddingspace thing even when making nonforcing calls.

[bab9]

helene_t, on May 31 2010, 05:25 AM, said:

I will try to make a bidding system in which a decision tree is created on the fly each time a bidding decision is to be made.

Such a decision tree will make binary splits, based on either length in a particular suit (say: spades>4 go right, <=4 go left), or HCPs (say: HCPs>10 go right, <=10 go left).

Are you going to allow the system to play in a Moysian fit?