Double-dummy solving

[Everett M. Greene]

As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver. I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents. 7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.

Has there ever been anything written regarding this problem
and the approach(es) that could be used?

[ahri]

Post by Everett M. Greene
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

http://en.wikipedia.org/wiki/Game_theory

[Alex Ogan]

Post by ahri

Post by Everett M. Greene
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

http://en.wikipedia.org/wiki/Game_theory

Also, http://en.wikipedia.org/wiki/Minimax

[Nick Wedd]

Post by ahri

Post by Everett M. Greene
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

http://en.wikipedia.org/wiki/Game_theory

Game theory is applicable when the two players choose their moves at the
same time, without seeing each others' choice of move. It may be
relevant in bridge (I am doubtful), but it is certainly not relevant in
double-dummy play, which is a game of complete information.

http://en.wikipedia.org/wiki/Alpha-beta_search may be relevant. I
suspect the tree is too large to search naively even with alpha-beta
pruning, but there must be a number of heuristics which may be enough to
bring it down to something manageable.

Nick

[ahri]

In article <***@maproom.demon.co.uk>, ***@maproom.co.uk
says...

Post by Nick Wedd
Game theory is applicable when the two players choose their moves at the
same time, without seeing each others' choice of move.

Not neccessarily AFAIK, but I reserve right to be wrong here :). Anyway,
I just gave a start point :).

[v***@hotmail.com]

Post by ahri
says...

Post by Nick Wedd
Game theory is applicable when the two players choose their moves at the
same time, without seeing each others' choice of move.

Not neccessarily AFAIK, but I reserve right to be wrong here :). Anyway,
I just gave a start point :).

Only in the simplest 2X2 matrix games do both players make their
moves simultaneously.
Take a simple poker game. After all the cards are dealt the game
reduces to a 2X2 matrix game(this assumes only two players still
remain in the pot). These two players act in turn, not
simultaneously.
Still it's a valid 2X2 game theory matrix.

[Carl]

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver. I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents. 7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

Bear in mind that double dummy assumes error-free play on both sides.
Your "best" results will never happen because the opponents are not
allowed to make "idiotic" plays.

The double dummy solvers currently available do use brute force, along
with search tree trimming techniques, rather than apply heuristics.
Search for Ginsberg and "partition search" in this group.

Cheers,

Carl

www.carlritner.com <- books, bridge, cheap, lots of them

[Nick Wedd]

In message

Post by Carl

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver. I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents. 7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

Bear in mind that double dummy assumes error-free play on both sides.
Your "best" results will never happen because the opponents are not
allowed to make "idiotic" plays.
The double dummy solvers currently available do use brute force, along
with search tree trimming techniques, rather than apply heuristics.

Um, yes. By "heuristics", I meant tree-trimming heuristics, like "if
you have touching cards you might as well always play the higher first",
and "if you have found a line that guarantees ten tricks, then a line
that starts by losing four need not be pursued further". Sorry I did
not make this clear.

Nick

Post by Carl
Search for Ginsberg and "partition search" in this group.
Cheers,
Carl
www.carlritner.com <- books, bridge, cheap, lots of them

[h***@yahoo.com]

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver.  I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents.  7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

I suggest you contact either Matt Ginsberg (inventor of GIB) or the
folks who created Deep Finesse. They could probably tell you more
than you want to know.

Henrysun909

[m***@hotmail.com]

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver.  I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents.  7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

Hasn't this already been done? Can you improve upon "Deep Finesse"?

[Lorne]

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver. I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents. 7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

Hasn't this already been done? Can you improve upon "Deep Finesse"?

********************************

Deep finesse can be improved a lot if you know how it works. Right now the
guy who wrote it is no longer interested in developing it but will give you
the dll entry points if you want to write your own interface to it.

The problem however is that you can only ask one question - which cards are
good or bad plays at this point in the hand and it analyses all reminaing
cards to be played.

To get a makeable contracts grid therefore requires much redundent
processing - you guess the answer and get back 13 good/bad results then
guess 1 higher or 1 lowere and get back 13 more and have to optimise your
guesses until you get back one result where a lead beats a contract but
reducimng the trick target by 1 gets back 13 results that let it make.

What is needed is a way to ask for just 1 or 2 cards rather than all 13 and
an interal routine that will give back makeable tricks rather than forcing
recursive questions until you solve it.

[Peter Smulders]

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver. I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents. 7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

Have a look at Bo Haglunds site. He wrote a very fine double dummy
solver program. There is also a description of the algorithms used.

http://web.telia.com/~u07502278/

[Rob Morris]

As a thought problem, I've been contemplating what's involved in
developing a double-dummy solver. I was thinking that a brute-force,
try-everything approach would work but then realized that the "best"
results would be when idiotic plays are made by the opponents. 7N
would (nearly) always be the "optimum" contract by this approach so
it would solve nothing.
Has there ever been anything written regarding this problem and the
approach(es) that could be used?

A whole branch of mathematics/computer science, that I'm afraid I know
very little about. I'm sure others can give you some sensible search
terms; I'm just going to try to give my understanding of how
double-dummy solving works. Hope this helps...

There is only one double-dummy result for a contract (in one direction)
on a given hand, coming from both pairs playing to their best advantage.

The brute-force, try-everything approach works because it is applied for
both sides - you decide your best move by trying it, then putting
yourself in the opponents' place and deciding their best move. And of
course they do so by, for each of their possible moves, putting
themselves in your place and deciding what you would do in response, and
so on, until the very last trick.

So in programming terms we are calling a function recursively, a lot of
times. But the recursion eventually gets to the end, when there are no
more cards to choose from, and the function starts returning values,
bubbling up the chain. The functions figuring out the last few tricks
return, giving results to the functions about earlier tricks, all the
way back to the start.

You can visualise the result, not as a tree of every possible sequence
of cards, but as a tree of 'best moves'. Who gets to make the first
move, deciding what the actual double-dummy result is? The opening
leader, of course!

Hope that makes sense, any corrections welcome.

Now, this approach is all very well for a single bridge hand, but the
real money is in getting results without working out the whole darn
tree. (Consider a single-dummy bridge program having to
double-dummy-analyse thousands of possible layouts; or applying the same
approach to make a computer play some other game like
draughts/checkers). The higher up you can 'prune' the tree, the more
computations you save - the difficulty is figuring out how to do so.

[Lorne]

Post by Everett M. Greene
As a thought problem, I've been contemplating what's involved
in developing a double-dummy solver. I was thinking that a
brute-force, try-everything approach would work but then
realized that the "best" results would be when idiotic plays
are made by the opponents. 7N would (nearly) always be the
"optimum" contract by this approach so it would solve nothing.
Has there ever been anything written regarding this problem
and the approach(es) that could be used?

If you look up "A star iterative deepening" in google you will get an idea
of the sort of maths involved in doing an efficient structured search for
problems with big tree branch solution like bridge play. It is not trivial.

Also Ginsberg is an expert in this field and I think developed methodoly to
help solve this type of problem so it is worth searching his published
works.