Author: Kai Middleton
Date: 11:06:46 05/13/98
As it is now a year since the last match I have been looking for old
articles on the match. This June 1997 article from Byte gave more
details on the hardware of Deep Blue than most.
http://www.byte.com/art/9707/sec6/art6.htm
Was world chess champion Garry
Kasparov defeated by a computer, or
by a team of engineers and grand
masters who beat the game clock?
Tom R. Halfhill
So IBM's Deep Blue beat Garry Kasparov. What's the big
deal? Computers have been whipping humans at all kinds of
games for years. And besides, most people don't get paid
$400,000 for losing. Whether running old classics like
Pac-Man, Asteroids, or Galaxian or newer games like
Doom and Quake, computers have an inherent speed
advantage that no mere mortal can possibly match.
Of course, chess is different -- it's not a twitch game like
Pac-Man or Doom. It demands strategic thinking, not quick
reactions.
Or does it?
After analyzing the technology behind Deep Blue, it's difficult
to avoid the conclusion that what really happened at the
world's most historic chess match is this: IBM turned chess
into a twitch game.
The prevailing view is that Kasparov was beaten by a
sophisticated chess program running on a 1.4-ton IBM
supercomputer. Even Kasparov and his adviser apparently
think so. However, another view is that Kasparov was
beaten by a team of engineers, programmers, and grand
masters who used a supercomputer to dodge the game clock
in tournament chess.
Playing alone, one on one, it's highly unlikely that any of the
human members of IBM's Deep Blue team could defeat
Kasparov. But playing together, pooling their talent, IBM's
players probably could defeat Kasparov -- if they had
almost unlimited time to ponder their moves, while still
holding Kasparov to the game clock.
It's possible to calculate how much time IBM's team needed
to win. A tournament chess player has an average of 3
minutes to make each move. IBM estimates that a player of
Kasparov's skill can evaluate about three moves per second,
or roughly 540 moves in 3 minutes. Based on past
experience -- Kasparov's victory over Deep Blue in 1996 --
IBM's team was fairly certain it needed to consider 36 billion
moves in 3 minutes. Expressed another way, they needed the
equivalent of about 380 years to agree on each move.
Anything less wasn't enough. Everybody knows how tedious
committees are, but this is ridiculous. It's doubtful the World
Chess Federation would sanction such a protracted
tournament, especially since it would have to be completed
by Kasparov's descendants. So IBM found a work-around:
It built a specialized supercomputer that could compress
those 380 years into 3 minutes.
In other words, the real loser in this tournament was the
game clock, which fell victim to brute force. Brute force is a
computing tradition that dates back to ENIAC's
number-crunching of artillery ballistic tables in the 1940s.
Indeed, the comparison is apt in more ways than one. Like
the hard-wired programs that ran on the vacuum tubes of
ENIAC, the Deep Blue program is substantially hard-coded
into the circuitry of a one-of-a-kind computer.
Beating the Clock
The Deep Blue team resists the brute force explanation.
Brute force implies that the computer triumphed by dumbly
examining every possible move instead of applying an
understanding of chess to evaluate the tactical situation.
Dismissing Deep Blue as a number-cruncher would seem to
diminish the team's 12-year effort to create the world's most
formidable chess program.
Certainly no one would argue that Deep Blue isn't a skillful
piece of programming. However, an examination of Deep
Blue's evolution leaves little doubt that its creators have
always gone to extraordinary lengths to exploit a computer's
most abundant resource: speed.
From the very beginning in 1985, when Deep Blue was
born, it wasn't just another chess program. Thomas
Anantharaman, a doctoral student in computer science at
Carnegie Mellon University, wrote the original code.
Another doctoral student, Feng-hsiung Hsu, hard-coded the
most time-critical move-generation routines into a custom
VLSI chip. Hsu took this unusual step even though the
program was already running on one of the fastest Sun
workstations available.
Known as Chiptest, the hardware-assisted program could
evaluate 50,000 possible board positions per second -- up
to 9 million moves in the average 3 minutes allotted to a
tournament chess player. That might seem like an enormous
advantage, but it wasn't. Chiptest could not come close to
beating a world champion, although it handily beat many
other chess programs. Even today, a leading program such
as Mindscape's Chessmaster 5000 evaluates only 15,000 to
20,000 moves per second.
The table "Deep Blue's Brute Force" shows how the
program's speed has improved since 1985. Boosted by
ever-faster microprocessors and increasing numbers of
custom chips, Deep Blue's ability to evaluate board positions
has soared by a factor of 4000. Yet even by 1996, when
Deep Blue was running on an IBM supercomputer
augmented by 256 custom chips, its ability to evaluate 100
million moves per second -- a 33 million to 1 advantage --
was not enough to defeat Kasparov in their first match.
It was after this loss that IBM made two crucial changes to
the software and the hardware. On the software side, IBM
made it possible to modify Deep Blue between games by
tweaking its move-evaluation functions. All good chess
programs are capable of making some adaptations on the fly,
during a game, to adjust for changing conditions. For
example, the material value of a bishop is normally three
points, which helps the program calculate whether an
exchange with an opponent's piece is worthwhile or not. But
in the later phases of a game, possessing both bishops is so
useful that a good chess program will increase that weighting
to reflect their greater relative value. Deep Blue was always
capable of making those kinds of judgments autonomously,
but last year's version didn't allow the programmers to
manually modify the program's material and board-position
weightings between games in order to adapt it to different
playing styles.
To guide those software modifications, IBM added a
full-time grand master to the Deep Blue team (Joel
Benjamin) and eventually engaged three additional grand
masters (Miguel Illescas, John Fedorovich, and Nick De
Firmian). IBM also expanded Deep Blue's database of
historic grand master games (it now contains 100 years'
worth, including all of Kasparov's games) and made other
changes as well.
But as much as IBM improved the software, the Deep Blue
team went to even greater lengths to make the program run
faster. What the team members needed was more
computational power, and they got it by turning an
off-the-shelf supercomputer into the near-equivalent of a
dedicated chess machine.
Transistor Deluge
The 1997 version of Deep Blue runs on an IBM RS/6000SP
supercomputer with 32 parallel processors. Each processor
is an IBM Power2 Super Chip (P2SC), the most complex
microprocessor ever made. A single P2SC integrates eight
older Power2 chips into a single die. Each die contains 15
million transistors (twice as many as Intel's Pentium II),
including 160 KB of on-board cache.
This phenomenal chip can execute eight instructions and
retire six instructions simultaneously. (A Pentium II can retire
only three.) Yet it runs at the relatively poky clock speed of
135 MHz because it relies on parallel instruction handling
instead of blinding clock cycles.
Oddly, though, the P2SC wasn't the best choice for this
application. As seen in the table "Comparing High-End
CPUs", the P2SC is highly optimized for floating-point (FP)
math. It scores a remarkable 17.3 on the SPECfp95
benchmark test, easily smoking Intel's 300-MHz Pentium II.
But it scores a lackluster 6.5 on the SPECint95 integer
benchmark. That's only about half the integer performance of
a 300-MHz Pentium II and about the same as a regular
Pentium-200.
Clearly, IBM designed the P2SC for scientific and
engineering applications, FP-intensive tasks at which it
excels. But chess is not FP-intensive. A chess program
spends virtually all its time performing integer operations and
evaluating Boolean conditions ("Will this move put my king in
check?"). At the CPU level, Deep Blue would actually run
better on the garden-variety microprocessors found in
high-end desktop PCs.
Hsu told BYTE that his team chose the RS/6000SP because
it was the best available IBM system for the job, even
though its P2SC processors don't have the best integer
performance. Although the P2SC lags in raw integer
horsepower, the RS/6000SP largely makes up for it by
uniting 32 of the processors in a parallel system architecture
with high-speed, low-latency connections.
More significantly, the Deep Blue computer is no longer an
off-the-shelf RS/6000SP. It's a unique machine designed for
the sole purpose of running one program as fast as possible.
Last year's version had 256 custom ASICs that assisted the
CPUs by encoding the most critical evaluation functions and
move-generation routines. This year's machine has 512
ASICs.
Hsu designed all the ASICs, which are essentially identical
except for varying amounts of ROM and RAM. Each chip is
a 0.6-micron CMOS device that contains 1.3 million
transistors. That means Deep Blue is running on a system
with more than 1.1 billion transistors in its 32 processors and
512 coprocessors. And that doesn't count the millions of
additional transistors in its auxiliary logic or the billions of
transistors in main memory.
Those 512 ASICs are solely for playing chess. They execute
the innermost loops of Deep Blue's code. Each CPU node
connects to 16 ASICs, and each ASIC can evaluate 2
million to 3 million moves per second. Together, they
off-load about two-thirds of the grunt work from the CPUs.
So the RS/6000SP that runs Deep Blue is very much a
dedicated game machine -- as dedicated to its purpose as a
Fidelity computer chessboard.
Speed Kills
By switching to the P2SC and doubling the number of
custom chips, IBM effectively doubled the number of moves
Deep Blue can evaluate in a given period. The program can
now analyze as many as 200 million moves per second, or
36 billion moves in 3 minutes. To consider the same number
of moves, Kasparov would have to think 24 hours a day for
nearly four centuries.
This matters because chess is a game of virtually infinite
possibilities. Chess perfectly illustrates the law of unintended
consequences: One move can start a ripple that quickly
cascades into a flood of unforeseen outcomes. Anticipating
the results of a move is critical to winning. The best players
are those who can see several moves or "plies" ahead.
During a match, Deep Blue typically searches a stunning 30
plies deep when evaluating the outcomes of possible moves.
According to Hsu, it can search 75 plies deep when not
bound by a game clock. By comparison, a program such as
Chessmaster 5000 searches 11 or 12 plies deep during a
tournament.
That's why it's hard to escape the conclusion that brute force
-- beating the clock, not the opponent -- was the
overwhelming factor in Deep Blue's victory over Kasparov.
It's true that IBM improved the code and tweaked the
algorithms between games. It's also true that Kasparov
wasn't able to study Deep Blue's previous games and,
according to observers, wasn't playing at the top of his form.
But ultimately it was IBM's doubling of Deep Blue's
execution speed that made the difference.
Like all computer programs, Deep Blue merely carries out
the instructions of its creators. IBM's team of engineers,
programmers, and world-class grand masters could almost
certainly defeat Kasparov if they had the same extravagant
advantage in game time (380 years per move) that Deep
Blue effectively enjoys. The heavily modified RS/6000SP
gave them that time.
Hsu doesn't argue that Deep Blue is artificially intelligent.
Nor does he like to characterize the famous match as Man
versus Machine. "It's not about intelligence," he says. "It's
about making tools that allow us to do things we couldn't do
before."
Of course, defeating the world chess champion isn't
something new. It's been done numerous times before -- by
talented humans. So maybe the most important thing Deep
Blue accomplished is that it allowed a group of less talented
chess players to outperform a greater talent, if only by proxy.
If computers can enable people to perform the same kinds of
feats in other endeavors, maybe it doesn't matter how the
software works.
Deep Blue's Brute Force
Deep Blue's Brute Force
Year
Board Positions per Second
1985
50,000
1987
500,000
1988
720,000
1989
2 million
1991
6 to 7 million
1996
100 million
1997
200 million
Comparing High-End CPUs
IBM P2SC
Intel
Pentium II
Human
Brain
Clock speed
135 MHz
300 MHz
1 KHz
SPECint95
6.5
11.6
N/A
SPECfp95
17.3
7.2
N/A
Instructions per
cycle
6
3
Many
L1 cache
(instruction/data)
128 KB/32
KB
16 KB/16
KB
N/A
Memory bus width
256 bits
64 bits
Unknown
Circuit complexity
15 million
transistors
7.5 million
transistors
50 billion
neurons
Fabrication
process
0.27-micron
CMOS
0.35-micron
CMOS
Cellular
mitosis
Die size
335 sq mm
203 sq mm
1348 cubic
cm
Power
consumption
30 watts
43 watts
20% of
metabolism
Introduction date
October
1996
May 1997
2-3 million
BC
Price (Q2 1997)
N/A
$1981
Priceless
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.