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

 Antrax, on 2011-June-30, 03:46, said:

I never said ABP causes errors

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

 Antrax, on 2011-June-29, 00:42, said:

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]

 Antrax, on 2011-June-30, 10:57, said:

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.

[nige1]

Google found the following...

Article about Bill Bailey in the Gold Coast Congress Bulletin, 2009 said:

Deep Finesse uses a series of search technique, transposition tables, alpha-beta pruning, intelligent heuristics to determine which lines of play to explore first and if they bear fruit there is no need to do further searching from that point. If they fail then a more detailed analysis becomes necessary. In the early months Deep Finesse occasionally made mistakes. It almost always came down to being too aggressive in deciding a play line was not worth pursuing. He remembers some early errors in his "quick peek" algorithm. That's something which at each position quickly determines fast winners in each suit. If they sum to more than are sufficient for the contract, then an exhaustive analysis of the position is not necessary a certain time saver. He notes that nobody has reported an error in a Deep Finesse since those early days.

I remember reading an article about the belated discovery of a bug of the "quick-peek" type -- quickly fixed. Anyway, I believe most double-dummy solvers are now infallible.

[Free]

 barmar, on 2011-June-30, 11:01, said:

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.

That's basically a method to speed things up a little typical for this game (you can't use this method in chess or 4 in a row for example). And if you apply it after each trick, the combined gains will probably be significant, IF the overhead created by the method outweighs calculating the entire position ofcourse. That's why I don't think the exact number is always calculated. For example when not playing in NT, ruffs can make things very complicated because trick order comes into play. Or when voids are in play, again, trick order may be important. If South is declarer it's quite easy to determine the amount of top tricks in West, in East, and checking if there's a way to get the lead from West to East. It gives a certain upper/lower boundary which doesn't need to be correct anyway, but the goal is to allow some pruning. It requires a lot of analysis (or simulations if you're no mathematician) to determine the optimal balance between helpful heuristics like this and calculating the entire position.

[hotShot]

Years ago I read a little of the thesis Ginsberg wrote about developing GIB and I remember that he implemented an algorithm to determine which cards are equivalent. The easiest example is:
If you hold AKQ in a suit it is irrelevant which card you play, so instead of 3 subtrees you only have to investigate 1. Another example is that if you hold 97 and the 8 was played in an earlier trick than they are equivalent. Once you found equivalence you can use it, in all nodes to come.

[barmar]

I haven't used any DD solvers except the one you get when clicking the GIB button on BBO. But I've heard that some of them have a speed setting that the user can select. Clearly, if there are optimizations that don't degrade the accuracy of the solution, there would be no point in making it a user option. So I have to assume that this setting controls the use of heuristics that can result in solutions being missed.

[nige1]

 barmar, on 2011-June-30, 13:55, said:

I haven't used any DD solvers except the one you get when clicking the GIB button on BBO. But I've heard that some of them have a speed setting that the user can select. Clearly, if there are optimizations that don't degrade the accuracy of the solution, there would be no point in making it a user option. So I have to assume that this setting controls the use of heuristics that can result in solutions being missed.

Such speed settings probably just control the number and quality of double-dummy simulations that the program uses for single-dummy play

[barmar]

 nige1, on 2011-June-30, 16:29, said:

Such speed settings probably just control the number and quality of double-dummy simulations that the program uses for single-dummy play

No, you're talking about programs that PLAY bridge. I'm talking about DD solvers that are used when preparing hand records that show all the possible makable contracts and par results.

Maybe I'm wrong about them having options like this. I just downloaded Deep Finesse, and it doesn't have it.

[nige1]

 barmar, on 2011-June-30, 20:43, said:

No, you're talking about programs that PLAY bridge. I'm talking about DD solvers that are used when preparing hand records that show all the possible makable contracts and par results. Maybe I'm wrong about them having options like this. I just downloaded Deep Finesse, and it doesn't have it.

To save time, some double-solvers allow you to specify a contract or ignore silly contracts (e.g. contracts with a six or fewer card trump-fit).

For example, a DD analyzer may skip the 6♠ contract on this deal.

---

[barmar]

That's probably it. Sometimes I'll see on a hand record that EW can make something like 6♠, 6NT, 5♦, and 1♣ in their 5-card club fit just due to power. Obviously, no one is interested in what happens when EW are in a club contract, although this suggests what a club sacrifice might do.

[hotShot]

On my old computer, the DD-Solver of Bo Haglunds DD-Solver with a script of Deal 3.1 of Thomas Andrews could determine all 20 results (4directions*5 denominations) of about 1000 Deals in an hour. It reuses the generated tree, for different declarers playing the same denomination.
There are save ways to speed up the problem.

[hotShot]

For those with a deeper interest on how GIB works: http://www.jair.org/...0-1957-jair.pdf

[doobygilis]

I had to google this because I just had a hand where the BBO Double Dummy tool was clearly wrong.

South led the 7H, I covered 10H, North played 4H, and DD said regardless of the card played by North, the hand was good for 3NT +2.

It clearly isn't or I've lost my marbles.

If North covers the 10H with the QH, the contract goes down at least 1.

---

[mikeh]

 doobygilis, on 2023-January-16, 21:23, said:

I had to google this because I just had a hand where the BBO Double Dummy tool was clearly wrong.

South led the 7H, I covered 10H, North played 4H, and DD said regardless of the card played by North, the hand was good for 3NT +2.

It clearly isn't or I've lost my marbles.

If North covers the 10H with the QH, the contract goes down at least 1.

---

You may want to rethink your statement. I have no idea what you think the correct line of play is but you have 11 top tricks on the heart lead regardless of which heart north plays.

Win the heart King….it doesn’t matter whether he covers the 10 or not…just win the king (if the 10 holds, the result is the same)

Now double dummy you can just drop the diamond king but in real life you cross in spades and lead a diamond. Unblock the clubs at some stage before you ruin all your dummy entries and you have 5 diamonds, three clubs, two spades and a heart


Here’s a hint: if a long established piece of software says 11 tricks can be made and you think otherwise…the odds are overwhelming that you’re wrong so you should look again.

[smerriman]

I'm afraid it's a case of the marbles East wins the first trick with the king, and the king of diamonds drops singleton. So East has 2 spades, 1 heart, 5 diamonds, and 3 clubs - that's 11 tricks.