[bab9]

Dirk Kuijt, on Jul 20 2010, 09:07 PM, said:

An update, but not a successful report.

I tried a Neural Net with these inputs:

HCP
# spades
# hearts
# diamonds
# clubs
and one input for all previous bids.

It was a failure.  I couldn't teach the program anything.

I'm going to make a next try with:
several inputs for HCP, essentially as ranges
ditto for suit lengths
one input for each possible previous sequence.

We'll see how this goes.  The number of possible sequences builds up very quickly, of course, so this may be unworkable from that respect.

Unexpected results should not be classed as a failure.

How did you determine that you could not teach the program anything?
What type neural network did you use?
How many nodes?
How big was your data set?
Were you looking at all bidding situations, or just uncontested ones?

[helene_t]

Sounds like Dirk's experiment with neural networks was similar to mine which also failed. Unlike Tysen's neural networks which, although we don't yet know if they point in the direction of effective bidding systems, at least produce something that makes sense.

My problem was, I think, that there were no neurons that represent two essential things:
- what information partner has conveyed
- what information I have already conveyed

Since the auction is part of the input, it would be possible to deduce what information partner has conveyed (and what I have conveyed) by "inverting" the neural network so to speak: but this is not what happens. What happens is that the neural network will, in the course of evolution, change the way it bids early in auction. This will then have consequences for what could, ideally, be inferred later in the auction, but this link is not assured.

So I think the way to go is to design the networks so that the information conveyed becomes represented by specific neurons.

[tysen2k]

I have not had much time to investigate this problem further, but I'm still having issues with my model in the sense that I don't get "normal" preempts. It may be a combination of two things:

• There is a severe problem with local minima. Since the entropy function is minimized when similar hands are put together, it tends to group closer to its initial configuration and not want to move in a new direction.
  
• Trying to increase the opponent's entropy might not be the best function to determine the right preempts.

The classic way to deal with the local minima is to start from several random starting points and see which leads to the best outcome. Unfortunately my current setup is way to slow for this. One solution to local minima may be to use Helene's method of decision trees. I think you'd need to divide it into at least 128 or 256 groups since preempts can be very rare/specific. The value function for the decision tree could be our entropy minus opp's entropy, although there may be problems with this (see below).

Here's how I would do the hill climbing to take into account bidding space. Once you have the leaves of your tree, randomly pick 11 leaves and assign the opening bids Pass, 1C,..., 2N (that's 11 different bids) to them. Figure out the entropy to those 11 leaves. Leave pass alone, but give an entropy penalty of 'x' to 1C, '2x' to 1D, etc. Then do hill climbing allowing other leaves to attach themselves to one of these bids. Repeat with several different initial 11 leaves. We can vary the x penalty to make sure we get a distribution that we think is normal (pass should be 40-50% of all hands, 1C should be 20-25%, etc.). Also, feel free to pick a different number of leaves than 11 if you want.

On to point #2 about my preempts. I tried several different starting points (including seeding it with "standard" preempts), but I found that it always wanted to do things like open at a high level with strong hands with long diamonds. The value function is finding hands where it can be relatively sure of its own contracts, but also eating up space when the opponents have a good contract too. And all that seems logical and the whole point of preempting. However, when we're looking at their "perfect contract" that contract is sometimes a sacrifice. Their perfect contract of 4S might be because they can make, or because they have a good sacrifice. So my model wants to open high with specific good hands like:

-
Ax
AKJxxxx
AJxx

because it has the logic of "my opponents can probably preempt against me, so I better describe my hand really well now before they get a chance." Kind of preempting a preempt, but with a strong hand. The model seems to think that using the high bids for these kinds of hands is valuable and puts the normal preempt hands into the constructive bids. Maybe it's on to something, but I'm thinking probably not.

That's it for now.

Tysen

[junyi_zhu]

tysen2k, on Jul 21 2010, 10:46 PM, said:

I have not had much time to investigate this problem further, but I'm still having issues with my model in the sense that I don't get "normal" preempts. It may be a combination of two things:

• There is a severe problem with local minima. Since the entropy function is minimized when similar hands are put together, it tends to group closer to its initial configuration and not want to move in a new direction.
  
• Trying to increase the opponent's entropy might not be the best function to determine the right preempts.

The classic way to deal with the local minima is to start from several random starting points and see which leads to the best outcome. Unfortunately my current setup is way to slow for this. One solution to local minima may be to use Helene's method of decision trees. I think you'd need to divide it into at least 128 or 256 groups since preempts can be very rare/specific. The value function for the decision tree could be our entropy minus opp's entropy, although there may be problems with this (see below).

Here's how I would do the hill climbing to take into account bidding space. Once you have the leaves of your tree, randomly pick 11 leaves and assign the opening bids Pass, 1C,..., 2N (that's 11 different bids) to them. Figure out the entropy to those 11 leaves. Leave pass alone, but give an entropy penalty of 'x' to 1C, '2x' to 1D, etc. Then do hill climbing allowing other leaves to attach themselves to one of these bids. Repeat with several different initial 11 leaves. We can vary the x penalty to make sure we get a distribution that we think is normal (pass should be 40-50% of all hands, 1C should be 20-25%, etc.). Also, feel free to pick a different number of leaves than 11 if you want.

On to point #2 about my preempts. I tried several different starting points (including seeding it with "standard" preempts), but I found that it always wanted to do things like open at a high level with strong hands with long diamonds. The value function is finding hands where it can be relatively sure of its own contracts, but also eating up space when the opponents have a good contract too. And all that seems logical and the whole point of preempting. However, when we're looking at their "perfect contract" that contract is sometimes a sacrifice. Their perfect contract of 4S might be because they can make, or because they have a good sacrifice. So my model wants to open high with specific good hands like:

-
Ax
AKJxxxx
AJxx

because it has the logic of "my opponents can probably preempt against me, so I better describe my hand really well now before they get a chance." Kind of preempting a preempt, but with a strong hand. The model seems to think that using the high bids for these kinds of hands is valuable and puts the normal preempt hands into the constructive bids. Maybe it's on to something, but I'm thinking probably not.

That's it for now.

Tysen

Interesting finding. Why diamonds are so special? Aren't clubs vulnerable as well?
As I remember, there was an old list, stating that diamonds are specially good for the preemptive opening value....

[bab9]

helene_t, on Jul 21 2010, 12:28 PM, said:

Sounds like Dirk's experiment with neural networks was similar to mine which also failed. Unlike Tysen's neural networks which, although we don't yet know if they point in the direction of effective bidding systems, at least produce something that makes sense.

My problem was, I think, that there were no neurons that represent two essential things:
- what information partner has conveyed
- what information I have already conveyed

Since the auction is part of the input, it would be possible to deduce what information partner has conveyed (and what I have conveyed) by "inverting" the neural network so to speak: but this is not what happens. What happens is that the neural network will, in the course of evolution, change the way it bids early in auction. This will then have consequences for what could, ideally, be inferred later in the auction, but this link is not assured.

So I think the way to go is to design the networks so that the information  conveyed becomes represented by specific neurons.

As an idea what if instead of using 1 neural network, a different one was used for each round of bidding? Kind of getting each neural network to specialise in a particular round of bidding. There would be a strong agruement for having information from the previous neural network feed into the current one.

[helene_t]

bab9, on Jul 22 2010, 03:42 AM, said:

what if instead of using 1 neural network, a different one was used for each round of bidding?  Kind of getting each neural network to specialize in a particular round of bidding.  There would be a strong argument for having information from the previous neural network feed into the current one.

The way I would like to think of the network is as the intermediate layer representing the information on which bidding decisions are made. So the synapses that connect the input layer to the intermediate layer condense/preprocess the information, while the synapses connecting the intermediate layer to the output make the decision. Therefore I chose a one-and-a-half network model: as for the inp-interm synapses I had one for 1st/2nd seat, and one for 3rd/4th seat, but for the interm-outp synapses I had only one set. The idea being that the decision rules should be the same but the preprocessing may be different because a pass in first seat could be informative and therefore the implication of an opening bid in 3rd/4th seat may be different from one in 1st/2nd.

But now I feel that this is inconsequent because it is no different from a 1♥ response to 1♦ having different implications than a 1♥ response to 1♣, so by the same logic I should have separate set of inp-interm synapses for each opening bid.

So I would consider going back to only one network. This would probably imply a certain symmetry in the bidding system. Although the system can still be highly asymmetric (a pass in 1st seat is a different input value than "it is not my turn yet" in 1st seat), I would expect the architecture of the network to bias the outcome of the evolution in the direction of somewhat symmetric systems. "Symmetric" here meaning that the opening scheme in 3rd/4th would be similar to 1st/2nd, but by a similar argument the responses to the different opening bids would be similar etc.*

Now if I were to include the inference from earlier calls as input, I might consider having seperate inp-interm synapses for each round. Maybe it should depend on how I would formalize the inference from the earlier calls. But even if I still had only one set of inp-interm synapses, there would still be a distinction, at the level of the new input neurons, between "the inference from previous round is blahblahblah" and "the inference from previous round is void as this is the first round".

*sidetrack: thinking of it, the fact that I have the same output neuron representing, say, the 2NT call regardless of what the previous call was, makes it difficult for the network to emulate step responses. Having one output neuron for 1st step, one for 2nd step etc. would make step responses more likely to evolve. The fixed neuron->call mapping probably favors natural bidding. Transfers would be equally easy to emulate with the fixed mapping, but the transfer accept would not. This would change by having the inference from earlier calls as input: now a transfer accept is a natural call since it is related to the suit in which partner has shown length.

Anyway, I will let the neural networks rest for now. I think Tysen is much better than I in making neural networks, and there are probably others who also know more about that issue than I do. So I will focus on my decision trees instead.

[NickRW]

junyi_zhu, on Jul 21 2010, 11:58 PM, said:

Interesting finding. Why diamonds are so special? Aren't clubs vulnerable as well?

I'm not sure that Tysen's work would suggest a different approach with the minors reversed. Part of what makes "strong preempting" with that hand good is the void in a higher ranking suit.

Nick

[NickRW]

bab9, on Jul 22 2010, 02:42 AM, said:

As an idea what if instead of using 1 neural network, a different one was used for each round of bidding?

For sure more nets for more specific situations has to be good - but personally I am uncertain as how best to make them evolve. If the first one behaves a certain way, then the 2nd can adapt to it - but if the 1st evolves, then the 2nd has to change - but equally if the 2nd makes a change to evolve to better fit with the 1st, maybe this makes the first able to tweak itself too. Kinda like you have both feedback and feedforward necessary going on between independent nets. Once you get a 3rd and a 4th net involved it looks to me like a mess.

Ultimately I suppose it is like language - computers aren't very good at it.

Take a reduced subset of this problem - the auction has gone 1♥-2♥ unopposed with relatively natural meanings for these calls. I can see a neural net representing opener's second turn quickly evolving sensible meanings for Pass and 4♥ - but what about all the calls from 2♠ up to 3NT - how should a net responding to whatever these mean evolve? And how does the first net decide it has hit a local minimum and try something completely different - short of human intervention - which is kinda not the goal of the exercise.

Nick

[helene_t]

NickRW, on Jul 22 2010, 04:00 PM, said:

If the first one behaves a certain way, then the 2nd can adapt to it - but if the 1st evolves, then the 2nd has to change - but equally if the 2nd makes a change to evolve to better fit with the 1st, maybe this makes the first able to tweak itself too.

Well it is always going to be so that as the meaning of your (say) 1♠ opening changes, your responses to it should change as well. This is true whether the opening and the responses are governed by the same NN or by two different ones.

The solution is, I think, to let the responses to 1♠ not use the information that "partner has opened 1♠", but rather use the information that "partner has shown 5+ spades and 11-20 points". Now as the system evolves so that 1♠ doesn't show 5+ spades any more, then the responses automatically adapt, it's not like they have to evolve to adapt to the new meaning.

I think this is necessary. But it does make the project a lot more complex because
- it is not clear how to code the information conveyed by partner.
- however we chose to code it, it will be more complex than just reporting the opening bid.
- we need some info about the mechanics of the auction anyway because we need to know how much bidding space we have etc.

Alternatively, one can decide not to care about responses but just optimize the opening scheme in isolation, as Tysen and I have been working on so far. Once we get that working it is a (almost) trivial extension to generalize this to the rest of the system since the same algorithms that were used to optimize the opening scheme can be used to optimize the responses to pass, the responses to 1♣ etc.

But of course it may turn out that the whole idea of optimizing the opening scheme in isolation is flawed, that in order to create an effective bidding system one would have to optimize every aspect of it as one whole, or at least a substantial part of it.

[NickRW]

helene_t, on Jul 22 2010, 03:14 PM, said:

The solution is, I think, to let the responses to 1♠ not use the information that "partner has opened 1♠", but rather use the information that "partner has shown 5+ spades and 11-20 points". Now as the system evolves so that 1♠ doesn't show 5+ spades any more, then the responses automatically adapt, it's not like they have to evolve to adapt to the new meaning.

I certainly see what you mean. However they don't automatically adapt. If the system suddenly decides that this opening will now be, say, 1NT, then that changes the meaning of pass, in response, considerably. Also, if you change to a 2 under transfer opening of 1♦, then the responding net has never had a chance to evolve a meaning for 1♥.

Also, you can't just transpose the responses to 1♠ onto 1♥ even if the 1♥ opening is largely identical - because the former has never had the option of evolving a meaning for 1♠ in response - unless you go in step responses - but that seems to me to be only really applicable for forcing auctions.

[helene_t]

Yeah if the response scheme has adapted to 1♠ showing spades and now suddenly it becomes 1NT that shows spades, then it may not function properly.

But what I envision is that the synapses governing responses evolve over a time during which they have been exposed to constantly changing opening schemes. What is sustainable in such an environment is not a response scheme compatible with a particular opening scheme, but rather a generic scheme which can handle unforeseen situations like "LHO makes a Missery 3♣ opening defined as blablabla, p makes a kgr 3♦ overcall defined as blablabla, RHO makes a KenRexford 3♠ freebid defined as blablabla, now you". What is needed to make that decision is
- the information conveyed by the other three players
- which bid is the latest, by whom, has it been doubled/redoubled
It can't afford to assume any particular relation between the last bid made and the information conveyed by the player that made it, because that relationship is subject to change from generation to generation.

I am not claiming that this is feasible. Maybe it is. Maybe one day it will be, when we get quantum computers etc. In any case I think it is a better approach than trying to establish a direct link from the auction-so-far to the meaning of calls.

[hotShot]

I think that the focus is to much on "the bid" right now.

Perhaps one should deal with abstract actions like "raise", "support", "pass",
"preemptive raise", "limit raise", "strong raise", "game forcing", "slam forcing" .....

[bab9]

hotShot, on Jul 22 2010, 12:06 PM, said:

I think that the focus is to much on "the bid" right now.

Perhaps one should deal with abstract actions like "raise", "support", "pass",
"preemptive raise", "limit raise", "strong raise", "game forcing", "slam forcing" .....

Should we be looking at "interference"?

Would we be simplifying the initial development if we looked at something like the sequence (1♥) - P - (2♥) - ? and have the computer/system determine the best bid? In which the 1♥ and 2♥ bids can be well defined, say using SAYC.

I recently read that the idea of "support" is based on the law of total tricks. It would be interesting to see if a computer would base support on a similar method, or have another determinant to indicate support.

With the work done on the neural networks so far, are you in a position to indicate if a response to an opening bid can should support? Either in a natural or artifical sense.

[Dirk Kuijt]

It was pointed out that, when I said my experiment was a failure, that really wasn’t true. We learn from failures. Indeed, true, which is actually why I posted it.

I rated the results as a failure in the sense that, as far as I could tell, it was bidding at random. Final contracts didn’t bear any relation that I could see to what I was trying to teach, nor to the way it bid similar hands. This was still true even after trials with as many as 1,000,000 hands.

My previous approach suffered (I realized in retrospect) from too much linearity, while bridge bidding systems are not linear. As such, even if I set the weights on input, I could not define standard bids. Specifically, five key inputs were HCP, number of spades, hearts, diamonds, and clubs. Consider a standard 1NT (let’s say 15-17, balanced). As the number of HCP goes up, the weight for the 1NT opener line should increase, but, when you get to 18 HCP, the value has to drop to zero. This is pretty much inexpressible in my previous approach.

New approach: I now have 9 inputs for ranges of HCP, and 7 ranges for the length of each suit. That makes 37 inputs, which are essentially binary. This at least allows me to express a Standard American 1NT opener.

I have also bitten the bullet and now have a set of weights for each possible bidding sequence. Gulp! Yes, that does take a lot of memory. At the moment I’m only dealing with 2 rounds of bidding (4 bids). I limit the opener to calls up to 2NT, the first response to 3NT, and the next two bids to 5D but it is still a lot of memory. At least I can now express a standard Stayman sequence or Jacoby Transfer.

Results are still random, much the same as the previous approach. Why, I don’t know.

[Dirk Kuijt]

Next approach (yes, I'm still at it):

First, I'm going to just try to get a system that gets to the right suit, rather than penalizing both for the wrong suit and the wrong level.

Second, I'm going to try having the program bid a hand until it gets it right, then modifying the hand *slightly* (at most one card in each hand, perhaps just one card in the 26), and having the program bid again. The idea is to make the program discover that similar hands should be bid in similar ways.

We'll see how this turns out. More to come.

[Ant590]

helene_t, on Jul 22 2010, 05:36 PM, said:

I am not claiming that this is feasible. Maybe it is. Maybe one day it will be, when we get quantum computers etc.

Blimey, just realised that GiB on a quantum computer will be able to simulate every possible hand in a fraction of a second.

[Dirk Kuijt]

I decided on tackling an easier problem. Rather than trying to get to the right contract, I would try to have the program just get to the right strain (suit or NT). The weights for HCP were all set to zero, and the weight changes were all based on whether the program got to the right suit (or at least an acceptable suit) or not. Specifically:
1. If the contract is in a suit, the suit must be 7 cards combined or more, with penalty weight changes increasing linearly the shorter the suit, and reward weight changes increasing with the length of the suit.
2. If the hands have 9 or more spades, don’t play in hearts unless there at least 8, don’t play in a minor unless there are at least 9, and don’t play NT.
3. If the hands have 9 or more hearts, don’t play in spades unless there at least 8, don’t play in a minor unless there are at least 9, and don’t play NT.
4. If the contract is NT, the shortest suit in the combined hands must have at least 4 cards.
The program was permitted to make 3 calls at most, with dealer’s initial pass allowed, but counting as one of the three calls. That is, opening bid, response, opener’s rebid is the longest possible sequence.
The initial weights were random, as were the hands, so the results listed below might well not be repeated if the program were rerun (as I plan to do). During the training phase, each hand was bid until the program got it right or it tried 100 times. Also, during the training phase, successive hands differed only by the exchange of one card with one other in the deck. Often, such a change will make no difference in the hands, and it will never make a large difference. During the examination phase, however, hands were (pseudo) randomly dealt fresh for each pair of hands, and the weights were not changed. The opening call may be Pass, or up to 2NT. The response may be up to 3NT, and the rebid may be up to 5D. There were 900,000 hands in the training phase.
The results are obviously not optimal in any sense; for one thing the program never opens 2S, or, at least, never did in the 50,000 deals of the examination phase. I have tried to eyeball the results, and can summarize the opening bids of the ‘system’ as follows:
Pass: long diamonds, may also have long clubs
1♣: 5 diamonds, 6 or more clubs
1♦: usually 4 spades and 6 clubs, sometimes 4 diamonds and 7 clubs
1♥: exactly 2-1-5-5
1♠: a catchall for normally balanced hands, may be 4-4-4-1
1NT: long hearts
2♣: long spades
2♦: long clubs, may have 4 diamonds
2♥: exactly 4-2-0-7
2♠: unused, as far as I can tell
2NT: 5 hearts and a 5 card minor
I recall an earlier poster had noticed a tendency to bid over the promised suit, rather than bidding the promised suit (as natural systems do, by definition) or bid under the promised suit, as in transfer situations. That happens in this set of results as well, with the 1♦, 1♥, 1NT, 2♣, and 2♦ bids, and arguably other cases as well. Why, I have no idea.
More to come.

[NickRW]

Dirk Kuijt, on Aug 1 2010, 08:17 PM, said:

Pass: long diamonds, may also have long clubs
1♣: 5 diamonds, 6 or more clubs
1♦: usually 4 spades and 6 clubs, sometimes 4 diamonds and 7 clubs
1♥: exactly 2-1-5-5
1♠: a catchall for normally balanced hands, may be 4-4-4-1
1NT: long hearts
2♣: long spades
2♦: long clubs, may have 4 diamonds
2♥: exactly 4-2-0-7
2♠: unused, as far as I can tell
2NT: 5 hearts and a 5 card minor
I recall an earlier poster had noticed a tendency to bid over the promised suit, rather than bidding the promised suit (as natural systems do, by definition) or bid under the promised suit, as in transfer situations.  That happens in this set of results as well, with the 1♦, 1♥, 1NT, 2♣, and 2♦ bids, and arguably other cases as well.  Why, I have no idea.
More to come.

As I understand it there is no penalty in your training methods for getting too high - consequently it is going to tend to assign some random opening to show some useful shape. I don't think it is particularly selecting any sort of transfer.

Emphasising this is that your opening pass and 1♣ - which should be fairly frequent in any system are not particularly frequent at all.

Nick

Later P.S. You might try adding a very limited hcp input - say the ranges that Helene's work highlighted: 0-6, 7-9, 10-12 and 13+ - which might allow some meaningful way of training it to not get too high - without a big increase in the complexity of your input layer (or indeed the middle layer).

[Dirk Kuijt]

Nick

Yes, my current training takes no notice of level or HCP at all. Obviously unrealistic, but my previous attempts to include them didn't lead to any convergence. I don't mean convergence on anything useful; I simply didn't get convergence at all. So, I decided to try a simpler problem that perhaps I could get some answer.

I would definitely like to bias the bidding to lower calls; I've pondered this in the past, but have been unable to find a way to do that. That investigation will also continue.

Incidentally, the problem that I set for the computer is not all that easy, given that you are restricted to three bids.

[bab9]

Dirk,

Interesting results. Are you able to determine how the responding sequence might proceed after the opening bid?