Sunday, October 25, 2009

What's NOT a good pruning strategy in Bridge - Part 1

In my spare time I look at academic papers for clues to optimize Gnubridge's double-dummy solver. In a frequently quoted 1996 paper, Chang proposes this pruning strategy:

Among all cards that are impossible to win the current winning card, only the one with smallest rank is selected. [1]
I have seen this strategy advocated in one other paper [2]. While it seems intuitive, it is flawed.

I implemented it in Gnubridge, and the stochastic equivalency checker quickly found counter examples. Take a look at the following position. West is to play and the trump is NT.

 If West follows the pruning strategy's advice, he'll play 4H and the pair will eventually lose the last trick when West plays 2D. If West correctly played 8H, the pair would win all tricks, by simply running the remaining hearts on East's hand.

Now the question remains - can this strategy be amended to only apply to cases when the opponent is winning the current trick and his high card cannot be beaten?