[zenko]

hrothgar, on Jun 19 2010, 11:02 AM, said:

gnasher, on Jun 19 2010, 05:26 PM, said:

helene_t, on Jun 19 2010, 02:36 PM, said:

pass=basically 0-7 or 18+

That's also featured in human-designed systems.

Quote

1♠=8-14 points with 4-6 clubs and either 1- hearts or exactly 4 hearts.

even that is vaguely similar to the TRS major-suit openings

I would be highly amusing if the Neural Network produced something akin to the Vulcan Variable Pass

Actually I played that system, and I would again but it is illegal pretty much anywhere.

[helene_t]

This doesn't work. Lots of deals are passed out and lots end up in nonsense 5♦ contracts. There seems to be very little association between the hands and what calls they make, except that in 3rd/4th seat a pass tends to be weaker than an opening bid. Yet this is not certain. It will sometimes pass with 25 HCPs in 3rd seat.

I must be doing something wrong. Now trying with uncontested auctions only, this may be simpler. Part of the problem with contested auctions is there is a lot of noise in the scores as you get rewarded for your opponents' foolishness.

Neural network:A system is comprised of two different networks, one for 1st/2nd hand bidding and one for 3rd/4th hand bidding. The synapses that connect the hidden layer to the output layer are shared, though.
Input layer: binary indicators for whether a legal call has been made or not, for example one indicator for the event that LHO bid 1♣ at his first turn, one for the event that I bid 1NT at my second turn etc. Also 5 hcp-indicators and 4 suitlength-indicators for each suit, based on 5(rsp 4) different inver-logistic functions with a range of 0 to 100 instead of 0 to 1! This is because it was my experience that without that amplification, bidding decisions would initially (with random synapse weights) be insensitive to the hand. In the end this doesn't matter as synapse weights can adjust to achieve the needed amplification, I just made that decision to get some variance to select on in the beginning.
Also, I have amplified output neurons by a factor 1.3^k where k is the step (0 for pass, 1 for double etc). I found 1.3 to give a reasonable degree of aggressiveness of the initial networks. Without such an amplification, most auctions would end up in 5♦xx initially.
20 neurons in the hidden layer.

Evolution: Each generation is a single board round where each system delivers one EW pair and one NS pair. Results are based on a simple heuristic that predicts the number of tricks probabilistically from the number of HCPs and the number of trumps and then computes mean rewards for the reached contracts.
Matchpointed, fitness is updated is 0.1*matchpoints+0.9*previousfitness, where previousfitness is set to the mean of the field for new systems entering the population.
After each generation, the 2N (N may be 10 or 20 or so) worst systems are killed and replaced with:
- Mutant copies of the N best system, by which each synapse gets a Gaussian mutation level of 1/400 times the variance in the seeding population.
- Hybrids between the two best system and the 2nd..(N+1)th best, by which half the synapse weights are inherited from each.

[NickRW]

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

This doesn't work...

...20 neurons in the hidden layer...

20 neurons in the middle layer is miniscule.

300 generations is miniscule to evolve something as complex as a bidding system.

One of the most successful applications of neural nets to game programming is backgammon - I believe (iirc) the best open source, neural net program is gnu - I think it has 128 neurons in the middle layer - further I think it has 2 maybe 3 different neural nets (for different situations) plus bear-off database. Its training dataset is in the order of millions of positions - I think.

I don't want to put a downer on what you're doing - coz I find it extremely interesting - but you're at the stage where you're playing with the problem.

If I've understood you correctly you're presenting the bidding so far and the hand to the net and asking it what is the best call - another simpler way of doing it is presenting it with the same input plus one alternative call at a time and ask it (via one single output) how it rates each theoretically possible call. This saves the net having to work out that illegal calls should have a low score coz you never present illegal calls to the network in the first place - the business of deciding what is legal or not can stay in a procedural part of the program.

Also - do you need to tell it what the hcp is - let it learn what cards are good - ok it blows up your input layer - so what.

Also - not sure that you want to concentrate on constructive auctions only - unless you have two different nets - one for the constructive auction and one where there is interference. I am reminded of the case of the US army training a neural net to recognise friendly and soviet tanks - in testing it performed wonderfully - with live data it was awful - turned out that the pictures of US tanks in the training data had all been taken on a fine day and the soviet ones on an overcast day. In other words they had produced a neural net that was very good at recognising what the weather was like!!!

Nick

[helene_t]

Thanks, Nick. I will try with more neurons in the middle layer. I think this is more complex than backgammon so I might need several hundreds.

In the meantime I have done 100,000 generations with constructive auctions. It is not very good but at least better than random. 1000 deals, result compared to PAR:
_____Neural Network
__PO PS_ G
PO 3 71 88
PS 2 135 278
G_ 2 157 264
(This table shows that for example on 71 boards PAR was passout but it bid a partscore. On 264 PAR was game and it bid game). With respect to denomination it is only slightly better than random.

Quote

the business of deciding what is legal or not can stay in a procedural part of the program.

It is, sorry if I didn't make this clear.

Quote

Also - do you need to tell it what the hcp is - let it learn what cards are good - ok it blows up your input layer - so what.

Yeah but it appears already to be too difficult so I don't want to add to the complexity.

Maybe it would make sense fist to train one neural network to predict rewards looking at both hands, and then somehow use that network when constructing networks for bidding.

Quote

not sure that you want to concentrate on constructive auctions only

Yes, conceptually contested auctions are simpler because you don't have the issue of which hands to include. You just include all of them. Also, in terms of programming and in terms of computing time it doesn't make much of a difference. It's just that the results from the contested auctions were pretty useless so I thought maybe it would be easier if EW were made silent.

Of the final population (100 systems), here is a randomly chosen system's 3rd seat opening scheme (the initial pass could be anything):
Pass: 0-8 points, 5- spades
1♣: could be anything
1♦: 6-18 points, 4- diamonds, 5-hearts
1♥: 7-8 points, 2-4 clubs, 3- diamonds, 5-6 hearts, 3-4 spades
1♠: 5-19 points, 2+ clubs, 5- diamonds, 1-6 spades
1NT: 5+ points, 5- clubs, 2+ spades
2♣: could be anything
2♦: 5+ points
2♥: 10+ points, 3-suited short in spades

Obviously there is a lot of overlap here so apparently most openings (except for the well-defined 1♥ and 2♥ openigns) must be some kind of multi-bids. Not sure how to make sense of those, any ideas? I tried a classification tree algorithm, leading to
Pass: 0-6 HCPs, 3+clubs, 4+ hearts
1♣: 0-9 HCP, 3+ clubs, 4+ diamonds
or 10+ HCPs, 3- clubs, 2- spades
or 10+ HCPs, 4+ clubs, 1- spades
1♦: 10+ HCPs, 5+ clubs, 4+ spades.
1♥: (undefined)
1♠: 7-9 HCPs, 3+ clubs, 5+ hearts, 2 spades
or 10-12 HCPs, 4+ clubs, 5+ hearts, 2-3 spades
1NT: 10+ HCPs, 2- clubs, 3+ spades
or 12+ HCPs, 4+ clubs, 2-3 spades
2♣: 0-6 HCPs, 3+ clubs, 3- hearts
or 0-6 HCPs, 3+ clubs, 2- spades
or 0-9 points, 2- clubs, 3- diamonds
or 10-11 HCPs, 4+ clubs, 2-3 spades
2♦: 7-9 HCPs, 3+ clubs, 3+ spades
or 10 HCPs, 3 clubs, 3+ spades
or 10+ HCPs, 4+ clubs, 4+ spades

Sorry to bother you with negative findings, this obviously doesn't work.

I'll try with some more hidden neurons. Any other ideas are very welcome. Also, I am happy to share code if anyone wants to have a go.

[gwnn]

I'd like to try this system, who is in?

[NickRW]

helene_t, on Jun 21 2010, 09:55 AM, said:

...Any other ideas are very welcome. Also, I am happy to share code if anyone wants to have a go.

Did you say what you've written it in? Can do Java and C - suppose I could figure out C++ if you've done it in that - I *might* have some time. Anyway, the email is:
nickwarren at tinyworld dot co dot uk if you think some help would be useful.

Nick

[bab9]

helene_t, on Jun 21 2010, 04:55 AM, said:

Sorry to bother you with negative findings, this obviously doesn't work.

I'll try with some more hidden neurons. Any other ideas are very welcome. Also, I am happy to share code if anyone wants to have a go.

Very interesting, and worth trying. Do you have any results for the overcalls or responses to the openings?

The negative results could also give an insight on how bidding systems are developed. I would be interested in them.

I am also interested in the code.

In your notation, what is the difference between 3+ and 3- ?

[helene_t]

3+ means three or more, 3- three or less.

I write in R. Maybe should change to Java or C++.

Cascade suggested making random calls and then as the experience accumulates, choosing the calls that have lead to good results in the past with similar hands in similar situations.

I thought of something else. It will rely on a reference DB which is simply a list of some 1000 hands (single hands, not deals) which broadly covers the HCP/distribution combinations that can come up. Rather than letting the neural network use the auction so far as input, I would let it use the subset of the reference DB that partner can have, as well as the subset of a reference DB that it could have itself. This would lead to a two-stage neural network:

The secondary stage uses the HCPs and suit lengths of the hand, plus the subset of hands in the reference DB that p could have, plus the subset it could have itself, as input. And legal calls as output. This would lead to some 23 output neurons and (with a reference DB of size 1000) 2000+ input neurons. So 100,000+ synapses with a hidden layer of size 50.

The primary stage would take the same subsets of the reference DB as input, and also some essential information about the auction (what was the last bid, by which side, is it dbld/redoubled, does p get another turn if I pass). And it would take the synapse weights for the secondary stage as output. So 2000+ input and 100,000 output.

This will be very computationally expensive, not only because of the size of the primary-stage network, but also because the subsets of the reference DB have to be constructed all the time.

But the advantage would be that the secondary stage will not have to rely explicitly on the auction (which it won't know to interpret initially, and also the interpretation of a given auction changes in the course of the evolution so what was optimal in the past may not be optimal now). Rather, it relies on the information conveyed by partner, and by itself, as coded as subsets of the reference DB.

[nige1]

hanp, on May 25 2010, 04:37 AM, said:

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.

AFAIR, Mathew Ginsberg's Bridge Program was intended to use a bidding system optimised for computers.

hanp, on May 25 2010, 04:37 AM, said:

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.

Claude Shannon's Chess program and Arthur Samuel's Checkers program altered the weights of assessment criteria by playing programs against each other, using genetic algorithms. AFAIR, they discovered that, if you make only small changes, the evolution may suffer from a plateau effect: you find the summit of a local hill, while ignoring a neighboring mountain.

In theory, a computer program has access to a large database and never suffers from memory problems, so it has no need for simple or consistent treatments (ie system on). In practice, the onus of disclosure limits the amount of complexity. If it has to compete in the real world, it may also have to conform to illogical and constantly changing local system regulations.

[NickRW]

OK. Brain dump...

1. I think hrothgar's comments about termination conditions are important. A useful bot has to either have (be programmed with) or be able to evolve some criteria for when to stop at what level - and in what denomination. My experience in doing this is somewhat double dummy. Some years ago I corresponded with Zar Petkov quite a bit and was somewhat both inspired by, but suspicious of his results - so I decided to check it out in a practical way - but I also realised that doing this by real life experience would be inadequate (especially as I wasn't playing any real life bridge at the time!) So what I did was build a db of double dummy results - one bot played perfectly - it had access to the double dummy results - my only concession to real life was that it would only double you if you were two off (the other, test bot also had access to the doubling function). Naturally the double dummy bot always won - but the test bot could lose by less depending on how good it was. The test bot had access to both its side's hands and had ways of counting points (by whatever point count system I cared to use), adding extras for shape, longer fits, deducting points for 7 card fits, shortages, stiff and doubleton honours, a different point counting algorithm for assessing prospects in NT were allowed as well - it also had an array of numbers of points being equivalent to bid to a certain level. Both the algorithms and the all important arrays (there was one for NT, one for major contracts and one for minors*) were all tweaked by me - though there is no reason why you couldn't have a program do its own tweaking.

(*You might ask why different arrays were required for majors and minors - surely the trick taking power of hands are independent of some arbitrary classification of suits into categories. Well yes - but the scoring system isn't - I was scoring boards by IMPs and it turns out that the bot, just like in real life, needed to push for major games and tend to steer clear of 5M and 4m contracts - whereas some push for 5m is desirable. Anyway - turned out that 6-4-2-1 was a perfectly good way to program a bot to bid suit contracts [beat 4-3-2-1 like hands down - so Petkov was on the right track] - but it was for the birds when it came to NT.)

Naturally, the above is not much direct use to you in that you're doing this single dummy so to speak and trying to evolve a system - which I certainly wasn't doing - merely testing hand evaluation criteria. Never the less, an auction has to be able to stop - and stop at a sensible point - also - for the results to be useful to a human - or even human interpretable - one needs to have bid definitions that show something - or show a range of options. Further, I know it is getting a little a bit ahead of ourselves at this stage, but there is the matter of disclosure to the opps as well - this also needs some way of communicating what your bids show too.

2. I understand the matter of the evolving a decision tree which you and others alluded to earlier in the thread - even for uncontested auctions the tree would need to be huge. Possibly that is where things have to inevitably end up - but it is a gargantuan ask for a bot being asked to evolve a system from scratch - or so it seems to me.

3. Your (it seems to me) compromise idea above - about starting with a database of hands - seems a possible way to go - the database is of manageable size - yet its use gives partner access to a sub set of hands that would match a certain sequence of bids. 1000 hands is plenty big enough - I think - for openings and first responses - but may start to be looking very small for the 3rd round of bidding... So it possibly needs to be bigger.

4. Binary indexes - take some time to build and occupy quite a bit of memory by the time you have a lot of them - but can be enormously quick for searching - just and the indexes together to get references to which hands match - that is, of course, if you have a definition of what a bid shows!

5. A solution doesn't need to be entirely neural net based. I've followed the evolution of the bots that the University of Alberta have been producing over the last decade or so to play Holdem. One of their earlier successes (Pokibot) (iirc) had a neural net - and other algorithms - and actions being determined on a voting system between the algorithms - Poki is still one of the best bots there is years on for the multi player limit game (they've made much more sophisticated ones for the heads up game - but that is such a restricted subset of the larger problem).

.... The Mrs - ye gods - has put the footie on the goggle box ... can't concentrate anymore.... the Seth Efricans have scored against the French - Yes!!!!!! And a Froggie has been sent off!!!!

Nick

[tysen2k]

I've actually been thinking about trying to do something like this for a month or so, then I saw this thread.

In my experience, it's best to do something ultra-simple first, then increase the complexity as you prove you can do something with easier problems. Here was my idea for a starting point. No opponent bidding, but you are restricted to only 1 or 2 bidding rounds. 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 was going to score it as IMPs from par.

Tysen

[hanp]

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).

[hanp]

I have had the same thoughts as Tysen.

It seems to me that if we want to give the systems a bit of freedom in terms of what kind of messages the bids can convey, 2 rounds of bidding will much more difficult to deal with than 1 round.

A further thought: large systems should come at a "cost". If two systems compete and the first system is much larger, the second system should get some number of IMPs per hand.

[hrothgar]

hanp, on Jun 22 2010, 09:48 PM, said:

A further thought: large systems should come at a "cost". If two systems compete and the first system is much larger, the second system should get some number of IMPs per hand.

AIC, AIC, AIC

(I just spent the half the morning trying to explain Tikhonov regularization to a group who seemed shaky about regression... I'm feeling positively giddy)

[jillybean]

Hi Richard, what is AIC?

[gnasher]

hanp, on Jun 22 2010, 07:48 PM, said:

A further thought: large systems should come at a "cost". If two systems compete and the first system is much larger, the second system should get some number of IMPs per hand.

An attractive way to impose a penalty for system size would be to make the computer occasionally forget its methods, with a frequency proportional to the size of the system.

[hrothgar]

jillybean, on Jun 22 2010, 10:00 PM, said:

Hi Richard, what is AIC?

AIC stands for "An Information Criteria" (or alternatively Akaike Information Criteria) is a measurement that describes the tradeoff between the accuracy of a model and the complexity of a model.

(It's more of a snarky comment than anything else... The thought of trying to do maximum liklihood estimation on one of this models is horrific)

[hotShot]

Prior to discussing technical stuff, we should make up our minds about what a good bidding system is.
If your side can make e.g. 3♠ are you allowed to stop below that?


I see the need to reduce complexity, but you eliminate the preemptive effect when you reduce complexity by looking at uncontested auctions only.

[hanp]

hotShot, on Jun 22 2010, 03:27 PM, said:

Prior to discussing technical stuff, we should make up our minds about what a good bidding system is.
If your side can make e.g. 3♠ are you allowed to stop below that?

How about using bridge rules for a start. What kind of comment is this?

[hotShot]

hanp, on Jun 22 2010, 09:57 PM, said:

hotShot, on Jun 22 2010, 03:27 PM, said:

Prior to discussing technical stuff, we should make up our minds about what a good bidding system is.
If your side can make e.g. 3♠ are you allowed to stop below that?

How about using bridge rules for a start. What kind of comment is this?

A useful comment.

Perhaps I should have elaborated that earlier postings suggested e.g.:

-to reach the par contract
-to make the most descriptive opening bid
-to find the best opening bid opposite partners most likely hands
-to limit the number of bidding round
-to take the size of the system into account

These are all relevant points, but not necessarily achievable at the same time.

So I think there is a necessity to define what criteria to take as measure for the quality of a bidding system.