Make No Mistake: Computers vs Suit Combinations
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
by Ian Frank, Ibaraki, Japan
and David Basin, Freiburg, Germany
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
Here is problem number 568 from the Encyclopedia, with the book's
(incorrect) solution:
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.
|