This paper describes our approach for overcoming this problem. We represent information about bridge in a task network that is extended to represent multi-agency and uncertainty. Our game-playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.

We have tested this approach on declarer play in the game of bridge, in an implementation called Tignum 2. On 5,000 randomly generated no-trump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the a = 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.

In this paper, we describe our approach for overcoming this problem. We develop a model of imperfect-information games, and describe how to represent information about the game using a modified version of a task network that is extended to represent multi-agency and uncertainty. We present a game-playing procedure that uses this approach to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.

In our tests of this approach on the game of bridge, we found that it generated trees having a much smaller branching factor than would have been generated by conventional game-tree search techniques. Thus, even in the worst case, the game tree contained only about 1300 nodes, as opposed to the approximately 6.01 44, x 10 nodes that would have been produced by a brute-force game tree search in the worst case. Furthermore, our approach successfully solved typical bridge problems that matched situations in its knowledge base. These preliminary tests suggest that our approach has the potential to yield bridge-playing programs much better than existing ones - and thus we have begun to build a full implementation.

As a step toward deeper understanding of how forward pruning affects quality of play, in this paper we set up a model of forward pruning on two abstract classes of binary game trees, and we use this model to investigate how forward pruning affects the accuracy of the minimax values returned. The primary result of our study is that forward pruning does better when there is a high correlation among the minimax values of sibling nodes in a game tree.

This result suggests that forward pruning may possibly be a useful decision-making technique in certain kinds of games. In particular, we believe that bridge may be such a game.