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
rep�
resent information about bridge in a task network that is extended
to rep�
resent 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 ff = 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.
%0 Journal Article
%1 smith96planning
%A Smith, Stephen J. J.
%A Nau, Dana S.
%A Throop, Thomas A.
%D 1996
%J Computational Intelligence
%K bridge game game, game�playing, imperfect information, planning, pruning, tree, uncertainty,
%P 106-130
%T A Planning Approach to Declarer Play in Contract Bridge
%U citeseer.ist.psu.edu/smith96planning.html
%V 12
%X 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
rep�
resent information about bridge in a task network that is extended
to rep�
resent 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 ff = 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.
@article{smith96planning,
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
rep�
resent information about bridge in a task network that is extended
to rep�
resent 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 \emph{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 ff = 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.},
added-at = {2007-11-23T14:13:20.000+0100},
author = {Smith, Stephen J. J. and Nau, Dana S. and Throop, Thomas A.},
biburl = {https://www.bibsonomy.org/bibtex/2555ee844076c2adedda2e29a2eedfe48/ramaz},
interhash = {e7efa328cf4e73dbd45681a73ff90377},
intrahash = {555ee844076c2adedda2e29a2eedfe48},
journal = {Computational Intelligence},
keywords = {bridge game game, game�playing, imperfect information, planning, pruning, tree, uncertainty,},
pages = {106-130},
timestamp = {2007-11-23T14:13:40.000+0100},
title = {A Planning Approach to Declarer Play in Contract Bridge},
url = {citeseer.ist.psu.edu/smith96planning.html},
volume = 12,
year = 1996
}