Bidding system designed by computer

[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]

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.bridgebase.com/index.php?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]

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]

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]

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]

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?

[dake50]

Feels this starts at the wrong place. Start with "what really matters?"

Eg does 2hcp in 5332 matter? How much? At the 0.0003% level? if yes, why wasn't that precision postponed until the 0.5% effects are found and schemed?

"What's in the cards" before some edifice of bidding.!

[Free]

I think the definition of "(c1<clubs<c2) & ...... & (p1<hcps<p2)" is easy to program, but in reality it's useless for system design.

 

Just look at a simple example, the minimulti:

0-4♣, 0-4♦, 0-6♥, 0-6♠, 6-9HCP

 

Suppose you also play Muiderberg (2M = 5M, 4+m):

0-5♣, 0-5♦, 0-5♥, 0-5♠, 6-9HCP

 

The program will not be able to decide which opening bid it should choose when holding a 5-3-3-2 with 7HCP, while in fact it should just pass!

 

It's important to have clear definitions available, so you don't have multiple options.

 

If you can put it as one of multiple options, you'd have a lot better description:

minimulti:

- 0-4♣, 0-4♦, 0-3♥, 6♠, 6-9HCP

- 0-4♣, 0-4♦, 6♥, 0-3♠, 6-9HCP

Muiderberg 2♠:

- 4-5♣, 0-3♦, 0-3♥, 5♠, 6-9HCP

- 0-3♣, 4-5♦, 0-3♥, 5♠, 6-9HCP

Now we don't have a problem anymore, and the 5-3-3-2 with 7HCP won't choose any of these openings.

 

Another very simple example is balanced hands. You could say 2-5 cards in all suits, but then you'll allow 5422's (even with 5-4M) which is probably not what you want. A simple way to describe all balanced hands is to order your distribution high to low (the general form) and you need at least "3332". With your definition you need 4 options:

- 2-4♣, 3-5♦, 3-5♥, 3-5♠, 15-17HCP

- 3-5♣, 2-4♦, 3-5♥, 3-5♠, 15-17HCP

- 3-5♣, 3-5♦, 2-4♥, 3-5♠, 15-17HCP

- 3-5♣, 3-5♦, 3-5♥, 2-4♠, 15-17HCP

 

The simple definition is good enough to start with, as long as you allow multiple meanings.

[helene_t]

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

The system could certainly "decide" to pass what is known to be a Moysian, or what might be a Moysian. But I think I would say that the utility of the information that I have at least three spades is zero if partner is known to have exactly four spades. But if partner is known to have 4+ spades, the expected utility of the information that I have 3+ spades is positive since he might have five. Anyway, this is a parameter in the algorithm that should be optimized by the genetic algorithm (for example).

 

I think the definition of "(c1<clubs<c2) & ...... & (p1<hcps<p2)" is easy to program, but in reality it's useless for system design.

Yeah, this would probably turn out to generate rather ineffective systems.

 

I can live without the multi, but for example the 1♣ opening in SA would have to map to 11 terminal nodes in the tree:

- 11-21 hcps, 6+ clubs, 5- d/h/s

- 11-21 hcps, 5 clubs, 4- h/s, 1- d

- 11-21 hcps, 5 clubs, 4- h, 1- s, 3 d

- 11-21 hcps, 5 clubs, 4- s, 1- h, 3 d

- 17-21 hcps, 5 clubs, 4- h/s, 4 d

- 12-14 hcps, 4 clubs, 4- h/s, 3- d

- 12-14 hcps, 3 clubs, 4- h/s, 3- d

- 12-14 hcps, 5 clubs, 3- d/h/s

- 18-19 hcps, 4 clubs, 4- h/s, 3- d

- 18-19 hcps, 3 clubs, 4- h/s, 3- d

- 18-19 hcps, 5 clubs, 3- d/h/s

 

The decision tree with one-to-one mapping between terminal nodes and "possible" calls is just a first step, to make it useful I would have to either use a completely different formalism, or to allow calls to map to multiple nodes.

 

Maybe there is a simple formalism that would cover a more useful range systems.

 

As for the idea of allowing general forms such as "3332" as opposed to "[3332]", I think it is too narrowly targeted at balanced hands. I mean would you want an opening dedicated to, say, 5431? I know some systems have a concept of a generic 4441 but I think that is a suboptimal choice that has been made because it is easy to remember. I think it is arbitrary to bundle [4441] with [4144], you might as well bundle [4441] with, say, [5521].

[zenko]

 

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.

 

AKxxxxxxxx

x

x

x

 

 

x

Axxx

Axxx

Axxx

 

laydown 7NT, with 4 HCPs to spare!

[bab9]

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

The system could certainly "decide" to pass what is known to be a Moysian, or what might be a Moysian. But I think I would say that the utility of the information that I have at least three spades is zero if partner is known to have exactly four spades. But if partner is known to have 4+ spades, the expected utility of the information that I have 3+ spades is positive since he might have five. Anyway, this is a parameter in the algorithm that should be optimized by the genetic algorithm (for example).

 

I think the definition of "(c1<clubs<c2) & ...... & (p1<hcps<p2)" is easy to program, but in reality it's useless for system design.

Yeah, this would probably turn out to generate rather ineffective systems.

 

I can live without the multi, but for example the 1♣ opening in SA would have to map to 11 terminal nodes in the tree:

- 11-21 hcps, 6+ clubs, 5- d/h/s

- 11-21 hcps, 5 clubs, 4- h/s, 1- d

 

If you are going to use a genetic algorithm, what form will your cost function take? Will it be based on double dummy, or actual results? How big is your sample size likely to be?

 

If you are going to use a genetic algorithm, why not let it determine the ranges and card counts, as an alternative to starting with a decision tree?