"Double Dummy"

[aguahombre]

A few times I, and surely others, have looked at a hand record for a particular board and have become convinced that Double Dummy has made a mistake.

 

Fortunately for me, I have spotted my own error before embarrassing myself publicly. The question is, other than somehow the printed hand record and the analysis being for two different boards, is it possible for DD to ever be wrong?

[Phil]

GIB is fallible on DD analysis. I haven't seen it a lot, but I have on occasion. Stranger still, I have been on the phone with someone going over a hand record looking at GIB results, and the results differ.

 

I have never seen, nor heard of Deep Finesse making an error.

[Vampyr]

I have never seen, nor heard of Deep Finesse making an error.

 

Deep Finesse will, however, on its lower settings, occasionally miss contracts that could have made. I think that on these settings it doesn't bother to analyse contracts with very short trump fits.

[nigel_k]

I have the source code and there appear to be 'shortcuts' in there that could possibly give rise to errors. We aren't yet at the point where a normal PC can compute a double dummy solution in reasonable time using brute force with only the obvious improvements such as choices among equal cards. Maybe such a hand could even be reverse engineered from the source code if I had nothing better to do with my time.

[hotShot]

In theory the DD-Solver can not go wrong, but software is programmed by humans and humans can implement software bugs and software runs on hardware created by humans and sometimes they have engineered a bug into the hardware.

 

So if 2 GIB's produce different results, and there is no input error, than I hope one of them is the version that is corrected.

 

If you ever see such a hand again it would be great to post it.

[Hanoi5]

I read about a mistake in Deep Finesse not so long ago. In fact, it was prior to Dealmaster pro change to another DD solver.

[aguahombre]

I made a term mistake in the OP. I meant Deep Finesse, unaware that the Gib thing was called DD-Solver. Anyway, I appreciate not being taken to task for that; and people answering about both.

[barmar]

I made a term mistake in the OP. I meant Deep Finesse, unaware that the Gib thing was called DD-Solver. Anyway, I appreciate not being taken to task for that; and people answering about both.

I think people thought you were talking about double dummy solvers in general, not any particular one.

[Rossoneri]

AFAIK, GIB uses some heuristics/simulation so it is possible for the correct "solution" to be missed.

[Free]

If a DD solver is deterministic, then it shouldn't make any mistakes and it will always produce the same result. So when a program produces different results it's either because you have a different version (one of which contains an error) or because it uses heuristics. I can't imagine programs would use heuristics for something like DD solving, except to make it faster (which is quite irrelevant these days). GIB is rather old, so it may be possible it makes mistakes.

[hotShot]

AFAIK, GIB uses some heuristics/simulation so it is possible for the correct "solution" to be missed.

 

Just to get the Syntax clear:

A DD-Solver looks at all 4 hands and searches for the optimal play for each player knowing the layout of the cards.

 

I would guess that every current Bridge program also has a SD-Solver.

This Single-Dummy solver, only knows one players hand and when available dummys hand.

 

GIB's SD-Solver, guesses several deals where the holding of the 2(3 at the lead) unknown hands fit the bidding and the previous played cards.

For each of these deals GIB uses the DD-Solver to find the optimal play on that simulated deal.

You can set the time how long GIB is allowed to do this and by that determinate how many different deals GIB can analyze.

The SD-Solver then picks an action from the established set of good moves on other deals.

The fewer cards are left to play, the more information about the hands is available and the less time the DD-solver needs to analyze a deal.

During the first tricks GIB bases its decisions on a small number of simulations, near the end of a deal GIB can analyze almost all possible holdings.

 

Analyzing the same deal with the SD-Solver could get you e.g. different leads, because the decision is based on a different set of simulations.

[whereagles]

hmmm... errors in DD analyzers? I've once seen a slam that "the oracle" (as I call it lol) says it makes, but I've never found out how. That might be it. Gotta check where I got the hand.

[barmar]

A complete DD analysis of a hand is pretty complex, it has to examine every legal order of card play. If you're preparing the hand records for a full session of deals (over 30 boards), this has to be done 20 times for each hand (4 declarers X 5 denominations). If each analysis took 30 seconds, it would take 5 hours to analyze all the hands.

 

So DD solvers generally have options to simplify the analysis to speed it up. But these simplifications mean it's possible that some relevant solutions will be missed.

[Free]

A complete DD analysis of a hand is pretty complex, it has to examine every legal order of card play. If you're preparing the hand records for a full session of deals (over 30 boards), this has to be done 20 times for each hand (4 declarers X 5 denominations). If each analysis took 30 seconds, it would take 5 hours to analyze all the hands.

 

So DD solvers generally have options to simplify the analysis to speed it up. But these simplifications mean it's possible that some relevant solutions will be missed.

Sorry but I have to correct you here. There are ways to speed things up so not every possible line has to be analyzed. But please inform yourself before stating such nonsense because speeding things up doesn't necessarily mean that errors can occur.

 

I once started reading the paper about GIB (didn't finish it though) and one of the first practical things that was explained was a way to speed things up. First it analyzes how many tricks the defense can take without losing a trick because that can be calculated quite fast. This is an absolute maximum declarer can ever achieve. Every other line of play that gives declarer more tricks will be scratched immediately. Say one of the defenders has ♥AKQJT in 3NT. Every line in which the defense doesn't take their tricks immediately and declarer gets 9 tricks is stopped, because the defense could take 5 tricks from the beginning.

 

Alpha Beta pruning is another way to speed things up (look it up with google) which doesn't make any errors. It uses a min-max strategy, but I'll leave it to others to explain it. ;)

[Antrax]

Huh. Alpha Beta pruning surely can cause errors if it's to speed anything up at all. Generally speaking, "free" speedups are of the variety you mentioned + not searching symmetric situations more than once + hash tables where applicable.

[barmar]

I'm familiar with minimax and alpha-beta pruning. It requires you to have a heuristic evaluation function that calculates how "good" a position is after each play. Is there such a function for bridge? I believe these algorithms are more appropriate when planning the play in games where it's not feasible to do a full analysis, like chess (and I assume that chess programs switch from minimax to exhaustive analysis in the end game).

[phil_20686]

I'm familiar with minimax and alpha-beta pruning. It requires you to have a heuristic evaluation function that calculates how "good" a position is after each play. Is there such a function for bridge? I believe these algorithms are more appropriate when planning the play in games where it's not feasible to do a full analysis, like chess (and I assume that chess programs switch from minimax to exhaustive analysis in the end game).

 

I think in bridge its along the lines of say the defence can cash 5 tricks off the top, then any line where the declarer gets as far as 9 tricks can be discarded without competion as it obviously does not represent best play. Similarly for declarer, if declarer can win any openeing lead and cash 11 tricks, then any line where the defence ends up with 3 tricks can be immeadeatley discarded as not best play.

 

Of course you can also have heuristics which do introduce errors.i have no specific knowledge of how GIB operates.

[Free]

Huh. Alpha Beta pruning surely can cause errors if it's to speed anything up at all. Generally speaking, "free" speedups are of the variety you mentioned + not searching symmetric situations more than once + hash tables where applicable.

Really too bad we don't have downvotes anymore, because apparently you don't know how it works. If you have a full evaluation then minimax and alpha-beta-pruning won't cause any errors. It's different if you need an evaluation function for a certain position up to a certain depth, because you can't see beyond that position (which has nothing to do with the pruning btw). But in bridge you can analyze full dept and use 'tricks made by declarer' as a simple evaluation method. Pruning can't cause errors because there's nothing after the 13th trick. If you only evaluate up to 11 tricks, then you can get errors obviously. But pruning is theoritically sound.

 

Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

 

During my studies I had to program a board game with an artificial opponent. It was quite interesting because everything depended on the evaluation method. For example, once it found a winning line, there was no need to find quicker alternatives. Modifying the evaluation function made sure it would always take the quickest road to victory.

With the computers at that time, we could could keep the game playable up to a depth of 8 without pruning, with pruning it was up to 15. 8 years later I can play it at a depth of more than 20 (I don't have the game without pruning anymore). :) So there is a considerable speed advantage.

[Antrax]

Free, your further post clarifies what you meant to say in your first post. However, your first post is still incorrect. There's nothing about the alpha-beta pruning algorithm that ensures that good moves aren't pruned - as you later point out, it's a function of the maximum depth you're allowed to search, and as the Wikipedia article you cite from points out, it's also a function of "good" move ordering. Since the discussion was about speed-up, I said what I believe is true based on my own knowledge and experience, that few ways exist for a real, guaranteed speed up with no negative side effects: one of them is alpha-beta if you have some heuristics for ordering the search order such that AKQJT combinations are searched before others, and the others I've mentioned.

So, if you'd downvote me based on my correction of something you've said, maybe it's better that downvotes are gone, since clearly discussing disagreements works better (I hope).

[Free]

I highlighted the most important part of the wiki quote, because it seems you're still convinced ABP (alfa-beta pruning - getting tired of typing it completely ;) ) causes errors, which it doesn't (= reason for the downvote, you're claiming something which just isn't true).

 

Ordening the moves doesn't change the mechanism about ABP, it can only make ABP more efficient (read: analyze fewer positions). ABP works best if the first move you analyze enables you to scratch all other moves at that point. So analyzing the best move first makes it faster, analyzing the worst moves first means nothing can be scratched, so a very slow performance. Look at 4 in a row for example. A heuristic method is to order the moves from the center to the borders (because controling the center is usually the best strategy). You have 7 holes, it means you look at moves in the following order: 4, 3, 5, 2, 6, 1, 7. If move 4 is leading to a winning position, then you'll be able to scratch all other moves. However, if only move 7 is able to win, then you'll have to analyze all other moves first (or some, depending on how good the other moves are).

 

I don't know your background and how you came in touch with ABP, but it's used in many AI situations. You can't compare all games with eachother however. For example, a chess engine may scratch several moves because they seem absurd (= heuristic method to determine if a move is absurd). This is not ABP however, it's just another mechanism to speed things up, following different rules. As a result you may get an error using that heuristic method. ABP however is an algoritm, which always delivers. But getting that algoritm to work even faster, one can use a heuristic method to order the moves. As a result, the algoritm will work faster in many situations, and slower in some, but the result will be unaffected.

 

A nice applet where you can see ABP in action: http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html. From the moment the min-step gets a result that's lower than the current max for the max-step, the rest is scratched. Similar, if the max-step reaches a result that's higher than the current min for the min-step, the rest is scratched. In the original applet you have the best move first so a lot can be scratched. If you turn it all around, you won't be able to scratch anything.

[Antrax]

I never said ABP causes errors, nor have I said it doesn't. I merely said you can implement pruning in various ways, and the implementation can as a result either guarantee a perfect result or not. The ordering is relevant to the speedup, and as I said (twice now), if you want guaranteed speedup with no errors, then ABP doesn't necessarily fit the bill (since it won't necessarily speed anything up - though it couldn't slow things down, I think).

I do appreciate the lecture, though, quite honestly. Again, better than a downvote :)

[Free]

I never said ABP causes errors

I must be misreading something, maybe I need glasses. Didn't you say:

Huh. Alpha Beta pruning surely can cause errors if it's to speed anything up at all.

 

What I'm trying to tell you is that it never causes errors because it's theoretically sound (you can prove this if you want). But I must admit that in theory there's no guarantee that ABP will speed things up.

 

Basically we agree that ABP can have situations where it doesn't speed things up. While in theory there's a very tiny little chance you'll ever encounter this worst case scenario, and a rather small chance of gaining just a small amount of time, in practice you easily gain a huge amount of time when calculating to bigger depths (because that's where you lose most time, the amount of situations to analyze usually grows exponentially over depth). When going 52 moves deep (actually only 48, because the last trick is fixed) it would be very unlucky if you wouldn't get any advantage at all. It's like claiming that it's possible to have 1000 time heads when flipping a coin: it's possible, but the chance of you being able to do this are quite small.

 

There's some formula to calculate the maximum gain according to the depth, assuming a fixed number of choices, but in bridge it's too complicated. When LHO leads and dummy has a void, we already have 13 subtrees. If dummy has a doubleton on the other hand, we only have 2 subtrees. So it's very variable. The funny thing is: you gain more speed when you need it most. If everyone has only 3 cards left, the game tree is rather small, ABP won't prune much away, but we don't have much to analyze. If everyone has 13 cards, then the game tree is huge and ABP will prune away like hell in practise. :)

[Antrax]

Sorry, I'll try to phrase exactly what I was trying to say: Alpha Beta pruning is not magic. If you want good % of getting speedup, you need to rely on heuristics. Often, heuristics are not of the AKQJ variety, and thus lose some moves that are unlikely to matter. Sometimes those moves matter, and then the algorithm outputs a less than perfect result (I believe that's the common case - though you're right that I never wrote an AI for Bridge).

The less theoretical point I was trying to make is that I think it's quite probable that given the fact GIB has a limited processing time, more aggressive pruning was taken, so errors in GIB's DD solver are possible.

[barmar]

I think I get it now, but I'm not sure how much it helps with DD analysis, since we use a full traversal rather than heuristic evaluation. In most cases, this will just allow you to prune the last few levels, but those levels generally go pretty quickly because there aren't many options.

 

For example, in the case where the defense can take 5 tricks off the top, you still have to traverse the first 9 tricks before you can start pruning. And the only cases that you can prune are the ones where declarer has taken all 9 tricks; at trick 10, you can prune if declarer has only lost 1 trick; and so on.

 

I also wonder how easy it is for the analyzer to determine that one side or the other can ALWAYS take N tricks. If there's a sequence where the defense takes the first N tricks, that's obvious, but most hands aren't that simple. But I guess it generalizes somewhat: if, from any point in the tree, the side on lead can always take N tricks, then you can prune any subtrees where the other side takes more than the remaining tricks minus N.

[Free]

The less theoretical point I was trying to make is that I think it's quite probable that given the fact GIB has a limited processing time, more aggressive pruning was taken, so errors in GIB's DD solver are possible.

That's possible, knowing how long GIB has been around.