Robotics Reference
In-Depth Information
Its strength lies in a strong relationship between bidding rules and
hand evaluation as the auction proceeds. The human user of CO-
BRA is not required to take any action whatsoever during the auc-
tion except to “calculate” the next bid, just as a computer will per-
form this menial task. [6]
Ginsberg points out that while attempts at computer bidding, such as
COBRA, appeared to have been able to perform at expert level during
the early 1980s, the technique and style of bidding in top-class Bridge
has advanced considerably since then, and machine performance using
such systems “is no longer likley to be competitive.” [5] Partly because
of this, Ginsberg pioneered the use of Monte Carlo methods for bidding
in Bridge.
The Monte Carlo approach to bidding is to generate a large num-
ber of deals, all consistent with the bidding that has taken place in the
hand thus far and with the cards held by the program player which is
considering its next bid. For each of the program's plausible bids, the
simulation process hypothesizes how the auction might continue after
that bid is made, considering all plausible bids by all four players. At
the end of each hypothesized bidding sequence the program knows the
final contract and it knows, from the meanings of the bids in each of
these bidding sequences, certain things about how the cards lie, for ex-
ample how many aces and kings are held by certain players. Knowing
this information allows the program to determine, from a Monte Carlo
simulation of the play of the cards, the likely result of the play if that par-
ticular bidding sequence is followed. So for each hypothesized bidding
sequence the program has an estimate of the number of tricks its part-
nership will take, and hence of the score that its partnership will achieve.
The program then chooses to make the bid for which the hypothesized
follow-up bidding sequences indicate the highest average scores for its
partnership.
Backgammon—A Game with Chance
Backgammon is a game with perfect information but it also has a chance
element—the roll of the dice that determines what moves a player may
make. This chance element creates its own problems for the programmer.
One of these problems is the large number of permutations of rolls of the
dice and the number of legal moves for each of the possible rolls, that a
program would need to include in a game tree. The roll of two dice
