The earliest approach to solving it involved emulating the human style of play. It is now clear that this was an extraordinarily difficult way to tackle computer chess. Even though chess seems to be a simple and restricted domain, people use many different aspects of intelligence in top-level play,including calculation of possible outcomes, sophisticated pattern recognition and evaluation, and general-purpose reasoning. Significant progress in computer chess did not occur until 1973, when David Slate and Larry Atkin wrote a well-engineered brute-force chess program called Chess 4.0. Since then, almost all good chess programs have been based on their work.

The Slate/Atkin program remained the best chess-playing computer program throughout the 1970s; it gained in strength with each new, faster generation of computer hardware. It was observed in practice, and verified by experiment, that every fivefold speedup in computer hardware led to a two-hundred-point increase in the program's rating as it approached the master level. Subsequent chess-playing machines pushed the computer chess ratings higher and higher -- in large part due to faster hardware, although software was also improving rapidly. The Slate/Atkin program reached the expert level (2,000) by 1979; in 1983 Belle, a machine from AT&T Bell Labs, used specially designed chess hardware to reach the master's level (2,200); then came Cray Blitz, which ran on a Cray supercomputer, and Hitech, which dedicated a special-purpose chip to each of the sixty-four squares on a chessboard. Recognizing this trend, Ray Kurzweil predicted that a computer would beat the world champion around 1995. All these machines were finally surpassed by Deep Thought, which began playing in 1988 (see figure 5.3). Designed and programmed by a group of graduate students (myself included), Deep Thought was the first machine to defeat a grandmaster in tournament play; it was capable of searching up to seven hundred thousand chess positions per second. Deep Thought eventually led to Deep Blue, still the world's best chess-playing machine.


How Deep Blue Plays Chess

The objectives of the Deep Blue project were to develop a machine capable of playing at the level of the human world chess champion and to apply the knowledge gained in this work to solving other complex problems. To accomplish these goals, a significant increase in processing power was necessary. Today Deep Blue is capable of searching up to two hundred million chess positions per second. Its ability to search such an extraordinary number of positions prompted Kasparov to comment that "quantity had become quality." In other words, the computer is able to search so deeply into a position that it can discover difficult and profound moves. Although Deep Blue uses a variety of techniques to achieve its high level of chess play, the heart of the machine is a chess microprocessor (see figure 5.4).

Designed over a period of several years, this chip was built to search and evaluate up to two million chess positions per second. By itself, however, the chip cannot play chess. It requires the control of a general-purpose computer to make it work. Deep Blue runs on an IBM SP2 supercomputer with thirty-two separate computers (or nodes) that work in concert. For the match against Kasparov, each SP2 node controlled up to eight chess chips, while the entire SP2 system had about 220 chess chips that could be run in parallel. The old saying about too many cooks spoiling the broth is also applicable to parallel computers. A lot of processors won't do much good unless they can all be kept busy doing useful work. In fact, parallelizing a chess program efficiently has proven to be a very difficult problem. For the match with Kasparov, Deep Blue looked at an average of close to one hundred million positions per second.

Nonetheless, a purely brute-force machine would have little chance against a player like Kasparov. Although grandmasters require very little actual calculation of variations for most moves, there are typically a few key points in a game where they must calculate the possible variations very deeply. Often these calculations far surpass what brute-force search could hope to attain. To overcome this problem, Deep Blue employs a technique called selective extensions, which enables the computer to search critical positions more deeply.

One of the questions most commonly asked about a chess computer is, "How deep does it search?" In the early days of the computer chess, most programs searched all lines to roughly the same depth, and this question was relatively easy to answer. The fact that Deep Blue employs sophisticated selective searches complicates the issue considerably. When asked how deeply Deep Blue searches, one can give at least three answers; minimum depth (six moves in typical middle game positions); average depth (perhaps eight moves); and maximum depth (highly variable, but typically in the ten-to-twenty-move range).

Yet, although Deep Blue's speed and search capabilities enable it to play grandmaster-level chess, it is still lacking in general intelligence. It is clear that there are significant differences between the way HAL and Deep Blue play chess.