Home Page

Publications

Misc AI Links

My Weather

FINESSE

MIKE

Ian Frank, David Basin

Bridge World, Vol 72, Num 2, November 2000, Pp 15 --19.

© The Bridge World. The copyright for this work is held by The Bridge World. We thank them for granting the permission to reproduce the full text below. Others seeking to make copies of this article (electronic or otherwise) should contact the Bridge World directly.

Make No Mistake: Computers vs. Suit Combinations

Over the last few years, the public profile of computer game-playing has reached new heights with the feats of the chess computer Deeper Blue. In many other games as well, researchers in industry and academia have produced computer players that can hold their own against the strongest humans. Until recently, though, computer analysis of bridge has been far inferior to that of homo sapiens.

Times are changing. Recently, Zia challenged seven computers in London. Such an event would have been unthinkable just a few years ago. Zia won, but said of the competition, "It was much more difficult than I anticipated."

Increasingly, computers are making fewer mistakes. This is evident in a program, Finesse, that we designed to find optimal plays under the assumption of best defense. To do this, we formalized the underlying mathematical theory and then investigated what is required to play optimally.

Finesse solves card combinations very well. We demonstrated this by testing it on 650 single-suit problems in the Official Encyclopedia of Bridge. All problems assume adequate entries wherever needed, and we compared just the lines of play for the maximum possible numbers of tricks. Our software gets all these cases right, a level of performance that few human players could match. Indeed, Finesse sometimes discovers lines of play that are better than the Encyclopedia's. Below, we give two examples of this and then describe the bridge knowledge that the program uses to solve such problems.

Two New Lines of Play

NORTH
A 10 3 2
SOUTH
9 5 4

For two tricks, lead low to the nine. If this loses to West, finesse the ten next. If an honor appears from East on the first round, lead low to the nine again; if East shows out or plays another honor, finesse the ten next; otherwise, play to the ace. Chance of success: 51%

This is one of the more complicated lines of play in the book. It succeeds against KQJx|xx, Kxxx|QJ, Qxxx|KJ, Jxxx|KQ, all three-three splits except xxx|KQJ, and when the West-East cards are split six=zero or five=one. Summing the probabilities of these cases verifies the 51% figure.

To check this solution, we looked up the situation in Jean-Marc Roudinesco's Dictionary of Suit Combinations. Roudinesco gives the same line of play, with the same chance of success. However, when we gave this problem to Finesse, we obtained a different suggestion: Lead low to the nine. If East plays low and West wins, cash the ace next. If an honor appears from East on the first round, run the nine and then finesse the ten. Chance of success: 57.5%.

The crucial distributions are those where West holds HHxx, H standing for any honor. The competing approaches both recommend starting by leading low towards the nine, confronting East with a choice.

Let's consider first what happens when East plays low. The nine will then lose to West. In the Encyclopedia's line, the continuation is then to finesse the ten, which will lose to East's honor. Finesse's continuation of the ace succeeds.

What happens if East goes up with an honor on the first round? The Encyclopedia, which continues with small to the nine and then the ace, fails. Finesse runs the nine and then finesses the ten, which succeeds.

So, Finesse's line of play gains whenever the defenders' cards are split HHxx|Hx (probability 0.1453). However, by cashing the ace on the second round after East plays low on the first, Finesse loses in comparison against KQJx|xx and KQJxx|x (total probability of 0.0848). Overall, the chances favor Finesse's solution by 0.1453 - 0.0848 = 0.0605.

A second example where Finesse's solution is better than The Encyclopedia's is number 601:

NORTH
Q 5 4 3 2
SOUTH
J 9 6

The Encyclopedia: For three tricks, lead small to the queen. If that loses to East, finesse the nine next; if an honor appears from West on the first round, lead toward the queen again. Chance of success: 48%

This line succeeds against all two=three splits except 10x|AKx, and all three=two splits except A10x|Kx and K10x|Ax. (The Encyclopedia introduces a slight rounding error by rounding up the probability of these distributions from 0.4748 to 0.48.) The Dictionary of Suit Combinations also gives a chance of success of 0.4748, although it suggests a slightly different approach.

Finesse's line is different: For a chance of success of 50.3%, lead low to the jack. (1) If West wins, lead low from the South hand, playing low from North unless West plays the ten. (2) If West plays the ten under the jack, lead low to the nine. (3) If East plays an honor, lead to the jack.

This line of play wins three tricks against all two=three splits except Kx|A10x and Ax|K10x, and all three=two splits except AKx|10x. This is the same total number of three-two breaks that the Encyclopedia's line handles. However, Finesse manages also to cope with a one=four layout, when West holds the singleton ten (probability 0.0283).

Of particular interest is how Finesse proceeds after the jack loses, and West later follows to a lead from the South hand with a low card. Finesse's action, to duck, illustrates that the program realizes that each card played by the defenders changes the probabilities, and that the best play at any given point may be conditional on the cards already revealed. Remarkably, this is one of only two examples among the 650 Encyclopedia problems where the card played by second hand changes the probabilities to such an extent that the declarer's third-hand play is altered. (To demonstrate this, we programmed a version of Finesse that bases its tactics only on probabilities calculated after every completed trick, rather than after every card played. The modified program solved all the Encyclopedia examples correctly except for this problem and one other, number 622.)

How Does the Program Work?

A primary challenge in the design of game-playing programs is to avoid being swamped by the overwhelming number of possible moves. Typically, at any point there are many possibilities, and the consequences of choosing any of these may be important. Yet, in bridge (as in many other games), human players do not exhaustively consider all possible sequences of moves. Instead, they plan their play using higher-level concepts and chunks of knowledge gained from experience. For example, one type of bridge knowledge is a familiarity with common tactics such as taking finesses and cashing winners.

The incorporation of high-level knowledge was a guiding principle behind our design of Finesse. We codified bridge knowledge about single-suit combinations into a list of precise tactics, then constrained the computer to construct lines of play based on only those tactics. We then gave Finesse sufficient mathematical strength to pick the best overall line of play from among any set of alternatives it could build.

We were surprised to find that only seven fundamental tactics were required to generate all potentially useful strategies for attacking card combinations. Although humans usually learn these techniques through experience, we have not come across any bridge textbook that presents this list explicitly.

The two simplest tactics are "cash" and "duck." These correspond to taking a winning card and playing a low one. Another relatively straightforward tactic is one we call "sequence." This handles situations where there are enough high cards to play one on each trick, and there is no element of maneuvering against particular outstanding cards. For example:

NORTH
K Q J
SOUTH
9 5 2

NORTH
Q 8 3
SOUTH
K J 5

The remaining four tactics, which involve finessing, are more interesting. Here, we will call a non-master card with which declarer tries to win a trick a "finesse card." A "lead card" is the card that declarer leads in order to initiate a finesse. A "cover card" is a card held by third hand that is capable of beating at least one of the outstanding cards above the finesse card. With these definitions, we can describe the four types of finesse as follows:

Type 1. The finesse card and cover card are in the same hand (i.e., they are a tenace), opposite the lead card.

NORTH
A Q 10
SOUTH
9 4 2

NORTH
A J 10
SOUTH
8 6 5 3

Type 2. The finesse card is also the lead card, and the opposite hand contains a cover card and a duck card. Furthermore, the finesse card must belong to a sequence (two or more cards with no outstanding cards between them) held by the declarer's combined hands.

NORTH
A Q 5 3
SOUTH
J 4 2

NORTH
A 7 4
SOUTH
Q J

Type 3. The finesse card and a "duck card" are opposite the lead card. No cover card is necessary.

NORTH
K Q 2
SOUTH
8 5 3

NORTH
A 6 4
SOUTH
Q 7 5

Type 4. The finesse card is the lead card and is led toward third hand, which holds a cover card. The card directly below the finesse card is held by the defense, and the card directly below that is held by declarer's side. Either the finesse card is a singleton, or there is a continuation for the next trick that uses the card two ranks below it as a finesse card for a Type 1 or a Type 2 finesse.

NORTH
K 5 2
SOUTH
A J 9

NORTH
A 9 8
SOUTH
K J 4

Building knowledge of these tactics into the program took time, but it also provided some valuable paybacks. Most significantly, Finesse was able not only to find solutions to card-combination problems but also to explain its plays to humans. The latter capability is a contrast with most game-playing programs. For instance, ask a typical chess-playing program why it made a move and you are lucky to get back a screenful of numbers. Finesse is different. It can automatically produce explanations, such as "finesse the queen; this leads to two tricks when West holds the king." The explanations produced by Finesse are easily understandable, because the lines of play themselves are built using bridge concepts that are familiar to human players.

What Lies in the Future?

Solving bridge problems is hard. Indeed, it is less surprising that humans make mistakes than that they can play as well as they do. For instance, the total number of outright errors discovered by Finesse in The Encyclopedia was only nine. Of these, one is a simple typo (number 609), and two are cases where the probability calculation is slightly wrong (numbers 31 and 430). In the remaining six cases, Finesse's line of play has a better chance of success than the book's (numbers 289, 477, 543, 568, 601, and 622), but the two problems described in detail above are the only ones for which The Dictionary of Suit Combinations is also wrong.

Although Finesse does very well on these problems, work on the system continues. For example, one thing our current program won't do is to try to take advantage of mistakes by the defense. The Encyclopedia attempts to incorporate this aspect of the game in its descriptions, often including extra explanations such as, "This line offers extra chances if West is tempted to win from king-ten-x-x-x." But this kind of reasoning can be tricky. Finesse identifies a total of seven problems where the Encyclopedia's given solution actually makes unstated assumptions about the defense's playing sub-optimally (numbers 437, 459, 541, 548, 590, 591, and 595).

A long-term project is to investigate how our use of fundamental tactics can be extended to generate full-deal declarer-play strategies. In the short term, though, our goal is to create a powerful instructor for single-suit play. This will be a tutor that knows about bridge, that can explain itself in simple English, and that never gets tired. Moreover, it will teach the student to play as well as the most capable humans --- and sometimes, even better.