Published on KurzweilAI.net October 19, 2002

In The Age of Intelligent Machines (MIT Press, 1990), which I wrote in 1986-1989, I predicted that a computer would defeat the human world chess champion by the end of the 1990s. I also noted that computers were gaining about 45 points per year in their chess ratings whereas the best human playing was essentially fixed, which projected the cross-over point at 1998. Indeed, Deep Blue did defeat Gary Kasparov in a highly publicized tournament in 1997.

Now with yesterday’s final game, we have the current reigning computer program, Deep Fritz, able only to achieve a 4-4 tournament tie with world chess champion Vladimir Kramnik. It has been five years since Deep Blue’s victory, so what are we to make of this situation? Should we conclude that:

• Humans are getting smarter, or at least better at chess?
• Computers are getting worse at chess?

And if we were to accept the latter, should we conclude that:

• The much publicized improvement in computer speed over the past five years was not all it was cracked up to be? Or,
• Computer software is getting worse, at least in chess?

The specialized-hardware advantage

None of the above conclusions are warranted. To gain some insight into these questions, we need to examine a few essentials beneath the surface of the headlines. When I wrote my predictions of computer chess in the late 1980s, Carnegie Mellon University was embarked on a program to develop specialized chips for conducting the "minimax" algorithm (the standard game-playing method that relies on building trees of move-countermove sequences, and then evaluating the "terminal leaf" positions of each branch of the tree) specifically for chess moves.

Based on this specialized hardware, their 1988 chess machine HiTech was able to analyze 175,000 board positions per second and achieved a chess rating of 2,359, only about 440 points below the human world champion.

A year later in 1989, CMU’s "Deep Thought" increased this capacity to 1 million board positions per second and achieved a chess rating of 2,400. IBM eventually took over the project and renamed it "Deep Blue," but kept the basic CMU architecture. The version of Deep Blue that defeated Gary Kasparov in 1997 had 256 special purpose chess processors working in parallel, which analyzed 200 million board positions per second.

An important point to note here was the use of specialized hardware to accelerate the specific calculations needed to generate the minimax algorithm for chess moves. It is well known to computer systems designers that specialized hardware generally can implement a specific algorithm at least 100 times faster than programming the same algorithm as conventional software on a general-purpose computer. ASICs (Application-Specific Integrated Circuits) require significant development efforts and costs, but for critical calculations that are needed on a repetitive basis (for example, decoding MP3 files or rendering graphics primitives for video games), this expenditure can be well worth the investment.

Deep Blue vs. Deep Fritz

Prior to the time when computers could defeat the best human players, there was a great deal of focus on this milestone, so there was support for investing in special-purpose chess circuits. Despite some level of controversy regarding the rules and procedures of the Deep Blue-Kasparov match, the level of interest in computer chess waned considerably after 1997. After all, the goal had been achieved, and there was little point in beating a dead horse. IBM cancelled work on the project, and there has been no work on specialized chess chips since that time.

Computer hardware has nonetheless continued its exponential increase in speed. Personal computer speeds have doubled every year since 1997. Thus the general-purpose Pentium processors used by Deep Fritz are about 32 times faster than personal computer processors back in 1997. Deep Fritz uses a network of only eight personal computers, so the hardware is equivalent to 256 1997-class personal computers.

Compare that to Deep Blue, which used 256 specialized chess processors, each of which were about 100 times faster than 1997 personal computers (of course, only for computing chess minimax). So Deep Blue was 25,600 times faster than a 1997-class personal computer for computing chess moves, and 100 times faster than Deep Fritz. This analysis is confirmed by the reported speeds of the two systems: Deep Blue can analyze 200 million board positions per second compared to only about 2.5 million for Deep Fritz.

Thus the primary problem with Deep Fritz is that it is much slower than Deep Blue. However, the reason for this is the use of specialized hardware in Deep Blue, and the lack of it in Deep Fritz. This reflects the relatively low priority we’ve given to chess machines since 1997. The focus of research in the various domains spun out of artificial intelligence has been placed instead on problems of greater consequence, such as guiding airplanes, missiles, and factory robots, understanding natural language, diagnosing electrocardiograms and blood cell images, detecting credit card fraud, and a myriad of other successful "narrow" AI applications.

Significant software gains

So what can we say about the software in Deep Fritz? Although chess machines are usually referred to as examples of brute-force calculation, there is one important aspect of these systems that does require qualitative judgment. The combinatorial explosion of possible move-countermove sequences is rather formidable.

In The Age of Intelligent Machines, I estimated that it would take about 40 billion years to make one move if we failed to prune the move-countermove tree and attempted to make a "perfect" move in a typical game (assuming about 30 moves in a typical game and about eight possible moves per play, we have 8³⁰ possible move sequences; analyzing one billion of these per second would take 10¹⁸ seconds or 40 billion years). I noted that this would not be regulation play, so a practical system needs to continually prune away unpromising lines of play. This requires insight and is essentially a pattern-recognition judgment.

Humans, even world class chess masters, perform the minimax algorithm extremely slowly, generally performing less than one move-countermove analysis per second. So how is it that a chess master can compete at all with computer systems that do this millions of times faster? The answer is that we possess formidable powers of pattern recognition. Pattern recognition incidentally is my principal area of technical interest and expertise, and is, in my view, the primary basis of human intelligence. Thus we perform the task of pruning the tree with great insight.

After the Deep Blue-Kasparov match, I suggested to Murray Campbell, head of IBM’s Deep Blue team, that they replace the somewhat ad hoc set of rules they used for this pruning judgment task, and replace it with a well- designed neural net. All of the master games of this century are available on line, so it would be possible to train these neural nets on a considerable corpus of expert decisions.

This approach would combine the natural advantage of machines in terms of computational speed with at least a modest step towards more sophisticated pattern recognition. Campbell liked the idea and we were getting set to convene an advisory group to flesh out the idea when IBM cancelled the project.

It is precisely in this area of applying pattern recognition to the crucial pruning decision that Deep Fritz has improved considerably over Deep Blue. Despite Deep Fritz having available only about 1.3% as much brute force computation, it plays chess at about the same level because of its superior pattern-recognition-based pruning algorithm.

So chess software has made significant gains. Deep Fritz has only slightly more computation available than CMU’s Deep Thought, yet is rated almost 400 points higher.

Are human chess players doomed?

Another prediction I made in The Age of Intelligent Machines was that once computers did perform as well or better as humans in chess, we would either think more of computer intelligence, or less of human intelligence, or less of chess, and that if history is a guide, we would think less of chess. Indeed, that is what happened. Right after Deep Blue’s victory, we heard a lot about how chess is really just a simple game of calculating combinations, and that the computer victory just demonstrated that it was a better calculator.

The reality is slightly more complex. The ability of humans to perform well in chess is clearly not due to our calculating prowess, which we are in fact rather poor at. We use instead a quintessentially human form of judgment. For this type of qualitative judgment, Deep Fritz represents genuine progress over earlier systems.

Incidentally, humans have made no progress in the last five years, with the top human scores remaining just below 2,800. Kasparov is rated at 2,795 and Kramnik at 2,794.

Where we go from here? Now that computer chess is relying on software running on ordinary personal computers, they will continue to benefit from the ongoing acceleration of computer power. In six years, a program like Deep Fritz will again achieve the ability to analyze 200 million board positions per second that was provided by Deep Blue’s specialized hardware. With the opportunity to harvest computation on the Internet, we will be able to achieve this potential several years sooner (Internet harvesting of computers will require more ubiquitous broadband communication, but that’s coming too).

With these inevitable speed increases, as well as ongoing improvements in pattern recognition, computer chess ratings will continue to edge higher. Deep Fritz-like chess programs running on ordinary personal computers will routinely defeat all humans later in this decade. Then we’ll really lose interest in chess.