Computer bridge is the playing of the game
contract bridge
Contract bridge, or simply bridge, is a trick-taking card game using a standard 52-card deck. In its basic format, it is played by four players in two competing partnerships, with partners sitting opposite each other around a table. Millions ...
using computer software. After years of limited progress, since around the end of the 20th century the field of computer bridge has made major advances. In 1996 the
American Contract Bridge League
The American Contract Bridge League (ACBL) is a governing body for contract bridge in the United States, Canada, Mexico, and Bermuda. It is the largest such organization in North America having the stated mission ''"to promote, grow and sustain t ...
(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
The World Bridge Federation (WBF) is the international governing body of contract bridge. The WBF is responsible for world championship competitions, most of which are conducted at a few multi-event meets on a four-year cycle. The most prestigiou ...
. 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. Winners of the annual event are:
*1997 ''Bridge Baron''
*1998 ''GIB''
*1999 ''GIB''
*2000 ''Meadowlark Bridge''
*2001 ''Jack''
*2002 ''Jack''
*2003 ''Jack''
*2004 ''Jack''
*2005 ''Wbridge5''
*2006 ''Jack''
*2007 ''Wbridge5''
*2008 ''Wbridge5''
*2009 ''Jack''
*2010 ''Jack''
*2011 ''Shark Bridge''
*2012 ''Jack''
*2013 ''Jack''
*2014 ''Shark Bridge''
*2015 ''Jack''
*2016 ''Wbridge5''
*2017 ''Wbridge5''
*2018 ''Wbridge5''
*2019 ''Micro Bridge''
*2020 championship has been cancelled
*2021 championship has been cancelled
Computers versus humans
In
Zia Mahmood's book, ''Bridge, My Way'' (1992), Zia offered a £1 million bet that no four-person team of his choosing would be beaten by a computer. A few years later the bridge program ''GIB'' (which can stand for either "Ginsberg’s Intelligent Bridgeplayer" or "
Goren In a Box"), brainchild of American computer scientist Matthew Ginsberg,
[Ginsberg profile](_blank)
/ref> proved capable of expert declarer plays like winkle squeezes in play tests. In 1996, Zia withdrew his bet. 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). 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.
Further progress in the field of computer bridge has resulted in stronger bridge playing programs, including ''Jack'' and ''Wbridge5''. 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
The Bermuda Bowl is a biennial contract bridge world championship for national . It is contested every odd-numbered year under the auspices of the World Bridge Federation (WBF), alongside the Venice Cup (women), the d'Orsi Senior Bowl and the W ...
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).
In 2009, Phillip Martin, an expert player, began a four-year project in which he played against the champion bridge program, Jack. He played one hand at one table, with Jack playing the other three; at another table, Jack played the same cards at all four seats, producing a comparison result. He posted his results and analysis in a blog he titled ''The Gargoyle Chronicles''. The program was no match for Martin, who won every contest by large margins.
Cardplay algorithms
Bridge poses challenges to its players that are different from board games such as chess
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to dist ...
and go. Most notably, bridge is a stochastic
Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselve ...
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 using a so-called "double-dummy solver" that uses extensive search algorithms to determine 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
Importance sampling is a Monte Carlo method for evaluating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. Its introduction in statistics is generally att ...
are used to generate sets of samples that are of minimum size but still representative.
Comparison 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
In economics, perfect information (sometimes referred to as "no hidden information") is a feature of perfect competition. With perfect information in a market, all consumers and producers have complete and instantaneous knowledge of all market pr ...
; 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
In the context of Combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, c ...
search techniques typically used in solving two-player perfect-information win/lose/draw games such as chess
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to dist ...
, go and reversi
Reversi is a strategy board game for two players, played on an 8×8 uncheckered board. It was invented in 1883. Othello, a variant with a fixed initial setup of the board, was patented in 1971.
Basics
There are sixty-four identical game pieces ...
. However, there are some significant differences.
* Although double-dummy bridge 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 bridge is not simply win/lose/draw and not exactly zero-sum
Zero-sum game is a mathematical representation in game theory and economic theory of a situation which involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is ...
, 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 (due to differences in scoring systems affecting the optimal general strategy). However, once the game has been reduced to deterministic double-dummy analysis, the goal is simple: one can without loss of generality aim to maximize the number of tricks taken.
* Bridge is incrementally scored; 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 Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to:
*The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
* Alpha Beta, a former chain of Californian supermarkets
*Alpha and beta anomer ...
, and the interval shrinks naturally as the search goes deeper. Other games typically need an artificial evaluation function
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position (usually at a leaf or terminal node) in a g ...
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
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position (usually at a leaf or terminal node) in a g ...
, 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
{{no footnotes, date=November 2017
A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the ...
, equivalence classes can be exploited to improve the hit rate. This has been described as ''partition search'' by Matthew Ginsberg.
*Numerous strategy games have been proven hard in a complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms ...
, meaning that any problem in that complexity class can be reduced in polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
to that problem. For example, generalized chess
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to dist ...
has been proven -complete (both in and -hard), effectively meaning that it is among the hardest problems in . However, since there is no natural structure to exploit in double-dummy bridge towards a hardness proof or disproof, unlike in a board game, the question of hardness remains.
The future
In comparison to computer chess
Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
, computer bridge has not reached world-class level, but the top robots have demonstrated a consistently high level of play. (See analysis of the last few years of play a
www.computerbridge.com
) However see below the Philippe Pionchon's article (1984). Yet, whereas computer chess has taught programmers little about building machines that offer human-like intelligence, more intuitive
Intuition is the ability to acquire knowledge without recourse to conscious reasoning. Different fields use the word "intuition" in very different ways, including but not limited to: direct access to unconscious knowledge; unconscious cognitio ...
and probabilistic games such as bridge
A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...
might provide a better testing ground.
The question of 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, much progress has been made in the last decade by researchers working in the field.
Regardless of bridge robots' level of play, 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 fraction of a second. These days, few editors of books
A book is a medium for recording information in the form of writing or images, typically composed of many pages (made of papyrus, parchment, vellum, or paper) bound together and protected by a cover. The technical term for this physica ...
and magazines
A magazine is a periodical publication, generally published on a regular schedule (often weekly or monthly), containing a variety of content. They are generally financed by advertising, purchase price, prepaid subscriptions, or by a combina ...
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
* List of computer science awards
This list of computer science awards is an index to articles on notable awards related to computer science. It includes lists of awards by the Association for Computing Machinery, the Institute of Electrical and Electronics Engineers, other comput ...
* Computer Olympiad
The Computer Olympiad is a multi-games event in which computer programs compete against each other. For many games, the Computer Olympiads are an opportunity to claim the "world's best computer player" title. First contested in 1989, the majori ...
* Monte Carlo method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deter ...
* Monte Carlo tree search
In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree.
MCT ...
* Importance sampling
Importance sampling is a Monte Carlo method for evaluating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. Its introduction in statistics is generally att ...
* Hanabi (card game)
References
External links
World Computer-Bridge Championship – ACBL/WBF bridge-bot world championship
(official website)
*
*
*
* Classic analysis of AI applied to bridge.
{{DEFAULTSORT:Computer Bridge
Contract bridge
Game artificial intelligence
Computer science competitions