Sizing up Deep Blue

Deep Blue was the brainchild of Feng-Hsiung Hsu who began researching computer chess at Carnegie Mellon University where he received his Ph.D. in Computer Science in 1989. Chess had been viewed as a fundamental challenge in the field of Artificial Intelligence. Hsu's idea was to obtain orders-of-magnitude improvements in performance by parallelizing the processing of chess positions.

In addition to parallel algorithms, implementing Hsu's idea required close integration of software algorithms and hardware circuits.

By beating the World Champion in a six-game match in 1997, it was finally proved that a brute force search of chess moves is superior to the most sophisticated human conceptual understanding of the game and superior to the ability of the most skilled humans to calculate chess moves.

The meaning of these results continues to be debated today because searching through all possible moves up to 8 moves ahead is definitely not how humans play the game. In his book Deep Blue: Building the Computer that Defeated the World Chess Champion, Hsu equates Deep Blue to any other tool devised by humans that can perform a specific task better than a human. Deep Blue did not possess an intellect or consciousness and was literally just a machine. What is more important, according to Hsu, is that the creation of Deep Blue is a human accomplishment.

In the past, building a personal computer equivalent to Deep Blue was not a realistic goal. IBM had spent millions on Deep Blue (the cost of the Deep Blue project from 1985 to 1997 is estimated to have been over $100 million), which was a massively parallel RS/6000 SP based computer with 32 processors that could evaluate 200 million chess positions per second.

Setting aside the multi-million dollar price tag, Deep Blue consisted of a pair of 6-foot, 5-inch black towers weighing 1.4 tons. Deep Blue's processors, designated "P2SC", integrated eight older Power2 chips on a single die with a total of 15 million transistors. Thus in terms of processor chips alone Deep Blue contained 480 million transistors; but the Deep Blue team did not stop there. In 1997 Deep Blue also contained 512 Application Specific Integrated Circuits (ASICs), each with 1.3 million transistors for an additional 666 million transistors resulting in a grand total of 1.15 billion transistors.

Because there are an estimated 10¹²⁰ possible positions in a chess game, playing chess well from a computing standpoint depends on how many positions can be compared within a time limit, such as in a chess tournament time control of 40 moves in 2 hours. Computing speed and brute-force calculations are the only way computers can challenge human understanding of the game: Machines don't understand the game in terms of human ideas, but they can calculate good moves. Table 1 shows how Deep Blue's calculations evolved between 1985 and 1997.

Year	Positions per Second
1985	50,000
1987	500,000
1988	20,000
1989	2,000,000
1991	7,000,000
1996	100,000,000
1997	200,000,000

If Deep Blue's computing power is compared with its chess rating, assuming Deep Blue was a chess master (rating 2200) in 1985 and equal to the World Champion in 1997 (chess rating 2800+), we can see a dramatic acceleration of the number of chess positions per second necessary to achieve a significant gain in chess rating. On average, the number of positions per second evaluated by Deep Blue increased by a factor of 2.2 times the number of positions per second every year, and an average of two years passed for every 100 point chess gain in Deep Blue's rating.

As a result, if Gary Kasparov's chess rating had been 2900, rather than 2820, it would have taken IBM at least another two years to develop a computer that could beat him.

What is interesting, however, is that it would have required calculating nearly 1 billion positions per second (969,289,665) to reach the chess rating of 2900 (see Table 2).

This is not surprising, given that the number of possible chess positions expands exponentially in a tree of possible positions. Considering that, Deep Blue ultimately represents a brute force approach to the problem of making computers play chess. Calculating all possible moves for 10 moves, for example, involves roughly 10 trillion possible positions. It's no wonder that IBM denied Kasparov a rematch because if Deep Blue had lost IBM would have to have invested substantially more money to win the next match.

Tags: chess, world champion, deep blue, kasparov

Project Deep Blitz: Master-Level Chess on a PC--ExtremeTech Feature