Experiments in heuristic search utilizing sampling and precomputation

There is an increasing fascination with programs that play games and especially those that play well. One game that is enjoyable to play, though difficult for programs to play well, is contract bridge. There are several reasons for this difficulty. Two of these difficulties are: 1) that the game consists of imperfect information, and 2) that the size of the game tree is too large for current searching techniques to solve. One goal described in this paper is to produce a bridge-playing program that can overcome these two difficulties. This program, referred to as the Bridge-player, used two ideas, sampling and precomputation, to assist it in the decision-making processes that enable it to play a single-dummy, no-trump contract bridge game. By using sampling to create hands for the unknown hands, the Bridge-player turns a game of imperfect information to one of perfect information. The precomputation is performed by constructing a game similar to contract bridge that is small enough to be exhaustively searched. The idea is that the solutions that work for this similar game will be beneficial to the sampling process for determining a correct play. This repeated action of generating hands and calculating an estimate of tricks to be won for each legal alternative allows the best alternative to be selected by maximizing on these estimates. The experiments and results described in this paper show that these two ideas are helpful in creating a bridge-playing program that plays the game well and suggests the usefulness of these ideas for other games as well.