Robotics Reference
In-Depth Information
nique known as Monte Carlo simulations for the playing phase. My
reason for being provocative was that World Champion Zia Mahmood
had been quoted in a British newspaper, the
Daily Express
, as offering
a prize of one million pounds for a program that could defeat him and
his partner at Bridge. My paper suggested how I thought this could be
achieved, using Monte Carlo methods for the play of the cards. Matt
Ginsberg was the first Bridge programmer to adopt this approach. His
program GIB, which was introduced in the mid-1990s, was a winner of
the World Computer Bridge Championship. During the 1998 (human)
World Bridge Championships in France, GIB was invited to compete in
an international tournament in which the participants attempt to solve
difficult Bridge playing problems in which they can see all of the cards.
41
GIB competed alongside 34 of the world's top human players and at the
halfway stage it led the tournament, but dropped back on the second day
to finish in a highly respectable twelfth place.
In card games, the idea of Monte Carlo sampling is based on guess-
ing in which hands the hidden cards might lie. The hope is that by
examining a sufficiently large sample of situations that conform to the
constraints of the deal, a playing decision that works well in a large pro-
portion of the sample can be found. The way that Monte Carlo methods
are used in Bridge play is to generate a set of deals that are all consistent
with the bidding and with any play that has taken place thus far in the
hand. For example, if one of the program's opponents had made a first
bid of “one heart”, and if the program's opponents are employing a bid-
ding system in which an opening bid of one heart means “I have at least
five hearts in my hand”, then Monte Carlo sampling would generate only
deals in which that particular player holds at least five cards in the heart
suit. All hands dealt as part of a Monte Carlo simulation must conform
to all such known constraints.
When a valid deal is generated by the Monte Carlo process the pro-
gram knows the locations of all the cards in that deal. It examines each
of the cards it could legally play at that point and determines how many
tricks its partnership would make, taking advantage of the knowledge of
where all the cards lie. After generating a large number of deals that are
consistent with the information at its disposal, and after testing the result
of playing each card from its current situation in each of these deals, the
program simply counts how many tricks its partnership would make for
41
These are called double dummy problems.
