Next: Scrabble Up: Games Previous: Backgammon

## Bridge

In bridge the hidden information consists of the cards that the opponents hold. The current best bridge program GIB [14] performs simulations in two stages of the game: during the auction to make a bid and during the actual game to decide which card to play.

To select a bid, GIB deals cards to the opponents in a way that is consistent with the bidding observed so far. GIB uses a database to project how the auction will continue if a certain bid is made, and then computes the result of playing out the hand. The hands are played in a double dummy variation of bridge (assuming perfect information - knowledge of all four hands). At the end of the simulation the bid with the maximal expected value is returned.

During a game, a simulation consists of dealing cards to the opponents in a manner that is consistent with the bidding and the cards played so far. The score of a move is determined by playing out the hand in a double dummy mode [12]. Repeated deals are played until either enough confidence is gained to decide which card to play, or a maximum number of hands is simulated, or a real-time constraint is met.

Opponents' cards are constrained by the information given by each player about the hand during the bidding. GIB also uses a probability distribution of the possible cards held by an opponent to bias the card dealings towards the most likely ones. This probability distribution is adjusted by identifying mistakes the opponents might make during the game. For example, assume that GIB's analysis says that 75% of the time that a player holds a specific card and does not play it in a particular game situation that an error has occurred. The probability of this opponent holding that card is modified accordingly after GIB observes that the card was not played.

Simulations have allowed GIB to play hands at a world-class level; however, limitations in the simulation-based approach and the high variance have prompted the author of GIB, Matt Ginsberg, to look at other solutions (including building the entire search tree) [13].

Next: Scrabble Up: Games Previous: Backgammon
Lourdes Pena
1999-09-10