Bidding system designed by computer

[hotShot]

Looks to me like it saying there are more spade contracts in the database than anything else, therefore when I have spades I want to bid cautiously - hence the spade pass - then it is chucking, essentially, the fert hands into 1C and, then, 1 over transfers are sort of the logical thing to do with the remaining suits/bids.

You can alway overbid opps suit on the same level with ♠.

 

That seems advantage enough to pass with ♠, since you don't mind 1-level overcalls or even 2-level overcalls, if you are prepared to play a Moysian.

 

Since (pass, ) 1♦, 1♥ and 1♠ are transfer bids that could be weak and "force" partner to bid the suit on the 2-level (if he's weak), what do you need preempts for?

[helene_t]

I am kinda jealous with Tyssen that he can write computer code so fast, for me this project takes ages, sigh .....

 

Anyway, I have now come so far that I can cluster openings hands based on which binary splits are most helpful to partner. I.e. if you can only give him a single bit of information, the one that will let him earn the most total points on average is to tell him whether you have <10 HCP (left subtree) or >=10 HCP (right subtree). I subsequently split the tree up by repeating the procedure 5 times, leading to 32 clusters.

 

Next step would be to establish the mapping from the nodes in this tree to opening bids.

 

I don't use a training database for this purpose: rather, I compute the exact conditional probabilities that I have x HCPs given that p has y HCPs, and the exact probabilities that I have distribution x given that partner has distribution y. Obviously to make this feasible I cannot handle very complex problems. In fact, even the simultaneous probabilities for (HCP,distribution) are too complicated and I have just assumed the two to be independent. I think it would be better to adjust the simultaneous probabilities by some ad hoc formula that take into account that gulash hands have less variance on HCPs.

 

There are some anomalies in this diagram. Sometimes it will split on diamonds before splitting on the majors. And generally it puts a lot of emphasis on HCP counts. Now it is possible that there is a programming error behind this, but I have noticed two things that could lead to silly results:

- Lots of probability contingencies are too small for the computer's precision. Maybe a better compiler would help but it is also possible that some clever programming could avoid these issues. This means that the algorithm is susceptible to round off errors.

- Given just a single bit of information, it cannot make very good decisions anyway so it matters very little what the root split it. I think this is partly due to the round off errors that destroy lots of the information that could have been used to discriminate between candidate splits.

 

This tree looks like something that will lead to a 3-card hearts / 5-card spades system. However there ought to be no difference between the majors, the only thing I can think of that could course different utilities of a heart split and a spade split would be numerical artifacts related to the ordering of hands in the probability tables. Also the ordering of the suits have effect in case of ties (a club rule wins from a diamond rule and a suit rule wins from an HCP rule by default), but also opener's decision in individual cases have similar defaults so it is not obvious that rounded suits would split before pointed suits in the absence of numerical issues.

[helene_t]

Just tweaked the calculations of the probabilities a little to reduce round-of errors. It makes a little more sense now.

 

I was thinking about a different approach also.

 

Clustering opening hands on the basis of the idea that responder must place the contract after having learned which cluster the opening hand belongs to, will lead to a "convex" bidding system, i.e. openings will be defined as rectangles in (clubs,diamonds,hearts,spades,HCPs) space. This is not necessarily bad but it is very restrictive. Is there any way the computer could learn to construct openings like the multi 2♦?

 

I think the rationale behind "multi" openings can (grossly simplified) be stated this way: a 2♦ opening which can be either weak with a long major or very strong will have a high safety level opposite many hands: any hand with support for both majors. It is attractive if we can tell responder immediately what his safety level is, even if we are not giving him any clues about what the final contract is.

 

So:

 

Let the matrix S be defined such that S[i,j] is the safety level when opener has hand i and responder has hand j: 0 for pass, 1 for 1♣, 35 for 7NT. Now derive the principal components of this matrix, and somehow (I am not sure about this) decide on thresholds for each of the three first principal components P1, P2 and P3. Now define openings:

Pass: P1low, P2low, P3low

1♣: P1low, P2low, P3hi

1♦: P1low, P2hi, P3low

1♥: P1low, P2hi, P3hi

1♠: P1hi, P2low, P3low

1NT: P1hi, P2low, P3hi

2♣: P1hi, P2hi, P3low

2♦: P1hi, P2hi, P3hi

[helene_t]

 

I have now assigned opening bids to the tree. Due to stupid programming mistake I lost information about the fifth split level so opening bids can for the moment only be assigned to nodes defined by 4 splits or less.

 

I decided to constrain the assignment to the openings pass through 2♦. The optimality criterion is that responder's decision after having learned from the opening bid is constrained by the opening bid itself, so expensive opening bids will be assigned to tree nodes with a high safety level. The algorithm starts by putting all 8 opening bids at level 4 in the tree. It first assigns the 2♦ opening to the level 4 node that suffers the least loss by being constrained to 2♦ or higher. Then among the remaining level 4 nodes I assign the 2♣ opening on the same principle etc. After that initial assignment I apply a hill climbing algorithm that merges and splits to improve the overall fitness of the opening scheme, and continue until I have found a local optimum.

 

A different principle I have thought of is that tree nodes with a high loss relative to par should be assigned to lower bids (useful space principle). This is similar to Tysen's entropy principle.

 

This could now in principle be extended to responses and rebids by letting responder chose bids based on the same algorithm. One issue here to think about is when the auction is allowed to die out.

 

I am writing in C++ now.

[NickRW]

I have now assigned opening bids to the tree...

If I've understood your tree correctly, you're saying:

 

Pass = 0-9, <4 spades, <5 clubs

1♣ = 0-9, 4+ spades

1♦ = 10-13, 3+ spades, 3+ hearts

1♥ = 10-13, 3+ spades, <3 hearts

1♠ = 0-9, <4 spades, 5+ clubs

1NT = 10-13, <3 spades

2♣ = 14+, 3+ spades

2♦ = 14+, <3 spades

 

Or, to put in more plain english

Pass = largely red oriented garbage

1♣ = fertish - but we could play in spades

1♦ = constructive, can tolerate both majors

1♥ = constructive, can tolerate spades, but not hearts

1♠ = weak, club preempt

1NT = constructive, can't tolerate spades, probably happy with everything else

2♣ = strong(ish), can tolerate spades

2♦ = strong(ish), don't like spades much.

 

One question, the strongish hands are obviously the ones most likely to (need to) end up in a game contract. My gut feel is that 2m is quite a high point to start the auction when you're only guaranteeing 14 (and most of them will be in the 14-16 range) - couldn't this lead to ending in the wrong spot quite a lot? Possibly at MP this doesn't matter so much if you're gaining a lot on the other hands - but at IMPs this could be quite expensive - so - finally the question - is there any account of the size of possible loss in your model?

 

Nick

[helene_t]

Yeah, there is no "useful space" principle at play here. As long as responder's immediate shot at a final contract is 2♦ or higher it is happy to opening 2♦. The fact that responder's immediate shot is not very good and that it would need a lot of bidding space to make a more intelligent shot is not factored in.

 

The opposite extreme would be to assign pass to the cluster of hands for which responder's immediate shot is worst, i.e. where it loses the most relative to PAR. That would presumably lead to a strong pass system, since the loss from a wrong slam decision hurts more (in terms of total points) than a wrong partscore decision.

 

I think ultimatively I should assign some weight to the useful space criterion, relative to the safety level criterion. Like the information efficiency parameter in Tysen's work.

[NickRW]

The opposite extreme would be to assign pass to the cluster of hands for which responder's immediate shot is worst, i.e. where it loses the most relative to PAR. That would presumably lead to a strong pass system,...

Well, possibly. Or it could lead to, say, 1C and 1D showing all the 14+ hands - or just 1C. That wouldn't be too strange.

 

Nick

[NickRW]

Not to be outdone, I decided to look at a simpler question - which hands should you be bidding on at all - and which ones should be passing (or ferting if strong pass takes your fancy). At least some of the results look more human friendly - though not perhaps not all - unless you're a loose preempter.

 

I took a database of DD results and computed par - then marked those (pairs of) hands that should:

 

1) Be bidding a making contract or

2) Be bidding a sacrifice or

3) Would have been bidding a making contract were it not for the sacrifice (and they do need to bid or the opps won't sacrifice of course)

 

Clearly pairs of hands in any of the above categories contain at least one hand that actually should be making the first move for its side.

 

Then I put to one side, from the remaining (single) hands, those which contain a 6+ card suit or a 5/5 shape which, despite the fact they should not sacrifice, their side can make at least 7 tricks in (one of) their long suit(s). These hands, though not clearly needing to bid, are candidate hands for preempting (if possible within the constraints of what can be shown in any eventual system).

 

The remaining hands are those which have no immediate need to do anything, i.e. passers (or ferters).

 

There was very nearly a 2 to 1 ratio of hands (where either it or its partner hand) that should bid versus passers for the database as a whole.

 

I then examined all distributions and hcp counts and computed the actual ratio of bidders to passers for that specific combination and came up with a speadsheet in a similar layout to Tysen's chart. Cells in the spreadsheet where the ratio of bidders to passers is 50% better than is general for the database as a whole are considered to be hands that must bid. Cells in the spreadsheet where the ratio of bidders to passers is 50% worse than the database as a whole are definite passing (or ferting) candidates. The ones in the middle are more "Meh - bid if you want" types.

 

Specifically for the both not vul case, this is what I come up with as those hands needing to bid:

 

14hcp+

13hcp and any unbal or semi-bal

13hcp and bal with a 4 card major, except not 3=4=3=3

12hcp and 5422 so long as it has spades

12hcp and any 6 carder

12hcp and any stiff

10hcp and any void

 

Clearly my definition of needing to bid is on the Roth Stone side of things - in practice, a point or so less than the above and you're still on reasonably safe - or at least break even ground.

 

As for what to pass - hmm - there seems to be really very little you want to definitely pass if unbal. Rather than give you a summary, here are a few cells from the spreadsheet:

 

..............Pass....Bid....Less Certain

0=3=4=6 4....6....5

1=3=4=5 8....12....9-11

2=3=4=4 9....14....10-13

3=3=4=3 10....14....11-13

4=3=4=2 8....13....9-12

5=3=4=1 7....11....8-10

6=3=4=0 never....5....0- 4

 

0=2=4=7 2....3....never

1=2=4=6 3....8....4- 7

2=2=4=5 9....13....10-12

3=2=4=4 9....14....10-13

4=2=4=3 9....13....10-12

5=2=4=2 8....12....9-11

6=2=4=1 3....7....4- 6

7=2=4=0 1....2....never

 

0=1=4=8 insufficient data

1=1=4=7 insufficient data

2=1=4=6 5....9....6- 8

3=1=4=5 7....12....8-11

4=1=4=4 7....12....8-11

5=1=4=3 6....11....7-10

6=1=4=2 4....7....5- 6

7=1=4=1 1....3....2

8=1=4=0 insufficient data

 

0=1=5=7 insufficient data

1=1=5=6 insufficient data

2=1=5=5 3....8....4- 7

3=1=5=4 7....12....8-11

4=1=5=3 7....12....8-11

5=1=5=2 2....8....3- 7

6=1=5=1 insufficient data

7=1=5=0 insufficient data

 

Remember that the above is computed with some of the (better) candidate preempters removed from the calculation, so.... shape seems to be worth showing in some way with very little excuse in the way of high cards!

 

Nick

[NickRW]

P.S. Par was calculated on the more realistic (well realistic at IMPs anyway) rule that contracts 2 off are doubled, one off and the opps are letting you off the hook.

[hanp]

Helene, for constructive bidding, shouldn't lower bids contain more branches of your tree than higher bids? Or are you making this system on the assumption that responder should immediately place the contract?

[helene_t]

Helene, for constructive bidding, shouldn't lower bids contain more branches of your tree than higher bids? Or are you making this system on the assumption that responder should immediately place the contract?

yes, responder places the contract immediately.

Still, it is very crude that I use a hill-climbing algorithm with only one startguess. I am now running the program again but with 7 levels in the tree and then I will try with a few hundred startguesses for the opening bid assignment since I suspect what I presented was not a global optimum.

 

I am also running the algorithm using Tysen's reward function (i.e. anticipating on opps competing, or doubling us). I thought it would be interesting to try with the same reward function as Tysen uses to see if I get a system similar to his.

 

If my system turns out to be radically different from the "silent spade" then it would be interesting to look into which difference causes it:

- Tysen minimizes entropy of the optimal contract, I maximize immediate-shot total points.

- Tysen uses a neural network, I use rectangular/binary decision trees

- Tysen uses a genetic algorithm, I use an induction algorithm.

- Tysen uses a training database, I use "exact" (well, making some crude independence assumption) probabilities.

[NickRW]

I did a bit more work with the figures I've got... Brought the preempts into the picture and defined each hcp/distribution combo as either a passer/constructive bidder or preempter. Then for the preempter types, used a self organising map (aka a Kohonen neural net aka a feature map) to pick out what typical shapes it wants to preempt with. Still figuring out what all the numbers mean, but it appears that:

 

1) It likes to preempt with 7 clubs

2) It likes even more to preempt with 7 or 8 diamonds - particularly if one of the majors is short - and doesn't give a rats arse if there are 4 cards in the other major. It also likes 1=3=6=3.

3) It is really quite indifferent about preempting a long major - especially if the major is hearts - possibly because quite a percentage of these should end up in a game contract and are more seen as potentially constructive hands.

4) Of the 2 suiters, it likes both majors the best - and quite likes all the others - except that not one cell in the output feature map represents both minors - so 2NT both minors seems to be a waste of bidding space.

 

Nick

[NickRW]

Actually, forget the last post - too many bugs!

[helene_t]

Actually, forget the last post - too many bugs!

lol, tell me about it. There was a sign error in my reward function (basically meaning that it would think partner's length in a suit is positively correlated with your own length rather than negatively), and when using Tysen's object function the procedure will only split on HCPs, I suppose this could be right but more likely a bug.

[NickRW]

Can't damn well get the code to do what I want at the moment. If you're interested, these are the raw totals for the different shapes of hands that either needed to sacrifice or could have safely preempted despite the fact that an eventual sacrifice would have been too costly.

 

2=3=2=6 5274

2=2=3=6 5239

3=2=2=6 5085

2=2=6=3 4498

 

2=6=2=3 3941

2=6=3=2 3808

6=3=2=2 3220

2=3=6=2 3157

3=2=6=2 3134

3=6=2=2 3081

 

3=1=3=6 2699

1=3=3=6 2582

1=2=5=5 2577

1=2=6=4 2526

2=2=2=7 2493

3=1=6=3 2390

1=3=6=3 2386

 

2=1=5=5 2158

6=1=3=3 2103

3=3=1=6 2092

2=1=6=4 2092

4=2=1=6 2084

6=2=2=3 2078

2=5=1=5 2075

2=7=2=2 2065

1=5=2=5 2075

1=5=5=2 2020

2=2=7=2 2012

 

2=1=4=6 1987

1=4=6=2 1986

2=5=5=1 1973

1=2=4=6 1966

2=6=1=4 1962

6=2=3=2 1950

1=6=4=2 1930

5=1=5=2 1904

3=3=6=1 1882

 

3=6=1=3 1670

1=6=3=3 1649

7=2=2=2 1646

2=4=6=1 1616

6=3=3=1 1614

5=2=1=5 1543

1=4=2=6 1511

3=6=3=1 1594

 

5=5=1=2 1430

5=1=2=5 1388

1=2=7=3 1341

5=2=5=1 1336

2=4=1=6 1297

1=2=3=7 1293

2=1=7=3 1287

5=5=2=1 1245

1=3=2=7 1081

4=2=6=1 1076

2=7=3=1 1073

7=3=1=2 1072

2=1=3=7 1068

2=3=1=7 1064

2=7=1=3 1056

3=1=7=2 1041

1=3=7=2 1023

4=1=6=2 1022

2=3=7=1 1020

1=7=2=3 1015

1=7=3=2 1008

 

3=1=2=7 995

6=1=2=4 985

6=3=1=3 983

4=6=2=1 979

6=2=1=4 973

2=6=4=1 942

6=4=2=1 942

6=1=4=2 908

 

6=4=1=2 880

6=2=4=1 855

1=6=2=4 840

3=7=1=2 838

7=2=1=3 834

7=1=2=3 825

7=3=2=1 817

3=2=7=1 810

3=2=1=7 797

7=1=3=2 639

7=2=3=1 617

 

Huge numbers of club hands!

 

The above figures are out of just over 700K boards (Matt Ginsberg's dd database).

 

Nick

[hotShot]

@tysen2k

 

I have thought about that preempt problem.

 

Do you take opponents entropy into account?

 

While e.g. a weak 2 might increase our own entropy of perfect contract distributions,

it could explode opponents entropy.

 

Since you try to minimize our own entropy, high preempts don't look attractive unless they maximize opponents entropy at the same time.

[helene_t]

I have now made a tree based on Tysen's reward function.

 

 

It is much less HCP-oriented than with the uncontested reward function. The topmost 8 clusters are:

0-3 ♥, 0-3♠, 0-4♣

0-3 ♥, 0-3♠, 5+♣

0-3♥, 4+♠, 0-2♦

0-3♥, 4+♠, 3+♦

4+♥, 0-2♠, 0-9 HCP*

4+♥, 0-2♠, 10+ HCP

4+♥, 3+♠, 0-2♦

4+♥, 5+♠, 3+♦

 

These 8 clusters do not necessarily map to the 8 opening calls I want to define as the split/merge hillclimbing may improve on them.

 

Note that the procedure rarely splits on other HCP levels than 10. An exception is the cluster marked with * (4+ hearts, short spades, 0-9 HCP), which splits in 0-6 and 7-9 HCP.

[hrothgar]

I'd like to repeat a comment from the first page of this thread: Start by modeling auction termination before thinking about opening structures.

 

Conceptually, auction termination seems like a much easier problem. This yields two (immediate) benefits:

 

1. The output from a neural networks / decision tree can be very difficult to interpret. Combining this with an intrinsically complicated subject - the set of all possible bidding system - seems highly problematic. In contrast, auction termination is much more constrained. I feel much more confident that someone can look at the output from the NN and say

 

"Yes, this makes sense" or "Something is seriously wrong".

 

In contrast, when I'm looking at the output from the opening bidding structures my immediate reaction is: "Way too much is going on to feel confident in the results".

 

2. Coupled with this, if you make a mistake or go down the wrong path, you're probably going to be able to catch yourself relatively early.

[tysen2k]

Do you take opponents entropy into account?

 

While e.g. a weak 2 might increase our own entropy of perfect contract distributions,

it could explode opponents entropy.

Yes, that's what I'm doing now by looking at the chance we can make ours and the chance they can make theirs. I haven't had any time to work on it this weekend though.

 

Tysen

[tysen2k]

I'd like to repeat a comment from the first page of this thread: Start by modeling auction termination before thinking about opening structures.

 

Conceptually, auction termination seems like a much easier problem.

Do you propose solving auction termination in general? Only in a relay context? Are you talking about something that can handle any starting level and any known info about partner's hand?

 

Tysen

[helene_t]

I'd like to repeat a comment from the first page of this thread: Start by modeling auction termination before thinking about opening structures.

Fair point.

 

My algorithm decides on the final contract immediately after the opening bid, so rather than making it make that choice after having heard an opening bid optimized by the procedure, I could make it make the choice after having heard, say, partner opening a standard preempt. This is not interesting in itself though since this is what (for example) GIB already does all the time.

 

Then the next step is to make a strategy for responder for choosing with which hands it must place the final contract and with which hands it must make a forcing bid.

[tysen2k]

Is there any way the computer could learn to construct openings like the multi 2♦?

There are plenty of dummy variables that you can add besides raw suit lengths.

• Length of longest suit
  
• Length of longest major
  
• Length of longest red suit
  
• Length of shortest major
  
• Number of doubletons
  
• Number of singletons
  
• Number of voids
  
• etc.
  

Tysen

[hrothgar]

I'd like to repeat a comment from the first page of this thread:  Start by modeling auction termination before thinking about opening structures.

 

Conceptually, auction termination seems like a much easier problem.

Do you propose solving auction termination in general? Only in a relay context? Are you talking about something that can handle any starting level and any known info about partner's hand?

 

Tysen

My preference is (almost) always to start with the simple and build to the complex:

 

Here's what I would find especially interesting:

 

Start with the following relay example:

 

RR has just bid 3♦ showing precisely

 

3=5=1=4 shape

6+ Slam points

9 - 14 HCP

 

The relay captain has a hand that

 

1. Is going to want to play in Hearts

2. Wants to explore 6♥ as a contract

 

See what the NN comes up with in terms of methods...

 

Once the network has converged on something, the next thing that I'd look at is the sensitivity of the resulting solution by changing the relay captain's hand.

 

Make sure that Hearts are still the best trump suit.

Include the same basic choice between game and slam.

 

Compare the two solutions and see how different the methods are...

[tysen2k]

Let me just say that I'm glad we're brainstorming here and all coming up with different ways of handling the same problem. I'd like to encourage others to try their own methods too.

 

Tysen

[hrothgar]

Let me just say that I'm glad we're brainstorming here and all coming up with different ways of handling the same problem. I'd like to encourage others to try their own methods too.

 

Tysen

Regretfully, I am completely buried at work right now

(Mid Year advisory + I'm prepping a lecture at Lawrence Livermore next week which involves lots of brand new content. Should be a fun talk - certainly a fun topic - but the audience is imposing...)

 

If I ever manage to extricate myself, I might see what some of our machine learning algorithms are able to come up with...