[Stephen Tu]

This is Ginsberg's last paper on GIB and Gibson:
http://www.jair.org/...0-1957-jair.pdf

I'm too dumb & lazy to understand most of it, but if someone can, maybe you are one who should join BBO team and work on improving the bots.

What I do think is that a "rules-based" "human-like thinking" approach to play is unlikely to work well (for bidding, rules necessary, this can work). Computers are good at brute force searching & computation. From what I understand what makes the chess programs good is mostly just sheer computational power; they get human GMs to tweak positional evaluation but brute force is the computer's edge, not "human-like thinking". I don't see why bridge wouldn't turn out the same. Our goal is "human expert level play", for the *output* of the program. But to me that requires more brute force simulation, and the *internal logic* of the program is thinking like computer, not human-type rules at all. The program think like computer, but the card it selects end up same as human expert, but arrived at same answer using different path, different technique.

I think GIB/Jack/Wbridge all show superior result of simulation approach vs. early version Bridge Baron etc. which use planning technique. I think if you try build new rules-based cardplay program from scratch you likely just end up spend many many years and still end up worse card player than current GIB. More likely success is some AI expert who can understand GIB code, then extend it along the lines Ginsberg was thinking of to fix current flaws and take advantage of today's computer, with more processors/cores/memory. This is just my opinion, maybe I am wrong. But I bet on simulation not rules-based cardplay given what I know.

[Antrax]

Stephen Tu, you're preaching to the choir - I've posted in this very thread that I don't believe rule-based programs have a future. But surely there's a middle path where the computer AI takes into account that the opponents have incomplete information, or at least prunes impossible hands from the double-dummy sims based on previous plays. No?

[Scarabin]

 Quantumcat, on 2012-July-26, 20:05, said:

After reading posts by people that sounds like they know what they are talking about, I would suggest you learn how GIB or Deep Finesse works first (and read their source code), figure out what their weaknesses are and find out if the programmers know of them, and have reasons for designing their algorithms the way they have (more efficient), then when you have a holistic understanding of GIB and could program it yourself from scratch with no references, THEN you can go about designing your own bridge playing software. Otherwise you'll end up making the same mistakes people did when they designed the very first bridge program, and you've got about 30 years worth of mistakes to make and fix before you get to where GIB is now.

This reads like a pretty rude and pompous post but if it is directed at me then perhaps I deserve it. I did not mean to offend you by ignoring your posts as I did not recognise any questions addressed to me but please accept my apologies. I am hardly qualified to advise you on choosing a subject for a thesis and can only say that when I attended uinversity we had a system of mentors, called tutors, and I would have discussed this with my tutor. This was a very long time ago and nowadays I suspect the normal thing would be to approach one of the professors in your discipline.

Turning to your specific points: I do not have access to GIB or Deep Finesse's source code (and as far as I know these are not available) so I cannot follow your advice.

I wrote my first bridge simulation about 30 years ago for the Commodore 64 computer. The program covered bidding and defence and coped with the AutoBridge hands compiled by Alfred Sheinwold.

I can understand that you consider a rule based play program is much more difficult than random simulation What I cannot understand is the rush to discourage anyone from even attempting to do so.

Do you consider Matthew Ginsberg presumptuous and arrogant? He cannot have been a proven author of world class programs when he started GIB, and the same goes for John Norris (Shark), Yves Costel (Wbridge5), Hans Kujf (Jack). Benito Garrozzo used to say that every great play starts with a single decision (like every journey starts with a single step). What is wrong with taking results on faith and seeing what you can do?

Again my apologies, I meant no disrespect.

[Scarabin]

 Stephen Tu, on 2012-July-26, 20:54, said:

I think GIB/Jack/Wbridge all show superior result of simulation approach vs. early version Bridge Baron etc. which use planning technique. I think if you try build new rules-based cardplay program from scratch you likely just end up spend many many years and still end up worse card player than current GIB. More likely success is some AI expert who can understand GIB code, then extend it along the lines Ginsberg was thinking of to fix current flaws and take advantage of today's computer, with more processors/cores/memory. This is just my opinion, maybe I am wrong. But I bet on simulation not rules-based cardplay given what I know.

Thanks Stephen,

Life is short and if I had access to a good random simulation play engine I would probably follow your advice. I don't have so I will continue with my attempt to perfect a rule based play engine. If I find that I cannot avoid sheer judgment plays I will probably have the program peek, at least pro.tem.. I have no desire to endure the drudgery of reproducing a random simulation.

At this stage of my development I prefer to branch out on a new path rather than follow a well worn trail.

[bluecalm]

Quote

.strong, yes, in the same way that GIB is strong now -- and its cardplay playing with itself IS very strong -- but if your goal is to avoid the plays that GIB doesn't understand, you don't get there by sticking one ply of single-dummy on top of a double-dummy analysis.

My understanding from barmar's posts is that GIB doesn't even try this one ply search (due to computational power limitations of decade old computers). It also doesn't understanding basic signalling.

My intuition is that it could be fixed in simulation based framework.

Quote

Single-dummy analysis of a random whole bridge hand is a long, long way away.

Solving it is long way away and maybe not possible ever.
Playing better than top humans is much easier though. Humans suck. Even at top level they make numerous blunders in card play which would never be made by fresh/rested/not pressured advanced player. Computer player doesn't need to be even close to solving anything to beat that imo.

Quote

I also think it is arrogant to think that a small group of you will in your spare time in a few short years do better than Ginsberg, or people like Hans Kuijf/Yves Costel and their Jack/Wbridge programs.

No idea about Jack but if Ginsberg stopped GIB development 10 years ago the chances are he missed many solutions/improvement due to his intuition of what is computationally feasible being developed at the time where hardware was 1000x slower than today.

I appreciate all the knowledgeable people posting in this thread. I accept that my intuition on this one might be completely off so I will shut up and maybe code something.

[bluecalm]

Btw, can current state of the art bridge programs solve all bm2000 problems assuming we tell them what hands are possible from the bidding ?

[Stephen Tu]

 Antrax, on 2012-July-26, 22:34, said:

But surely there's a middle path where the computer AI takes into account that the opponents have incomplete information, or at least prunes impossible hands from the double-dummy sims based on previous plays. No?

I don't see how that is a "middle path". It's just even more simulation, but opps are running single-dummy not double-dummy engines. Things that barmar described above that GIB could do, that can get super computationally intensive. I don't see how that relates to a "rule-based" approach.

 bluecalm, on 2012-July-27, 06:46, said:

Btw, can current state of the art bridge programs solve all bm2000 problems assuming we tell them what hands are possible from the bidding ?

The paper linked above claims 163/180 for 2001 GIB on BM2000, if given benefit of the doubt on a dozen or so hands out of the 180 where he felt that GIB's line wasn't clearly worse than BM's recommended line or might be better. See Gibson vs. Bridge Master posts on rec.games.bridge for discussion of the hands in question.

The initial version of GIB, without the single-dummy engine, scored 100/180.

Don't know about other programs, haven't seen people posting test results.

[P_Marlowe]

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

[antonylee]

 bluecalm, on 2012-July-24, 16:20, said:

So, for example, if there is a rule in constructive bidding: "with 12-14hcp if it goes 1D - 1S we raise to 2S with 4 spades" then it's instantly not interesting because there is nothing new we can learn from that. On the other hand if simulations or similar process shows the bid being effective then that's something - even if only confirmation in this somewhat obvious case.
I want my program to answer questions like : "is it better to bash 3NT here or to go via stayman and try to discover 4-4 major fit" or: "if I bid 3NT here, how often I will make in real play", or "what is the difference in EV between preempting to 3S and 4S here".
Once it's rule based it will just tell me what common wisdom here is which - especially that you are proposing that many people contribute to the knowledge base - about useless in my mind.

I think there are a few interesting questions here.
The first example can be seen as, given an auction that starts 1D-1S, and assuming that opener has 4 spades (let's forget about 3-crd raises :-)), with what hands should he bid 2S? 3S? 4S?
We can make this question even simpler. Assume that opener opens 1N, and that responder has a balanced hand without a 4cM (or responder has any hand, but we only allow NT play -- allowing suit play only obscures the essential point). Essentially, there are 3 calls possible: pass, 2N and 3N (let's forget about slams too). An "invite strategy" is basically a partition of all possible hands for responder into 3 subsets, RESP={pass, 2N, 3N}, and a partition of all possible hands for opener into 2 subsets, OPEN={accept invite, reject invite}.
How do we evaluate how good a strategy is? One possibility is to make the program play against itself, or against other programs. However this is not good because we would then try to exploit each program's peculiar weaknesses and bugs (say that my opponent, for some reason, misdefends whenever he doesn't have the C2; then I'll bid much more aggressively whenever I have it) -- this is pointed out, in the context of bidding, by Ginsberg in his paper linked above. An improvement would be to score the final contract against the par DD contract (again, only allowing NT contracts). An even better refinement would be to score against the par DD contract but with single dummy opening leads -- blasting to 3N compared to going through 2N is well-known to make it harder for the defense to find the right opening lead.
Anyways, even with DD scoring, is it possible for simulations to give us a better hint at what the RESP and OPEN sets look like? Most of us use a description that resembles: RESP={pass: <8HCP, 2N: =8HCP, 3N: >8HCP} and OPEN={accept: <=17HCP, reject: >=17HCP} with some judgment in between... but better descriptions should exist.

[barmar]

 Stephen Tu, on 2012-July-26, 19:46, said:

BTW GIB does do single-dummy reasoning after a few tricks as declarer only.

Note that this is one of the significant differences between the "Basic" and "Advanced" robots that you can rent from BBO. The Basic robots have GIBson disabled, so everything is done using DD simulations, and they have less thinking time than the Advanced robots.

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

 CarlRitner, on 2012-July-29, 13:01, said:

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]

 Scarabin, on 2012-July-30, 02:23, said:

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]

 Scarabin, on 2012-July-30, 02:23, said:

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.