Search in Games with Incomplete Information:
A Case Study using Bridge Card Play
Ian Frank, David Basin
Artificial Intelligence, Vol. 100, Pp. 87--123, 1998
The version on these pages is an earlier ETL Technical Report,
ETL-TR-97-7
Abstract:
We examine search algorithms in games with incomplete information,
formalising a reduced model of such games based on the assumptions
typically made when incomplete information problems are analysed in
expert texts. We show that equilibrium point strategies for optimal
play exist for this model, and define an algorithm capable of
computing such strategies. Using this algorithm as a reference we
then analyse search architectures that have been proposed for the
incomplete information game of Bridge. These architectures select
strategies by analysing some statistically significant collection of
complete information sub-games. Our model allows us to clearly state
the limitations of such architectures in producing expert analysis,
and to precisely formalise and distinguish the problems that lead to
sub-optimality. We illustrate these problems with simple game trees
and with actual play situations from Bridge itself.
|