| 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
 Comparing High-End CPUs
 The Blue Team
The humans behind Deep Blue (L to R): Joe Hoane, Joel Benjamin, Jerry Brody, F.H. Hsu, C.J. Tan, and Murray Campbell. Deep in Thought Kasparov's three moves per second vs. Deep
Blue's 200 million.
Tom R. Halfhill is a BYTE senior editor based in San Mateo, CA. You can reach him at thalfhill@bix.com. Copyright 1994-1998 BYTE |