Computer Bridge - Properties of Double-dummy Bridge Compared To Other Strategy Games

Properties of Double-dummy Bridge Compared To Other Strategy Games

While bridge is a game of incomplete information, a double-dummy solver analyses a simplified version of the game where there is perfect information; the bidding is ignored, the contract (trump suit and declarer) is given, and all players are assumed to know all cards from the very start. The solver can therefore use many of the game tree search techniques typically used in solving two-player perfect-information win/lose/draw games such as chess, go and reversi.

However, there are some significant differences worth mentioning.

• Although double-dummy brigde is in practice a competition between two generalised players, each "player" controls two hands and the cards must be played in a correct order that reflects four players. (It makes a difference which of the four hands wins a trick and must lead the next trick.)
• Double-dummy brigde is not simply win/lose/draw and not exactly zero-sum, but constant-sum since two playing sides compete for 13 tricks. It is trivial to transform a constant-sum game into a zero-sum game. Moreover, the goal (and the risk management strategy) in general contract bridge depends not only on the contract but also on the form of tournament. However, since the double-dummy version is deterministic, the goal is simple: one can without loss of generality aim to maximize the number of tricks taken.
• Bridge is incrementally scoring; each played trick contributes irreversibly to the final "score" in terms of tricks won or lost. This is in contrast to games where the final outcome is more or less open until the game ends. In bridge, the already determined tricks provide natural lower and upper bounds for alpha-beta pruning, and the interval shrinks naturally as the search goes deeper. Other games typically need an artificial evaluation function to enable alpha-beta pruning at limited depth, or must search to a leaf node before pruning is possible.
• It is relatively inexpensive to compute "sure winners" in various positions in a double-dummy solver. This information improves the pruning. It can be regarded as a kind of evaluation function, however while the latter in other games is an approximation of the value of the position, the former is a definitive lower bound on the value of the position.
• During the course of double-dummy game tree search, one can establish equivalence classes consisting of cards with apparently equal value in a particular position. Only one card from each equivalence class needs to be considered in the subtree search, and furthermore, when using a transposition table, equivalence classes can be exploited to improve the hit rate. This has been described as partition search by Matthew Ginsberg (the creator of GIB).