Cardplay Algorithms
Bridge poses challenges to its players that are different from board games such as chess and go. Most notably, bridge is a stochastic game of incomplete information. At the start of a deal, the information available to each player is limited to just his/her own cards. During the bidding and the subsequent play, more information becomes available via the bidding of the other three players at the table, the cards of the partner of the declarer (the dummy) being put open on the table, and the cards played at each trick. However, it is only at the end of the play that full information is obtained.
Today's top-level bridge programs deal with this probabilistic nature by generating many samples representing the unknown hands. Each sample is generated at random, but constrained to be compatible with all information available so far from the bidding and the play. Next, the result of different lines of play are tested against optimal defense for each sample. This testing is done utilizing a so-called double-dummy solver that via extensive search algorithms determines the optimum line of play for both parties. The line of play that generates the best score averaged over all samples is selected as the optimal play.
Efficient double-dummy solvers are key to successful bridge-playing programs. Also, as the amount of computation increases with sample size, techniques such as importance sampling are used to generate sets of samples that are of minimum size but still representative.
Read more about this topic: Computer Bridge