Computer chess
Computers began to compete against humans in the late
1960s. In February 1967 MacHack VI, a program written by
Richard Greenblatt, an MIT undergraduate, drew one game
and lost four in a U.S. Chess Federation tournament. Its
results improved markedly, from a performance equivalent
to a USCF rating of 1243 to reach 1640 by April 1967,
about the average for a USCF member. The first American computer
championship was held in New York City in 1970 and was
won by Chess 3.0, a program devised by a team of
Northwestern University researchers that dominated computer
chess in the 1970s.
Technical advances accelerated progress in computer
chess during the 1970s and '80s. Sharp increases in
computing power enabled computers to "see"
much further. Computers of the 1960s could evaluate
positions no more than two moves ahead, but authorities
estimated that each additional half-move of search would
increase a program's performance level by 250 rating
points. This was borne out by a steady improvement by
the best programs until Deep Thought played above the
2700 level in 1988. When Deep Blue, its successor, was
introduced in 1996, it saw as far as six moves ahead.
(Gary Kasparov said he normally looks only three to five
moves ahead, adding that for humans more are not
needed.)
Also helping computer progress was the
availability of microprocessors in the late 1970s. This
allowed programmers unattached to universities to
develop commercial microcomputers that by the 1990s were
nearly as strong as programs running on mainframes. By
the late 1980s the strongest machines were capable of
beating more than 90 percent of the world's serious
players. In 1988 a computer, HiTech, developed at
Carnegie Mellon University, defeated a grandmaster,
Arnold Denker, in a short match. In the same year
another Carnegie Mellon program, Deep Thought, defeated
a top-notch grandmaster, Bent Larsen, in a tournament
game.
HiTech used 64 computer chips, one for each
square on the board, and was capable of considering up
to 175,000 positions per second. Feng-Hsiung Hsu, a
Carnegie Mellon student, improved on HiTech with a
custom-designed chip. The result, Chiptest, won the
North American Computer Championship in 1987 and
evolved into Deep Thought, a program powerful enough to
consider 700,000 positions a second. Although its
evaluation skills were not as well developed as HiTech's--and
far below that of a human grandmaster--Deep Thought was
sponsored by International Business Machines Corporation
(IBM) in an effort to defeat the world's best player by
the mid-1990s in a traditional time limit.
At faster speeds even personal computers were able to
defeat the world's best humans by 1994. In that year a
Fritz 3 program, examining 100,000 positions per second,
tied for first place with Kasparov, ahead of 16 other
grandmasters, at a five-minute tournament in Munich,
Ger. Later in the year Kasparov was eliminated from a
game/25 tournament in London after losing a two-game
match against Genius running on a Pentium personal computer.
In 1991 Deep Thought's team said the program, renamed
Deep Blue, would soon be playing at the equivalent of a
3000 rating (compared with Kasparov's 2800), but this
proved excessively optimistic. The main improvement was
in the computer running the chess program. IBM
developed, and used chess to test, a sophisticated new
multiprocessing system (later used at the 1996 Olympic
Games in Atlanta, Ga., U.S., to predict the weather)
that employed 32 microprocessors, each with six
programmable chips designed specifically for chess. Deep
Thought, by comparison, had one microprocessor and no
extra chips. The new hardware enabled Deep Blue to
consider as many as 50 billion positions in three
minutes, a rate that was about a thousand times faster
than Deep Thought's.
Deep Blue made its debut in a six-game match with PCA
champion Kasparov in February 1996. The $500,000 prize
fund and IBM's live game coverage at their World Wide
Web site attracted worldwide media attention. The
Kasparov-Deep Blue match in Philadelphia was the first
time a world champion had played a program at a slow (40
moves in two hours) time format. Deep Blue won the first
game, but Kasparov modified his style and turned the
later games into strategic, rather than tactical,
battles in which evaluation was more important than
calculation. He won three and drew two of the remaining
games to win the match 4-2.
In a six-game rematch held May 3-11, 1997, in New
York City, an upgraded Deep Blue was able to consider an
average of 200 million positions per second, twice its
previous speed. Its algorithm for considering positions
was also improved with advice from human grandmasters.
By adopting a new set of conservative openings,
Kasparov forced Deep Blue out of much of its prematch
preparation. After resigning the second game, in a
position later found to be drawable, Kasparov said he
"never recovered" psychologically. With the
match tied at one win, one loss, and three draws, Deep
Blue won the decisive final game in 19 moves.
|