The Implications of Kasparov Vs. Deep Blue

This two-part Viewpoint offers some diverse perspectives on IBM Deep Blue's recent win over world chess champion Garry Kasparov. Our goal is not to analyze the games or the technology but to consider the implications of the machine's succes for chess and computer science. That's why we called on leades from both spheres. International Chess Grandmaster Yasser Seirawan is atop U.S. contender for the championship whose spirited commentary during the six-game match last May in New York illuminated the strategic thinking begind each move for a worlwide audience. ACM Turing Award winner Herb Simon and Toshinori Munakata focus on the AI lessons of the machine's improving chess abilities. Despite IBM's reluctance to publicly address Deep Blue's "knowledge" skills, these authors expect some powerful applications to be borne of Blue. Here are their stories.

In commentng on the recent chess match between Garry Kasparov and Deep Blue, IBM has avoided speaking of AI, focusing almost exclusively on its large parallel processor that examinates about 1.8 * 1010 positions in each three minutes (the average time allowed for a move). IBM promotial literature even proclaimed, "The power behind Deep Blue is an IBM RS/6000 SP system finely tuned with customized processor chips designed by IBM Research. This combination, in addition to expert knowledge, enables users to take on larger problems by analysing a greater number of possible solutions."

We have a somewhat different view of Deep Blue's prowess and its implications for computing in general and AI in particular. Grandmaster Joel Benjamin, a consultant to the Deep Blue team, and Murray Campbell, an IBM research scientist and computer-chess expert, claimed important advances during the year between matches with Kasparov in Deep Blue's chess knowledge, not merely its ability to examine more positions.

Deep Blue's branching factor at each move (or ply) avereges perhaps four or five, after allowing for various procedures, like the alpha-beta algorithm and special continuations that are selectively incorporated into the search. Hence, although the speed of Deep Blue was increased by a factor of two during the year between matches, the search capability increasedby only a fraction of a ply. Yer all grandmasters watching the match (as well as Kasparov) commented on the qualitative change in its play, especially its ability to play differently in different kinds of positions. So it is to chess knowledge, not brute-force search, we must look for most of the improvement. That knowledge appears to take three forms:

Thus there are three directions - beyond increased speed - along which Deep Blue could have improved during the yaer, and its play gave every indication that it improved in all three. Its greater strength over 1996 is much more convincingly expalined in these therms than by the modest increase in its look-ahead ability. Especially interesting is that these improvements correspond to three kinds of chess knowledge possessed by human chess players, enabling them to select good moves after relatively little search (almost certainly never more that 1000 braches, except when the "book" is followed). Deep Blue increased speed may be allocated, not to searching deeper but to computing and recognizing more sophisticated patterns, permitting more selective search.

Deep Blue's essential elements can be summarized as:

Chess aside, what does the chess match mean for the future of computers for complex, knowledgerich tasks and for the role of AI methods in performing these tasks? First, speed alone cannot solve complex problems and must be supplemented with knowledge. Moreover, if there is enough knowledge, the ability to recognize cues and thereby access knowledge associated with paricular kinds of situations will gradually replace speed and brute-force search as the main tool for building high-performance systems.

This does not mean computer power is unimportant for solving challenging problems. In the human brain, recognizing patterns in visual and auditory stimuli is perhaps the most expensive computing task performed, sometimes making parallel processing is central to dealing with complexity, methods are needed for acquiring and evaluating new patterns. Human programming cannot do the job, especially if the program has to be updated continually to incorporate new knowledge. Capabilities must be developed for learning patterns autonomously from information about the task environment. We have considerable experience building programs that learn - reaching back to the late 1950s to Arthur Samuel's pioneering checker-playing program that learned to improve its game by modifying its evaluations with experience. Today, we can learn through "neural nets," adaptive production systems, self-modifying discrimination nets, and genetic algorithms. Experience with Deep Blue suggests a high priority on incorporating such learnig capabilities, enabling the system itself to learn from published games and from its own analyses.

If we classify the tasks handled by machines as (I) simple, (II) moderately difficult, and (III) very difficult, then at the low end of level I, we have arithmetic computations, simple spelling checks, and straightforward database retrieval. From upper end of level I, through level II, we have most of the practical AI applications today, such as symbolic calculus, expert systems, robotics, and machine visions.

Chess playing against human grandmasters can be regarded as lying toward the upper end of complexity level II. Although the domain is well defined, a high level of a play cannot be attained without doing sofisticated knowledge and selective search. Although computers are still far behind people in performing in complex everyday environments, they do perform at the level of highly expert humans in domains like chess, using their superior computational power to supplement knowledge and selectivity (see Promising Applications).

What are the prospects for AI solutions to problems at level III complexity? One possibility increasingly examinated in recent years is to apply parallel computing methods. Some impressive applications of parallelism today involve speech recognision and vehicle steering.

AI has been used mainly in serial applications for two main reasons: In AI's early days, appropriate parallel machines were not generally available. We still do not understand many things about designing and programming parallel systems to perform tasks involving massive interaction with heavy demand for communication among components and with strong constraints on the order in which tasks may be performed. While most human neural processes appear to be highly parallel, processes that require conscious awareness or going through the narrow bottlenecks of short-term memory are largely serial. For example, in symbolic integration, we apply one formula at a time, checking whether it leads toward a solution before asking the next step. AI has focused primarily on tasks with a large serial component. The most notable exceptions are categorical learning tasks involving increasing numbers of statistical and neural net methods.

Promising Applications

With the prospect of combining the whole range of available AI methods, we can expect many new applications in such areas as molecular dynamics, financial risk assessment, and decision support. Other areas and problems with great promise for the near future and many with ongoing R&D efforts and even successful applications include:

Generic categories:

Application areas: