A Planning Approach to Declarer Play in Contract Bridge
A Planning Approach to Declarer Play in Contract Bridge
Files
Publication or External Link
Date
1998-10-15
Authors
Smith, S.
Nau, Dana S.
Throop, T.
Advisor
Citation
DRUM DOI
Abstract
Although game-tree search works well in perfect-information games,
it is less suitable for imperfect-information games such as
contract bridge. The lack of knowledge about the opponents' possible moves
gives the game tree a very large branching factor, making it impossible
to search a significant portion of this tree in a reasonable amount of time.
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 5000 randomly generated notrump
deals, Tignum 2 beat the 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 an average time of only 27.5 seconds per deal on a Sun
SPARCstation 10. Further enhancements to Tignum~2 are currently
underway.
(Also cross-referenced as UMIACS-TR-95-85)