A PLANNING APPROACH TO DECLARER PLAY IN CONTRACT BRIDGE

Although game-tree search works well in perfect-information games, it is less suitable for imperfect-information games such as contract brid ge. The lack of knowledge about the opponents' possible moves gives th e game tree a very large branching factor, making it impossible to sea rch a significant portion of this tree in a reasonable amount of time. This paper describes our approach for overcoming this problem. We rep resent information about bridge in a task network extended to represen t multi-agency and uncertainty. Our game-playing procedure uses this t ask network to generate game trees in which the set of alternative cho ices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes. We have tested this appro ach on declarer play in the game of bridge, in an implementation calle d Tignum 2. On 5000 randomly generated notrump deals, Tignum 2 beat th e strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the alpha = 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in a n average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.