[EricK]

In many books on cardplay there's a hand where you have, say, ♥AQ ♦AJ2 opposite ♥32 ♦KT3 with ♠ trumps, and the correct play is to draw trumps eliminate ♣, then play ♥A followed by ♥Q, and thus throw the opposition in and so pick up the ♦Q.

Are there any computer bridge programs which are capable of finding this sort of play? My understanding is that they approach each cardplay decision by dealing out various hands consistent with the bidding and play to date and working out what works most often double dummy. If that is so, won't they always see the ♥ finesse as a free shot at an overtrick, because they assume they will always pick up the ♦?

If there are any which get this right, how do they do it?

[Free]

It seems to me decisions should be based on scoring.

Lets consider total points first. Say going for the endplay gives us X tricks. Then there are 5 different cases:
- ♥ finesse loses, ♦ finesse loses: we get X-1 tricks
- ♥ finesse loses, ♦ finesse wins: we get X tricks
- ♥ finesse wins, ♦ finesse loses: we get X tricks
- ♥ finesse wins, ♦ finesse wins: we get X+1 tricks
- Cash ♥A and exit with ♥Q: we get X tricks
The computer will calculate not only the ♥ finesse first, but also the ♦ finesse, cashing ♦AK,...
So, when we consider the average total points, it depends on the contract. If we're playing 2♥ and X=9, then any line would be equal. However, when we're playing 3NT and X=9, then taking the risk of getting only 8 tricks will lower the average score significantly. Here, not taking any finesse should get a better average score.

MP and imp scoring are more complicated, but the principle is similar. Total points should be converted to imps or MP's somehow to calculate the average.

[BunnyGo]

Free, on 2011-December-18, 06:48, said:

It seems to me decisions should be based on scoring.

Lets consider total points first. Say going for the endplay gives us X tricks. Then there are 5 different cases:
- ♥ finesse loses, ♦ finesse loses: we get X-1 tricks
- ♥ finesse loses, ♦ finesse wins: we get X tricks
- ♥ finesse wins, ♦ finesse loses: we get X tricks
- ♥ finesse wins, ♦ finesse wins: we get X+1 tricks
- Cash ♥A and exit with ♥Q: we get X tricks
The computer will calculate not only the ♥ finesse first, but also the ♦ finesse, cashing ♦AK,...
So, when we consider the average total points, it depends on the contract. If we're playing 2♥ and X=9, then any line would be equal. However, when we're playing 3NT and X=9, then taking the risk of getting only 8 tricks will lower the average score significantly. Here, not taking any finesse should get a better average score.

MP and imp scoring are more complicated, but the principle is similar. Total points should be converted to imps or MP's somehow to calculate the average.

But the strange thing is, I think the robot will *always* assume that it picks up the diamond finesse (since it's double dummy). So it's choices are:

1) AQ of hearts, get X tricks
2) Heart finesse loses, get X tricks
3) Heart finesse wins, get X+1 tricks

[Zelandakh]

BunnyGo, on 2011-December-18, 11:34, said:

But the strange thing is, I think the robot will *always* assume that it picks up the diamond finesse (since it's double dummy).

I do not understand this. The robot deals, say, 100 hands. In 48 of them RHO has the DQ and in 52 of them LHO. So the robot treats the diamond finesse as a 52% chance. It is not double dummy for a single hand, it is double dummy for the sample hands and then averaged.

[EricK]

Zelandakh, on 2011-December-18, 11:53, said:

I do not understand this. The robot deals, say, 100 hands. In 48 of them RHO has the DQ and in 52 of them LHO. So the robot treats the diamond finesse as a 52% chance. It is not double dummy for a single hand, it is double dummy for the sample hands and then averaged.

On each hand, the double dummy play is to take the ♥ finesse, because, even if it loses, the computer sees that on every hand it can pick up the ♦ (double dummy). It is only later in the play, when it actually has to play a ♦ that it "realises" that it doesn't know where the ♦Q is

[rwbarton]

EricK, on 2011-December-17, 10:07, said:

In many books on cardplay there's a hand where you have, say, ♥AQ ♦AJ2 opposite ♥32 ♦KT3 with ♠ trumps, and the correct play is to draw trumps eliminate ♣, then play ♥A followed by ♥Q, and thus throw the opposition in and so pick up the ♦Q.

Are there any computer bridge programs which are capable of finding this sort of play? My understanding is that they approach each cardplay decision by dealing out various hands consistent with the bidding and play to date and working out what works most often double dummy. If that is so, won't they always see the ♥ finesse as a free shot at an overtrick, because they assume they will always pick up the ♦?

If there are any which get this right, how do they do it?

For simplicity, let's assume that we need to make all but one of the tricks to make our contract and that's the only goal we care about. The algorithm that you are talking about is to consider each option at the current juncture and to choose the one that has the highest probability of success assuming double-dummy play by both sides thereafter. And yes, it is true that this algorithm has no reason to prefer playing ♥A over ♥Q to this trick because it can always make 4 tricks from the red suits double-dummy later. So it may make the incorrect play of ♥Q.

Here is a sketch of an alternative algorithm that will find a single-dummy line which always achieves our goal regardless of the layout, provided that such a line exists. This is not a general solution to single-dummy play, since often we are in contracts that are not cold, but it's a step in the right direction.

Consider the following game of perfect information. Take all of the remaining East-West cards and mix them in a single pile. The game is played like bridge except that whenever it is East's or West's turn to play, they may choose any card from the pile, provided it is not inconsistent with the previous plays—for instance if East previously discarded on a club, he may not later play any clubs. In other words, the defenders must ensure at all times that their plays are legal for at least one original layout of the East-West cards. Now the claim is that the declarer can achieve his goal in this game (in our example, taking all but one of the tricks) if and only if there is a single-dummy line in the original position which achieves the goal regardless of the defenders' holdings and plays. As this new game is a game of perfect information which is not much larger (in the sense of its game tree) than a double-dummy bridge problem, it is amenable to standard game-playing algorithms like alpha-beta search.

In your example, suppose we play this modified game and declarer first plays to the ♥Q. Then East will play the ♥K and return a heart. Now however declarer plays the diamonds, the defenders can choose to win the ♦Q on whichever round declarer does not play the ♦A or ♦K. On the other hand, if declarer starts with the ♥A and ♥Q, then of course the defense will have no way to prevent declarer from taking the rest of the tricks.

Ginsberg's paper "GIB: Steps Toward an Expert-Level Bridge-Playing Program" (http://citeseer.ist....=10.1.1.52.2188) describes algorithms that extend this kind of logic to hands where the contract is not single-dummy cold. The basic idea is to select some subset of all the possible layouts, and modify the game above to require the defenders to choose their plays so that they are consistent with at least one layout in this set. That tells us whether there is a line of play which will succeed against every layout in that set. Now we want to choose such a set which covers the most hands. As there are many subsets to consider (doubly exponentially many in the number of remaining cards), we cannot afford to do this directly. I refer you to that paper for methods to deal with this.

I'm not sure which versions of GIB actually use the algorithms described in that paper. I think the online "dumb bots", at least, do not. Does anyone have more details about this?

[Free]

EricK, on 2011-December-18, 12:02, said:

On each hand, the double dummy play is to take the ♥ finesse, because, even if it loses, the computer sees that on every hand it can pick up the ♦ (double dummy). It is only later in the play, when it actually has to play a ♦ that it "realises" that it doesn't know where the ♦Q is

Idealy every choice in the game tree should be made 'single dummy'. But I'm afraid that current computers don't have the power yet to do this quickly for whole deals. In that case, you're probably right that the computer will always take the ♥ finesse based on the fact that it will get +1 trick about half the time, without realising that it can go down as well.

If every decision in the game tree can be made single dummy, then my analyse is still correct. Perhaps it's possible to do this in an endgame, but I'm not sure about this. GIB for example has some tricks to speedup his DD analysis. In an endgame, it plays really quickly, so perhaps it's possible (and still performant enough) to introduce single dummy in endgame situations up to a certain amount of tricks. This can be a great improvement imo, because you'll get more accurate probabilities.

[Zelandakh]

I remember when chess computers made plays 1-ply; then they went up to 3-ply. Now they see deeper than human opponents in tactical positions and at blitz speeds. I suspect that there are big gains to be had in computer bridge by including some pattern recognition routines, especially for declarer play. A 2-way finesse with a side loser is such a classic pattern that it should really not take very long for a computer to check this on trick 1. In fact this is so obvious I am mildly surprised noone has done this already if they currently operate at the 1-ply level suggested in this thread!

For endgames, the most common trick is to use hash tables. Modern chess computers contain hash tables for all basic endgames. I am not sure if this is really necessary for bridge although if you could extend it enough cards out it would help the situation being discussed here.

[Mbodell]

Zelandakh, on 2011-December-19, 03:58, said:

I remember when chess computers made plays 1-ply; then they went up to 3-ply. Now they see deeper than human opponents in tactical positions and at blitz speeds. I suspect that there are big gains to be had in computer bridge by including some pattern recognition routines, especially for declarer play. A 2-way finesse with a side loser is such a classic pattern that it should really not take very long for a computer to check this on trick 1. In fact this is so obvious I am mildly surprised noone has done this already if they currently operate at the 1-ply level suggested in this thread!

For endgames, the most common trick is to use hash tables. Modern chess computers contain hash tables for all basic endgames. I am not sure if this is really necessary for bridge although if you could extend it enough cards out it would help the situation being discussed here.

The other hash table like trick that makes sense in bridge is to map the cards to a smaller space (to keep the hash tables smaller) since AQ with K2 missing is the same as Q9 with T4 missing. I.e., it is the relative rank of the cards that matter, not the absolute rank.