Would you join a group effort to write a new simulation?

[Scarabin]

"To dream the impossible dream....", song from Man of La Mancha.

 

Well, I think we have reached the moment of truth: the time to reflect and decide.

 

First, I would like to pay tribute to all the posters who gave of their time and knowledge to contribute to making this topic so interesting and informative. I have learned many things I did not know including access to new sources of information.

 

Second, I must thank Ahydra for his open offer of support, and Stephen Tu for his courteous and constructive response to my criticism. Stephen you have the rare gift of actually reading and understanding posts before replying to them. There may have been other offers of support and if I have erred in finding these ambiguous please forgive me and accept my gratitude.

 

Next, I have decided there is insufficient support to justify the extra work involved in coordinating a group effort. This is a personal decision and I will be very glad if anyone else decides to take over and persevere with the initiative. I will be equally glad to see this topic continue, I just won't try to answer every question or objection.

 

The only sour note is that I am saddened by the degree of animus against changes to the status quo. Real progress demands departures from current trends and threats to existing practices. May I ask you to indulge me in a small experiment: Think back to the time when you first identified the internet as the market of the future. Were you perceptive enough to foresee this before it became a general trend? And now think of the companies who have not profited from the (new) trend. My experience relates to insurance in Australia and yours may well be different, particularly if you work(ed) in IT in which case you really should have foreseen the change at an early stage.

 

I really believe there is no limit to what the human mind can accomplish, only the limits we put on ourselves. Of course I frequently fail in what I try to do but that does not keep me from being genuinely surprised by failure and examining the reasons therefor.

 

Thanks again for your company and help. Goodbye and good luck.

 

"The mind is complete and in itself, in its own place, can make a heaven of hell, or a hell of heaven" John Donne.

[Antrax]

It sounds like you have me in the naysayer pile; That wasn't my intention at all. I think a good way to start thinking about a problem is to assume others who have considered it knew what they were doing. My experience, at least, shows that I'm not that guy that can figure out stuff better than everyone else. If you ARE that guy, my apologies.

[CarlRitner]

Look for posts by Nelson Ford on rgb. He developed a bidding database that would permit people from all over the world to contribute to. While bidding can be helped by simulation, it is pretty much rule based, since every bid is supposed to be bounded, and needs to have a definition and an explanation for the opponents. Otherwise it just is not bridge.

 

I think the project fell apart when nobody could agree on one standard system to program to, like SAYC. That in itself would require manhours in the millions (my guess) but each variation you add increases the effort geometrically.

 

Programs like GIB can probably be enhanced to expert level for card play. For bidding, you need the definitions for each usable sequence, and for an expert system, there are too many (again, my guess).

[bluecalm]

So I am thinking something along the lines:

Keep all possible combinations of hands of opponents grouped by categories (say shapes). There will be like only 240 possible shapes and they will be pruned quickly as informations from bidding/play are included. Now for every possible shape there are possible combos of suits so in every shape thing you keep possible combos of spades/hearts/diamonds/clubs. It's still small so far. Now you add a number which represents number of all combos for given shape (you multiple number of combos for every suit for each shape) and sort the whole thing from the biggest amount of combos to the smallest one.

Now you add some weights. Say if opponent leads 3/5 and you see 2s you assign very small weight to every combination of spades with 2s where it's not systemic lead and keep weight unchanged for the ones where it's systemic lead. You do the same for shapes with stiffs if the stiff is not lead etc. etc. After applying those rules you sort from the most likely shape to the lest likely one and start running simuls for the most likely hands opponent might have. After every trick you repeat the process again applying the rules and again sorting to find the most likely hands to run simuls on.

 

I have no clue how gib works but my experience from writing some poker simulations and solving double dummy problems on huge databses tells me it *MIGHT* be computationally feasible to construct system like that. Also my intuition tells me it can potentially be very strong.

I am quite hyped up about it right now :)

[barmar]

One of the first things I worked on after I started working for BBO was something like what bluecalm describes, but just for bidding. I wrote a program to go through our records of saved hands (we have records going back about 7 years), categorize them using attributes like HCP, total points, and distribution, and summarize the count of each bid that was made at each step of the auction. The new database was essentially "you have hand X, the auction so far has been Y, the actions that human players have taken are 20% A, 50% B, 30% C." What we were thinking of doing was to have GIB consult this database when it's deciding on the bids to consider in simulations, and discard any bids that have low frequency, to prevent GIB from making the ridiculous bids that it occasionally makes.

 

The problem we saw was that there are just too many combinations, especially for competitive auctions that give GIB the most trouble, so once you get past the first round of bidding or so, there often aren't enough samples to get useful statistics.

[antonylee]

Bluecalm: the first part of what you describe sounds like the approach Deal and Redeal use to generate rare hand types through "smartstacking".

[Scarabin]

Look for posts by Nelson Ford on rgb. He developed a bidding database that would permit people from all over the world to contribute to. While bidding can be helped by simulation, it is pretty much rule based, since every bid is supposed to be bounded, and needs to have a definition and an explanation for the opponents. Otherwise it just is not bridge.

 

I think the project fell apart when nobody could agree on one standard system to program to, like SAYC. That in itself would require manhours in the millions (my guess) but each variation you add increases the effort geometrically.

 

Programs like GIB can probably be enhanced to expert level for card play. For bidding, you need the definitions for each usable sequence, and for an expert system, there are too many (again, my guess).

 

I am fascinated. Is there any way to access Nelson Ford's database? I see you started your own program, is it still under construction?

 

My own aim is pretty modest, all I want to do is enable a bridge player to write bridge simulations without having to undergo the drudgery of learning a programming language and operating system. (and having Microsoft make these obsolete before he has finished learning them. Oh how I yearn for the pristine simplicity of DOS!)

 

Once the shell is complete anyone can enter any bidding system he wishes and, hopefully, everyone can cooperate by writing sections of play.

[agusaris]

No reference here to a programme written in 1980 by T. Lindelof which according to the author was capable of bidding at World Championship Level. Details of his work were published in a book "Cobra" at that time.

 

If the programme is available, and works as well as the author claims, the bidding problems discussed here were resolved 32 years ago.

[antonylee]

My own aim is pretty modest, all I want to do is enable a bridge player to write bridge simulations without having to undergo the drudgery of learning a programming language and operating system. (and having Microsoft make these obsolete before he has finished learning them. Oh how I yearn for the pristine simplicity of DOS!)

<troll mode>Switch to a Unix system.</troll mode>

More seriously, I don't think "without having to undergo the drudgery of learning a programming language" is a very interesting goal -- I can write a domain-specific language for specifying a bidding system in a couple of days if you want, and others have done that too (e.g. BML). Whether you specify you system in XML or in BML or in S-expressions or in C(!) hardly matters. The hard part is writing the bidding system itself.

 

(define 1NT (and (>= hcp 15) (<= hcp 17) (balanced)))

[CarlRitner]

 

I am fascinated. Is there any way to access Nelson Ford's database? I see you started your own program, is it still under construction?

 

 

You can contact Nelson ford at nford@mail.cswnet.com if he's still around. He released the program and database to anyone willing to help.

 

When working on my own bidding program, Project 6, I set an early requirement that every bid had to have a definition or explanation that could be given to both computer and human competitors. So I set about writing a complete system description. That activity showed me the incredible expanse of usable bids. The total number of possible bids is some ridiculously large number and while I knew that 99.99999% were never needed, that left way too many for me to deal with. And that was using NO alternate conventions (no leafs). I found myself stuck in the "land of opening bids" for so long I realized the only way I could ever finish was with an incomplete (or misleading) database, and that discouraged me enough to shelve the project.

[barmar]

No reference here to a programme written in 1980 by T. Lindelof which according to the author was capable of bidding at World Championship Level.

There are some references to Lindelof in GIB's hand evaluation code. For instance, GIB's suit quality metrics (biddable, rebiddable, etc.) come from Lindelof.

[Scarabin]

Hi,

 

I have toyed with such an idea, but my energy level is usually quite low.

 

The whole thing may become a bit more interesting, if you go

 

#1 use learning methods like reinforecment learing to train the player

 

The difference between Chess and Bridge is the

 

#1 random part

#2 the amount of information that is available to all participants

 

The rule based approach works, because you have full information in

a non random enviroment.

The reinforcement approach at least worked for Backgammon, ... random

game with full information.

 

Final comment, there exist an open source double dummy solver.

http://privat.bahnhof.se/wb758135/

 

With kind regards

Marlowe

 

Thanks for help. Am familiar with Bo Haglund's double dummy solver.

 

Regards

 

Scarabin

[Scarabin]

No reference here to a programme written in 1980 by T. Lindelof which according to the author was capable of bidding at World Championship Level. Details of his work were published in a book "Cobra" at that time.

 

If the programme is available, and works as well as the author claims, the bidding problems discussed here were resolved 32 years ago.

 

My point is that as long as we work in isolation any individual's work vanishes with the individual. That is why I am pressing for a group, freeware approach that does not require end users to be proficient in specific programming languages.

[Scarabin]

<troll mode>Switch to a Unix system.</troll mode>

More seriously, I don't think "without having to undergo the drudgery of learning a programming language" is a very interesting goal -- I can write a domain-specific language for specifying a bidding system in a couple of days if you want, and others have done that too (e.g. BML). Whether you specify you system in XML or in BML or in S-expressions or in C(!) hardly matters. The hard part is writing the bidding system itself.

 

(define 1NT (and (>= hcp 15) (<= hcp 17) (balanced)))

 

 

But I see a value in:

 

- enabling every bridge player to enter his chosen bidding system (for practice) without having to learn programming,

 

- sharing our work with others so that we can build on past work and not continue to re-invent the wheel,

 

What you say is true for an experienced programmer, but let me give you my own experience. I first learned to program on a Wang computer. I realised this could be applied to bridge and completed a program on the Commodore 64. In those days you could start programming immediately in interpretative Basic (with no Windows overheads) and I graduated to Basm which comprised elements of Basic,C, and Assembler.

 

For obvious reasons, like Commodore going out of business I decided to stick with my day job and continued to dabble in C, and then VisualC++, 4,5, & 6, etc. It seems that every year you have to do more work before you can get down to actually programming bidding and play.

 

Of course, I would love having you provide me with a system that enabled me and any player to enter bidding systems, etc. My concern and reason for suggesting a group effort is the task of agreeing vocabularly ( especially for a play engine) and making entry user friendly.

 

Hope you can make sense of my turgid prose.

[Scarabin]

You can contact Nelson ford at nford@mail.cswnet.com if he's still around. He released the program and database to anyone willing to help.

 

 

Thanks Carl have emailed Nelson Ford.

 

Regards

 

Scarabin

[antonylee]

Of course, I would love having you provide me with a system that enabled me and any player to enter bidding systems, etc. My concern and reason for suggesting a group effort is the task of agreeing vocabularly ( especially for a play engine) and making entry user friendly.

 

Hope you can make sense of my turgid prose.

 

Not really... Does something such as Kungsgeten's BML (http://www.bridgebase.com/forums/topic/52574-bml-markup-language-for-full-disclosure/) suit you? (adding a specific syntax for specifying the bids)

 

1N; 15-17hcp bal
1N
 2C; 8+hcp (4H or 4S)
 2D; 5+H
 2H; 5+S

 

Say for example that the description of each bid is a list of items, which are "and"ed together, except that you can use parentheses and "or" as well. An item is either a single token ("bal", "unbal", etc.) or "quantity object" (quantity: number, number+, number-, number1-number2; object: hcp, controls, suit).

 

There is a BML -> FD converter; I don't know if FD -> BML exists but that should be not too hard to write anyways and now you get to use bidedit.exe to input your system...

 

Anyways, I'm going way too much in the details here. My whole point is that all that is only a minor step towards writing bidding sims.

[bridgeemu]

But I see a value in:

 

- enabling every bridge player to enter his chosen bidding system (for practice) without having to learn programming,

 

That is why antonylee is suggesting a DSL, if you have a DSL then you can have an intuitive syntax that any bridge player can use to enter their chosen bidding system. You can also build an editor withvalidation and code folding.

[antonylee]

Here is another challenge for computer bidding.

This is a hand I actually played in a side pairs in Philly (but let's assume we're playing imps for the sake of the question). I held AJx xx KQxx KQxx ans my partner opened 1♠. Playing "standard" 2/1, the auction continued 1♠-2♣-2♦. Now I (or a simulation) can already see that if there is a slam (is assuming partner has a heart control and enough keycards), the diamond slam will usually be better than the spade one, as I'll be able to pitch my hearts on the spades. So it seems normal to agree diamonds and enter a cuebidding/keycard auction using your favorite methods. But this is actually not optimal as I'd much rather agree spades for now in order to be able to ask for the ♠K and ♠Q, which may be critical to get to a grand, so our auction continued 1♠-2♣-2♦-2♠-2N-3♦... and now my partner will have not problem understanding that my 6♦ later in the auction, for example, is a signoff and not a grand slam try. (As it happened, partner had only two keys so I stopped in 5♠ making).

Anyways, developing more and more complete system databases is not going to help your computer get to the right sequence on hands like this one... something "more" seems to be needed.

[barmar]

I think you underestimate the difficulty of entering a bidding system. Describing all the rules, along with all the exceptions, and specifying how they relate to each other, is an extremely complicated process. Whether you use an existing programming language or something designed specifically for bridge, it has to provide ways for you to describe all these details. This is effectively programming.

 

The only attempt I've ever seen to allow ordinary players to describe bidding systems has been the Full Disclosure program. But it just allows you to describe the meaning of specific bidding sequences, there's no way to enter more general rules and exceptions.

 

The rules in the Meadowlark bidding database used by GIB each contain the following information: Bid, Priority, Auction pattern, Hand pattern, Criteria, Specification.

 

Bid: This can be a specific bid like 1♥, but most of the time it's more general like "1 of some suit other than the last bid", "2 of some suit lower than partner's bid", or "jump bid in the same suit partner bid".

 

Priority: If multiple rules match the conditions, the one with the highest priority is chosen. E.g. the rule for bidding a 5-card major has higher priority than the rule for bidding a 4-card minor, but the rule for bidding a 6-card minor is higher yet.

 

Auction pattern: Bids have different meaning depending on where they appear in the auction (opening, overcall, responding, competitive, responses to asking bids, etc.), and this allows the rule to be specific to appropriate auctions.

 

Hand pattern: Matches hand attributes like HCP, total points, distribution, suit qualities, stoppers, etc.

 

Criteria: Matches what partner, opponents, and we have already shown or denied in the auction so far. This allows bidding rules to select a trump suit when the combination of what we hold and what partner has shown is at least 8, or to make stronger bids when our strength is much more than what we'd shown in our previous bids.

 

Specification: What kind of hand is promised by the bid selected in this rule.

 

The auction pattern, hand pattern, and criteria all allow combining attributes with AND, OR, and IF/THEN/ELSE, as well as doing calculations. So you can say things like "You can make an overcall on level N if you have 6+2*N HCP."

 

The actual language used for this is really gross (it's mostly a variation on regular expressions), I certainly wouldn't recommend it. But even if we could translate it into something readable, the complexity of the information you have to describe is enormous.

[CarlRitner]

 

But even if we could translate it into something readable, the complexity of the information you have to describe is enormous.

 

 

Exactly. What we need here are two things. The first is a rigid standard for describing bids within a system, rigid enough to eliminate as much ambiguity as possible, yet something most non-programmers can use. The full disclosure program is a great start, but as you pointed out, it needs a way to add hierarchy, or rules based on generalities. Even with this added flexibility, you are going to require a very large number of rules to handle just 1NT and the next three bids. I've tried this and I keep having to go back and rework 1NT - 2C because that can include anything from a bust hand that will pass anything by opener, all the way up to a known slam.

 

The second thing you need is a program to read the above rigidly defined and formatted bidding rules into a pre-compiler or iterative compiler. You only need a small core team of people to have the knowledge to deal with this, although there will be a lot of back and forth with the rules for writing and the rules for compiling, until you work out something that covers it all. I have worked with the GIB source code and while it is nearly undecipherable by the average bridge enthusiast, it compiles iteratively into an apparently compact and fast hybrid between a database and executable script. That's likely a sloppy technical description; the bottom line is that something like this is workable IF you can develop a front end like Full Disclosure. This is what Nelson Ford was working on, although his database was more like a set of convention cards you fill out, a full data sheet for every bid. I don''t think he had any generalized rules that the specific datasheets filtered through.

 

When I was very active on my own program, I tried to incorporate a lot of flexibility into bid definitions, by greatly expanding the convention card, so that the end user could specify so many more things about each bid shown. Had I continued, I think I would have ended up with an immensely complicated front end for the end user, and a simplified rule processor for the program itself. Something tells me this is the way to go if you can assemble a large enough team of convention card / datasheet / full disclosure rule writers, all on the same page.

 

That is a totally different challenge than writing the rules processor. I think it's the bigger challenge.

[uday]

something "more" seems to be needed.

 

At various points in the auction, GIB does sims in the bidding. It generates N hands, and for each hand tries out the plausible bids and follows them thru to the end ( bidding all 4 hands using its rules )

 

In your example, after 1s p 2c p 2D, if it knew that 3D and 2S and 3S ( say ) were close enough to the official bid ( based on rules) to be candidates, it would check each bid out.

 

In principle, this is smart. In practice, what often happens is that the rules aren't capable of handling complex multi level auctions well.

 

Ginsberg talked about having these bidding simulations do more than just use the rules, having them make each call of the projected auctions using sims as well as rules, not just rules. That's probably beyond our abilities to implement, even if the speed was acceptable.

[antonylee]

In principle, this is smart. In practice, what often happens is that the rules aren't capable of handling complex multi level auctions well.

 

That is the whole point. I understand very well that simulations work better than rules in many games, including for card play in bridge, but I have doubt that simple simulations (or any "simple" set of rules, in fact) will be able to handle cases such as the one I gave (AJx xx KQxx KQxx after 1♠-2♣-2♦). Note that if I held KQx xx AJxx KQxx instead then the correct bid would probably be 3♦, not 2♠!

 

The approach I imagine would be as follows. After the auction I gave, responder sees (i.e. a rule says) that by claiming captaincy (hopefully captaincy will be easy to define :-)) he will be able to either ask for keycards and the "trump" queen either in spades or in diamonds. Now, for each value of {number of keys, presence of the TQ}, responder generates a number of hands to place the final contract (by DD or SD simulations) and computes the average score, which is then weighted by the probability of opener holding each number of keys + TQ. Now hopefully the EV of asking for keys in spades will be higher than the EV of asking for keys in diamonds (as we will have strictly more information available), so we set spades as trumps.

 

By the way a strong notion of captaincy is also required here to avoid overruling by opener for the final contract :-)

[barmar]

By the way a strong notion of captaincy is also required here to avoid overruling by opener for the final contract :-)

In fact, the Meadowlark bidding rules includes a notion of captaincy. In addition to what I said above, each bidding rule can have flags, and one of them is the "Captaincy" flag -- partner is only allowed to make the book bid in response, not override with simulations. It's a bit redundant, since there's also a "no simulate" flag that can be put on the responding bids, to prevent them from being overridden; but the captaincy flag allows you to say it in one place (the 2♣ or 4NT rules) rather than repeating it in all the followup bids. But you also have to flag the bids that relinquish captaincy. I suspect it's really more useful for relay sequences -- the relayer stays captain until he breaks the relay.

[Scarabin]

Let me try to post a combined answer to Barmar,Carl, and Antony. At the very least it may win me a commendation from Quantumcat for "listening to those who seem to know what they are talking about".

 

I cannot argue with your concensus that writing a bridge simulation is difficult and not for the faint- hearted. I agree too that Barmar's description of Meadowlark could serve as a template for a bidding system code or database.

 

However, I am 80 years old and, while there must be a significant chance I won't complete any project i start, unless I am prepared to fold my hands and await sainthood I might as well do something interesting.

 

I have already convinced myself that it is easier to write artificial bidding sequences and systems than natural ones, and also that,given enough time, I could simulate the Roman club and Super precision bidding systems.

 

Add to this the fact that Oxford bridge has marketed a bidding editor which allows the end-user to enter data bases for bidding systems. Unfortunately the base language may not be sufficiently broad to cover all hand evaluation methods.

 

So perhaps there is still hope?

[Zelandakh]

If I were doing this personally, I would make the bot play a very rules-based system which provides one hand with all of the information of the other, such as symmetric relay or the like. This allows for very efficient sampling during the later stages of the bidding to decide whether to push on for slam, and, if so, by which method. The truth is that I simply do not believe that creating a computer that can bid at a high level is as difficult as people make it out to be. You simply need the correct definition language - having no ORs in this is just a complete LOL for me - and enough expert knowledge. To get the judgement in difficult auctions really finely tuned will likely take the intimate involvement of some top players, much as the involvement of Kasparov, et al allowed chess computers to advance extremely rapidly in quieter positions which are difficult for brute-force algorithms.

 

I think the cardplay problem is much more difficult. A question I have here is whether a mixed system has been tried whereby certain patterns are stored in the database in the same way that chess computers store standard endgames. Storing these positions might allow the bot to be much more accurate in, for example, 2-way finesse positions since it could recognise it as an "elimination and endplay" hand rather than simply assuming that it can pick up the suit (double dummy). Naturally it would be extremely complex to combine this library of positions with sampling but my feeling is that the overhead from such storage would be worth the cost if done well. It would certainly be interesting to find out if this is true in practise.