Robotics Reference
In-Depth Information
creates 21 distinct possibilities:
1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5,
3-6, 4-4, 4-5, 4-6, 5-5, 5-6 and 6-6.
For each of these rolls a program must examine every legal move that
can be made by its men, and there may be many of them. The average
number of legal plays for each roll of the dice in Backgammon is ap-
proximately 20, so with 21 possible rolls the average number of possible
roll-and-play combinations from a position is approximately 420 (i.e., 20
x 21). Comparing this figure to the typical numbers of moves possible in
Checkers (which lies between eight and ten) and in Chess (an average of
37) gives some indication of the magnitude of the problem if the game
were to be programmed using a deep tree-search. Since this number of
combinations is higher even than the maximum number of legal moves
in Go (361), it is not difficult to understand why Backgammon program-
mers tend to avoid the idea of using a deep tree-search. And because of
the chance element created by the dice, it has been found that beyond a
few half-moves, search in Backgammon is of no benefit.
The earliest Backgammon program of note, called BKG, was devel-
oped by Hans Berliner at Carnegie Mellon University with about one
man-year of effort, starting in mid-1974. Berliner is a former World
Champion at Correspondence Chess and has also been a true giant in
the world of strategy games programming. What was remarkable about
Berliner's Backgammon program was not so much that that it was able
to play at a very high level, but that its strength was due largely to the
sophistication of the program's evaluation function with no look-ahead
at all.
On 15 July 1979, Luigi Vila, who had just won the World Backgam-
mon Championship, played a match in Monte Carlo against BKG ver-
sion 9.8, for the first player to reach seven points. The cash stakes were
a winner-take-all purse of $5,000 but the event turned out to be of far
greater import for the human race than was suggested by the size of the
cash prize. The program won by a score of 7-1, thereby becoming the
world's first man-made entity to defeat a reigning human World Cham-
pion at a recognized intellectual activity.
Post-mortem analysis of the games showed that Vila made far fewer
mistakes and that the computer was lucky with the numbers that were
rolled on the dice. Berliner was rather maganimous in victory:
