State of the Art4

[Scarabin]

:) No examples. In this post I try to set out as clearly and as succinctly as I can my view of the current state of computer programming of bridge play. I will ignore computer bidding: bidding based on random simulations is on a par with using Buller's British Bridge as your bidding system. :lol:

 

There are two main approaches to writing a computer bridge program to reproduce human card-play:

 

The first is the "monte-carlo" or random simulation approach. This is a "one size fits all" type of approach requiring only a limited number of algorithms.

 

It involves a dealer program which provides random hands for the concealed players constrained by the known cards in the open hands( the player and dummy)The number of random hands dealt is limited by the need to keep delays within acceptable limits. This is merely a quick way of approximating to the true probabilities of the distribution of the unknown cards.

 

Next everyone of these sample distributions is examined on a double-dummy basis and the acceptable card or cards recorded.Then the card which is recorded on the greatest number of samples is played. If there is more than one card the choice between them is either made at random or according to some rule set in advance. We have seen that either method can lead to seriously weird results.

 

The major advantage of the random simulation approach is that it is relatively quick to program - one estimate is 2 years to produce to develop a computer champion standard program. The great disadvantage is that it plays poorly on many types of deals and the timing of individual plays is decidedly eccentric. :(

 

The second approach may be labelled "pragmatic reasoning". This requires a much longer period of development with separate groups of algorithms for every type of play, and the computer declarer at least is also required to formulate an initial plan.

 

There are several programs on the market which could be classed as following this approach but I have not found any where programming has gone beyond a few basic plays.

 

However Fred Gitelman described such a program in 1992 and estimated developing it would take a further 5 years on top of the work he had already put into Base III. I fear his estimate may prove conservative.

 

Bridge Baron seem to have used a simpler program of this type, which they called Tignum2, when they won the championship in 1997. Unfortunately they lost to GIB in 1998 and seem to have reverted to a monte-carlo clone thereafter.

 

Various academic papers (lists available) have discussed the limitations of random simulations and have formulated approaches to reproducing declarer play but no complete system or program has emerged so far.

 

To date, the random simulation programs have the edge in competitive play; I would say largely because no one has been prepared to devote the time necessary to develop a pragmatic program capable of beating them.

 

I would dearly like to see a fully developed pragmatic program before I die because it would offer so much more than a random simulation. It would be a program worth queuing in the rain for :rolleyes:

 

I do see one slander ray of hope. Each year the programmers return from the championship and settle down to improving their programs competitiveness. Similar to Barmer and Inquiry improving GIB in response to our complaints.

 

Now random simulations can be improved by:

 

removing bugs

 

removing errors in the dealer or double-dummy programs

 

increasing the number of samples, this cannot go beyond making the probabilities more nearly accurate

 

Thus at some time they have to realize that any further improvement must come from superimposing pragmatic reasoning on the monte-carlo results. Once this is done the door is opened to a seamless transition from a very imperfect random simulation to a potentially perfect pragmatic program. The program need never be off the market and the only visible evidence of change is that more and more deals begin to be played correctly. :)

[inquiry]

Similar to Barmer and Inquiry improving GIB in response to our complaints.

 

I have absolutely nothing to do with GIB and wouldn't know how to begin to write a computer program or even some lines of code (well, ok, I did take fortran in college and have written hello world in "c"). Barmar (not barmer) does, however.

[hrothgar]

With all due respect: Do you have real significant experience with computer program in general or, better yet, in the realm of artificial intelligence?

Is there any reason that we should place any weight on your opinions?

 

To date, the random simulation programs have the edge in competitive play; I would say largely because no one has been prepared to devote the time necessary to develop a pragmatic program capable of beating them.

 

Other than the fact that this is a tautology, why should we believe that this is true?

 

Do you have any domain expertise?

Why should I care about your opinion?

[barmar]

I have absolutely nothing to do with GIB and wouldn't know how to begin to write a computer program or even some lines of code (well, ok, I did take fortran in college and have written hello world in "c"). Barmar (not barmer) does, however.

Not sure why, but he seems to be confusing you with Georgi, who does 90% of all the GIB rule improvements.

[EricK]

Warning: The below is just based on my very limited knowledge of bridge programs or of programming in general!

 

It's probably not original, but I think bridge programs need a two-step Monte Carlo approach. The problem with the double dummy methods as they stand is that they just look at the card to play from this hand, not the one that will be played by partner (or dummy). A classic example is, say, AT3 opposite KJ2. The 3 is a double dummy play for 3 tricks, but when LHO follows small, half the time you have to play the K and half the J. So the 3 will appear to be a much better play than it ought, and the computer will only find out too late, that it has a guess.

 

So what could happen is the Monte Carlo runs as normal, then the top two or three results are analysed to see if they are actually one play (eg small to the King) or two different plays (eg small to the King or Jack depending on where the Q happens to be). Maybe this could be done by seeing if after LHO plays small whether every possible card is significantly worse, double-dummy, than the original estimate the play.

[Scarabin]

I have absolutely nothing to do with GIB and wouldn't know how to begin to write a computer program or even some lines of code (well, ok, I did take fortran in college and have written hello world in "c"). Barmar (not barmer) does, however.

My apologies to Barmar and to you. My spelling has become atrocious and unfortunately BBO's spelling checker does not cover user names! :rolleyes:

[Scarabin]

With all due respect: Do you have real significant experience with computer program in general or, better yet, in the realm of artificial intelligence?

Is there any reason that we should place any weight on your opinions?

 

 

 

Other than the fact that this is a tautology, why should we believe that this is true?

 

Do you have any domain expertise?

Why should I care about your opinion?

 

You should respect anyone's opinions if they are logical and founded on truth. I think you should be able to check my statements.

 

I have re-read the sentence you quote but fail to recognize any tautology. Perhaps it is like Thurber's English teacher at high school who ruined Shakespeare for him. He used to dream of walking through the forest of Arden and having figures of speech jump out from behind every tree.

[Scarabin]

Not sure why, but he seems to be confusing you with Georgi, who does 90% of all the GIB rule improvements.

 

My apologies for misspelling your user name. My spelling and my memory are getting atrocious. Thank goodness for spelling checkers.

 

My error in respect to Inquiry is actually a compliment: He analysed one of my example deals and extended the analysis to the workings of the underlying computer program. He convinced me that he was familiar with Monte Carlo simulations.

[Scarabin]

Warning: The below is just based on my very limited knowledge of bridge programs or of programming in general!

 

It's probably not original, but I think bridge programs need a two-step Monte Carlo approach. The problem with the double dummy methods as they stand is that they just look at the card to play from this hand, not the one that will be played by partner (or dummy). A classic example is, say, AT3 opposite KJ2. The 3 is a double dummy play for 3 tricks, but when LHO follows small, half the time you have to play the K and half the J. So the 3 will appear to be a much better play than it ought, and the computer will only find out too late, that it has a guess.

 

So what could happen is the Monte Carlo runs as normal, then the top two or three results are analysed to see if they are actually one play (eg small to the King) or two different plays (eg small to the King or Jack depending on where the Q happens to be). Maybe this could be done by seeing if after LHO plays small whether every possible card is significantly worse, double-dummy, than the original estimate the play.

 

Perhaps not so limited? Remember however that a double dummy analysis knows exactly where the Q is so it sees the play as 100%. The probability is introduced by the sampling technique and this may be inaccurate.

 

I think the real trouble is that a Monte Carlo technique is unlikely to spot a throw-in making the finesse unnecessary. I am not sure why this should be so. My observations (still anecdotal rather than the result of repeated trials)seem to show this.

 

What you suggest in your last paragraph would improve these programs immensely but you would have to cover an awful lot of cases and this would take time.

[Free]

I would dearly like to see a fully developed pragmatic program before I die because it would offer so much more than a random simulation.

My suggestion: first try to prove that a pragmatic approach would provide significantly better results. If you can't, you better program it yourself, because businesses won't jump on a project which requires enormous amounts of time and effort (= money) for minimal or no gain.

 

If developers can teach their current programs the art of discovery plays, they would already improve dramatically. You could call this some sort of hybrid approach, whatever, but the DD basis is imo the way to go. Improve computing power and their results will also improve - for minimal or no costs at all!

[kgr]

I wonder if the latest versions run a DD simulation from 1 hand. It should run a DD simulation for all hands.

I mean: It does not take into account that e.g. the declarer has a guess?

[Scarabin]

My suggestion: first try to prove that a pragmatic approach would provide significantly better results. If you can't, you better program it yourself, because businesses won't jump on a project which requires enormous amounts of time and effort (= money) for minimal or no gain.

 

Good suggestion but it is difficult to prove this unless you already have a good pragmatic program. The work involved in writing a really good program would be prohibitive: first i would have to write a fast,accurate double-dummy program, second I would have use this to write a monte-carlo simulation, third I would have to write a pragmatic program incorporating a single-dummy program like suit-play and I would probably have to write all this in Prolog so that the pragmatic program could be open ended. I do not think I would ever finish and I do not think I would even start without a good team of programmers! Of course an author with an existing random simulation program can expand this with pragmatic supplements.

 

If developers can teach their current programs the art of discovery plays, they would already improve dramatically. You could call this some sort of hybrid approach, whatever, but the DD basis is imo the way to go. Improve computing power and their results will also improve - for minimal or no costs at all!

 

Agree with your first conclusion and with your second so long as the considerations are purely financial. However I like a hybrid approach and dislike a double dummy approach. Monte carlo simulations are only acceptable so long as they do not attain double dummy accuracy. If they do they become tantamount to cheating!

 

Do you agree?

[barmar]

I wonder if the latest versions run a DD simulation from 1 hand. It should run a DD simulation for all hands.

I mean: It does not take into account that e.g. the declarer has a guess?

What does this mean? DD means all players can see all 4 hands, and make the most advantageous plays.

 

When not using the GIBson algorithm, GIB deals a bunch of hands that it thinks are consistent with the bidding, then runs DD simulations of each of them.

[kgr]

What does this mean? DD means all players can see all 4 hands, and make the most advantageous plays.

 

When not using the GIBson algorithm, GIB deals a bunch of hands that it thinks are consistent with the bidding, then runs DD simulations of each of them.

Suppose that GIB is West and knows from the bidding that South has ♣Kxxx

[hv=pc=n&s=shAdcKT32&w=shdxxcQxx&n=shdAxcAJx&e=sxxhdQxxc]399|300[/hv]

South plays ♥A and GIB deals a bunch of hands that it thinks are consistent with the bidding, then runs DD simulations of each of them.

GIB sees that South will always make all tricks DD. So it can as well discard a ♣ as a ♦. Then there are only 2 ♣s out and South can play them from the top.

So when West runs the DD simulation it should run for every deal it generates for South a DD simulation from Souths viewpoint.

...I'm not sure if something like that is done.

[Free]

I've been thinking about DD solvers in the past, and I came to the conclusion that in theory, the ultimate (and still relatively easy) way to go is to let computer players make a decision based on SD results rather than DD results. This would require an enormous (exponential) amount of extra computing power (which makes it quite impossible at the moment), but it would definitely solve many issues GIB and other DD-based programs have while it keeps the good results from these programs. I think kgr is suggesting the same, but it's quite difficult to explain. ;)

 

- kgr's example would easily be solved. Since all South's cards are equally successful DD, he could play small to the Ace in lots of situations. The SD result will mean that discarding a ♦ has more chance of success than discarding a ♣ (around 50% vs 0%).

 

- When there is a 100% line, it would still find it because SD results would also calculate a certain line as 100% successful.

 

- I'm not sure what would happen with playing some random cards, blocking suits, discarding Kings,... However, when he's squeezed with ♠Kx-♥A after dummy's ♠AQ and declarer's ♠x-♥K, then he would discard a ♠ because SD he still has a chance of declarer taking the finesse (unless HCP clearly* show he's got both honors) while discarding ♠K or ♥A always leads to defeat.

(*) when there's even the slightest chance of him not having the ♠K, then it may encounter a deal where declarer should finesse the ♠ so SD keeping the ♠K and ♥A will be clear

[barmar]

GIB doesn't try to "get into the opponent's head", so it doesn't know that declarer doesn't know the location of the Q. As a result, we often see boneheaded defensive plays -- declarer leads a ♣ towards dummy and West puts in the Q, taking away the guess completely. West assumes South is playing double dummy, so will always guess right, and it's not giving up anything by playing the Q.

 

Running simulations from the other player's viewpoint results in a combinatorial explosion -- if we consider 25 hands in a simulation, this means we'd have to consider 25*25 = 625 hands to simulate our decision and declarer's decision. Or maybe even 25*25*25 = 15625 -- declarer must consider both defenders, and defenders must consider their partner's viewpoint as well. And that's just going back one trick -- it gets worse if you try to work out why they've taken the whole line they've taken.

 

Humans solve this by using planning rather than simulations. We then use our imagination to figure out from the play what the opponent's plan seems to be, and then infer the likely hands. Programming this would be hard AI.

[Cthulhu D]

Humans solve this by using planning rather than simulations. We then use our imagination to figure out from the play what the opponent's plan seems to be, and then infer the likely hands. Programming this would be hard AI.

 

Curious here: why doesn't it make sense to use pre-programmed optimal play to a suit stuff (like suit-play), if simulation doesn't generated a clear best line. So have a pre-calculated table of all suit combinations and when it's declaring it looks up the one it has and makes that play.

 

It's probably most relevant for defence when it 'knows' that all the cards are equal from a DD perspective. It would make sense to fall back on a rules engine here. So have a default rule on what to play in second seat from any given holding.

[Antrax]

I can think of two problems with this:

a) Making it too predictable. If the rule says you play a 2 and you don't play a 2, then you don't have a 2.

b) Making it dumber in some situations, where the percentage action is influenced by information it should have and suitplay won't take into account.

[Cthulhu D]

I can think of two problems with this:

a) Making it too predictable. If the rule says you play a 2 and you don't play a 2, then you don't have a 2.

b) Making it dumber in some situations, where the percentage action is influenced by information it should have and suitplay won't take into account.

 

A is easily addressed by saying 'pick either the 4 or the 2' from Q42 or 'random from Q or J' from QJ tight.

 

B Yeah, it's only relevant when it comes to the situation where all cards are double dummy equivalent - so simulations indicate that it doesn't matter what card you should play from Q42 - the root cause of the boneheaded defence plays Banmar is talking about.

 

If and only if simulations say 'nope, doesn't matter' is it worth resorting to pre-programmed rules. It should be computationally relatively cheap because you could pre-program it.

[barmar]

Whenever I think about programming in tables like this, I think back to Mike Lawrence's book on card combinations. It's organized into chapters with several hands where declarer has to figure out how to play the same card combination, but has different inferences from the way the opponents have bid and/or played, or you're in a different contract and have different constraints. Tables of card combinations usually make simplifying assumptions, like you have adequate entries to both hands, there's no danger hand, etc. When you put them into the context of an entire hand, things aren't nearly so simple.

 

So while there may be times when a table like this can be used, figuring out when you're in such a situation is difficult.

[Free]

Curious here: why doesn't it make sense to use pre-programmed optimal play to a suit stuff (like suit-play), if simulation doesn't generated a clear best line. So have a pre-calculated table of all suit combinations and when it's declaring it looks up the one it has and makes that play.

As far as I know current programs already use some form of suitplay analysis in certain situations. However, this is limited to deals where only 1 suit can be played in several ways, and entries aren't any problem.

 

Expanding this to 4 suits wouldn't work btw. It doesn't take tempo or control into account, combinations of suits need a certain amount of entries,... It's just too simplistic.

[Cthulhu D]

Not sure I get this. For starters, there is already a fall back rule. It is 'from any DD equivalent holding, play a random card.'

 

So the objections to having fall back rules at all are illogical. There is currently a fallback. It is just not very good.

 

Whenever I think about programming in tables like this, I think back to Mike Lawrence's book on card combinations. It's organized into chapters with several hands where declarer has to figure out how to play the same card combination, but has different inferences from the way the opponents have bid and/or played, or you're in a different contract and have different constraints. Tables of card combinations usually make simplifying assumptions, like you have adequate entries to both hands, there's no danger hand, etc. When you put them into the context of an entire hand, things aren't nearly so simple.

 

So while there may be times when a table like this can be used, figuring out when you're in such a situation is difficult.

 

Surely in these cases (as for Free's) though simulation is going to produce different values! If there is a danger hand, the simulation will find this! It's only when the simulations tell you there is no difference in what card you play from from your suit holding that you should resort to manual rules.

 

In that case, it doesn't even matter if your rules are very good, or very detailed.

 

It doesn't take tempo or control into account, combinations of suits need a certain amount of entries,... It's just too simplistic.

 

If the simulation isn't finding this either then you have other problems. Remember, we're only talking about situations in which DD, there is no difference what card you play. The reason is to avoid the below:

 

GIB doesn't try to "get into the opponent's head", so it doesn't know that declarer doesn't know the location of the Q. As a result, we often see boneheaded defensive plays -- declarer leads a ♣ towards dummy and West puts in the Q, taking away the guess completely. West assumes South is playing double dummy, so will always guess right, and it's not giving up anything by playing the Q.

 

I am not sure why objections like 'if there is a danger hand' hold true - surely, surely if there is a danger hand your simulations will determine that and then the cards will not be DD equivalent.

 

It's just to prevent cases like Barmar is stating above, where all the cards are DD equivalent. If you KNOW the cards are DD equivalent, there is little complexity - entry problems, danger hands etc would have been revealed in the simulation. You just need a totally generic fallback position. It is unlikely to cost if your fallback position is wrong either - remember the cards are DD equivalent...

 

Then you can play a basic rule. Note that 'second hand plays a random small card from any holding with a single H' is sufficient to solve the problem above, and handles all permutations in which the two, three, five or 12 cards are DD equivalent.

 

If I am mistaken, please tell me why, but I am not sure why a rule such as 'from any DD equivalent holding headed by 1 honor, play a random small card in second seat' is inferior to the current rule of 'play any random card.'

 

Heck, I'm 99% sure that you could just change the fallback rule from 'random card' to:

 

* From any DD equivalent holding with no honour or sequence, play a random card

* From any DD equivalent holding headed by an single honour, play a random small card

* From any DD equivalent holding headed by an honour sequence, play <random card from the sequence>

* From any DD equivalent holding headed by more than one non touching honor, do... something. Maybe cover an honour with an honour otherwise play a random small card.

 

I just pulled these out of my ass.

 

Then if you can show me any scenario in which both these are true:

 

A) Monte Carlo simulations would show that the cards are DD equivalent

B) Applying these four rules costs over simply playing a random card.

 

I will give you a gold star and commit internet seppuku. ;)

[kgr]

See http://www.bridgebase.com/forums/topic/52654-simple-6s/page__p__631300__fromsearch__1#entry631300

I think that this is another disadvantage of DD analysis. It will delay decisions (it has to take anyway) to later tricks and take extra risks of ruffs in the mean time.

If it can finesse in trumps, but will never do, and go down if trumps are 4-1 and it will delay playing trumps from the top. Because the risk of a ruff is smaller then trumps 4-1. Then it will later play the trumps from the top anyway, having risked a ruff in the mean time.

[Scarabin]

At my level of competence, it seems logical to believe:

 

most robots follow monte carlo rather than pragmatic reasoning because it's quicker to program and gives better results on average

 

monte carlo could be improved quite simply by superimposing rules on drawing trumps, playing low cards when not affecting result, and possibly on combining chances (although theoretically monte carlo should cover this?)

 

when pragmatic reasoning programming becomes sufficiently developed (probably requires someone like Fred who is expert at both bridge analysis and programming) it should out perform monte carlo (which has limited potential for improvement without changing into true double dummy analysis, which is equivalent to cheating, or into pragmatic reasoning).

 

OK, tell me I am wrong but this is where I stand.

 

Edit: Looking back I find I have restated my original thesis, so let me try to add something new:

 

Barmar has pointed out the limitations of single dummy analysis like suit play but does not a human expert plan by examining the combinations in each individual suit, taking into account any inferences as to the distribution of the missing cards and then combines individual suit plays to give the optimal result for the complete deal.

 

I do not see any insuperable barrier to reproducing this in a computer program. Whether we rewrite suitplay or use a table of probabilities is a point of detail?

[FM75]

At my level of competence, it seems logical to believe:

 

most robots follow monte carlo rather than pragmatic reasoning because it's quicker to program and gives better results on average

 

..snip..

 

I do not see any insuperable barrier to reproducing this in a computer program. Whether we rewrite suitplay or use a table of probabilities is a point of detail?

 

It seems clear that you simply do not understand the reference work that was provided in your earlier thread.

 

It is nice to know that you do not see an insuperable barrier...

 

When can we expect to see your program in competition?

 

Perhaps you should read up on some game theory. Its foundations go back to the 40's.

 

What is your human rule for this situation?

After an opening bid of 2NT, the player in the balancing seat always doubles.

How should the "declaring" pair handle this in their bidding? Will the balancing player (team) modify its behavior? How? When?

 

(I am not trying to hijack this thread. I only pose a game theoretic straw man to suggest that. in fact, games of imperfect information tend to be perforce stochastic.)