Computer bridge

Computer bridge is the playing of the game contract bridge utilizing computer software. Following years of limited progress, at the end of the twentieth century the field of computer bridge has made major advances. In 1996 the American Contract Bridge League (ACBL) established an official World Computer-Bridge Championship, to be held annually along with a major bridge event. The first championship took place in 1997 at the North American Bridge Championships in Albuquerque. Since 1999 the event has been conducted as a joint activity of the American Contract Bridge League and the World Bridge Federation. Alvin Levy, ACBL Board member, initiated this championship and has coordinated the event annually since its inception. The event history, articles and publications, analysis, and playing records can be found at the official website.

World Computer-Bridge Championship

The World Computer-Bridge Championship is typically played as a round robin followed by a knock-out between the top four contestants.[1][2] Winners of the annual event are:

Computers versus humans

In Zia Mahmood's book, Bridge, My Way (1992), Zia offered a £1M bet that no four-person team of his choosing would be beaten by a computer. A few years later the bridge program GIB,[4] brainchild of American computer scientist Matthew Ginsberg,[5] proved capable of expert declarer plays like winkle squeezes in play tests. In 1996, Zia withdrew his bet.[6] Two years later, GIB became the world champion in computer bridge, and also had a 12th place score (11210) in declarer play compared to 34 of the top humans in the 1998 Par Contest (including Zia Mahmood).[7] However, such a par contest measures technical bridge analysis skills only, and in 1999 Zia beat various computer programs, including GIB, in an individual round robin match.[8]

Further progress in the field of computer bridge has resulted in stronger bridge playing programs, including Jack [9] and Wbridge5.[10] These programs have been ranked highly in national bridge rankings. A series of articles published in 2005 and 2006 in the Dutch bridge magazine IMP describes matches between five-time computer bridge world champion Jack and seven top Dutch pairs including a Bermuda Bowl winner and two reigning European champions. A total of 196 boards were played. Jack defeated three out of the seven pairs (including the European champions). Overall, the program lost by a small margin (359 versus 385 imps).

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.

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.

The future

In comparison to computer chess, computer bridge is in its infancy. Yet, whereas computer chess has taught programmers little about building machines that offer human-like intelligence, more intuitive and probabilistic games such as bridge might provide a better testing ground.

The question whether bridge-playing programs will reach world-class level in the foreseeable future is not easy to answer. Computer bridge has not attracted an amount of interest anywhere near to that of computer chess. On the other hand, researchers working in the field have accomplished most of the current progress in the last decade.

Irrespective of the results of computers against humans in tournament bridge, computer bridge already has changed the analysis of the game. Commercially available double-dummy programs can solve bridge problems in which all four hands are known, typically within a second. These days, few editors of books and magazines will solely rely on humans to analyse bridge problems before publications. Also, more and more bridge players and coaches utilize computer analysis in the post-mortem of a match.

See also

References

  1. ↑ ACBL/WBF World Computer-Bridge Championship Official Site
  2. ↑ World Computer Bridge Championship - List of contestants and their links
  3. ↑ "Meadowlark" was in fact GIB's playing engine, competing under a pseudonym
  4. 1 2 GIB Website
  5. 1 2 Ginsberg profile
  6. ↑ Zia's bet and the rise of computer bridge as reported in the Netherlands bridge magazine IMP
  7. ↑ "Rosenberg Wins Par Contest" (PDF).
  8. ↑ Foreword to Man vs Machine - The Bridge Match of the Millennium
  9. ↑ Jack homepage
  10. ↑ WBridge5 homepage (in French)

Shark Bridge home page

External links

This article is issued from Wikipedia - version of the Friday, October 30, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.