  This paper investigates the problems arising in the construction of a program
to play the game of contract bridge. These problems include both the difficulty
of solving the game's perfect information variant, and techniques needed to
address the fact that bridge is not, in fact, a perfect information game. GIB,
the program being described, involves five separate technical advances:
partition search, the practical application of Monte Carlo techniques to
realistic problems, a focus on achievable sets to solve problems inherent in
the Monte Carlo approach, an extension of alpha-beta pruning from total orders
to arbitrary distributive lattices, and the use of squeaky wheel optimization
to find approximately optimal solutions to cardplay problems. GIB is currently
believed to be of approximately expert caliber, and is currently the strongest
computer bridge program in the world.
