Join Bridge Winners
AI, Contract Bridge, Conventional Bidding. A casual update.

Many readers will be aware of the recent successes of unsupervised learning in the games area, for example by Alpha Zero and its progeny. Unsupervised means essentially that the computer teaches itself, based purely on the rules of the game, without a human supplying value functions or weights to various positions. Here are some of the games for which a program is “best” in the world along with the approximate year they surpassed humans:

Scrabble  ca. 1986 Maven     

Backgammon 1979 BKG 9.8

Checkers  ca. 1994 Chinook

Chess       1997 Deep Blue

Go            ca. 2017 Alpha Go

Shogi        ca. 2017 Alpha zero (match against other AI)

No-limit Texas hold ‘em (heads-up)           ca. 2017 Libratus

(Not all of these programs use unsupervised learning)

I have no doubt that AI will surpass humans in bridge at some point. Although there are 4 people involved, bridge is really a “2-person” game. Two-person is important for technical reasons because collusion of multiple opponents is not possible. (We ignore illegal communication by partners.) That is the reason that the Carnegie Mellon poker playing program competed in heads-up only.

Libratus is significant for another reason. Poker is an incomplete information game, like bridge (and Scrabble). It seems likely that many of the technical details of its success at poker will prove valuable at bridge. For those of a technical bent, see http://science.sciencemag.org/content/early/2017/12/15/science.aao1733 for the original publication.

While there are currently no world class bridge programs, unsupervised learning has been used to attack bidding in uncontested auctions. In July 2016, Yeh and Lin published the results of self-taught bidding: https://arxiv.org/pdf/1607.03290.pdf. Their program generated 140,000 N-S hands, bid them, and rated the success by subsequent double-dummy analysis versus an ensemble of 5 random E-W hands playing double-dummy defense.

While superseding humans at chess, programs discovered the solutions to a large number of previously unsolved end positions, such as rook-knight vs knight-knight. When it turned out that the number of moves needed to mate in these positions exceeded the previously allowed endgame move number of 50, the rules of chess were originally changed (several times) to accommodate this. Ultimately, when it was realized that very many end positions required exceedingly lengthy mating sequences the 50 move draw rule was restored. For kindred reasons, AI applied to bidding may (with no certainty) result in demands for more flexibility in allowed bidding conventions.

Consider the opening bids selected by the Yeh/Lin AI [Y-L] after its learning period. Recall that human criteria, such as point count, were not pre-programmed in. Ex posteriori, one can look at all the openings and see if they clustered into types based on suit length, Work point count, or other human-defined features. The results are very interesting. Here is an approximate summary from the paper of all the AI chosen opening bids:

PASS 0-10 HCP;

1♣ 11+ HCP;

1♦ 10+ HCP, 5+♥;

1♥ 12+ HCP, 5+♠;

1♠ 16+HCP, balanced;

1NT 12+ HCP, 6+♦;

2♣ Not used; 2♦ Not used;

2♥ 18+ HCP, 5-6♠;

2♠ Not used;

2NT 15-17 HCP, 6+♠.

The merit of this approach was tested by direct comparison with Wbridge5, described as the current state of the art (and computer world champion in 2016). It outperformed that program bidding 20,000 hands with results measured in IMPs over the expected double dummy results. However the performance of Y-L declined when its opening non-pass bid was constrained to match SAYC in its choice of opening bid.

Over the past decade, transfer methods have continually expanded. Y-L indicates that it may be optimal even at the initial call. Even the balanced hands are opened 1, a transfer. Also note the deference paid to spades, the boss suit. Three separate bids become assigned to showing spades: 1, 2 and 2NT.

Of course, this study is an early approach to bridge via unsupervised learning, and constrained to uncontested auctions. It would be premature to guess that subsequent efforts will reach similar conclusions. However given the rapid speed with which Deep Learning is progressing it would be naïve to think AI generated bridge progress will not explode shortly into our consciousness.

35 Comments
Getting Comments... loading...
.

Bottom Home Top