Science / Medicine : Beating the Computer at CHESS : Competition: Gary Kasparov proves that humans are still masters of the game. But the machines have made great strides in recent years.
Human players still rule the game of chess. World chess champion Gary Kasparov proved that last month when he easily crushed his electronic challenger, Deep Thought. But how long will human players maintain this advantage over chess-playing computers?
That such a match took place at all provides a striking demonstration of how far computer chess has advanced in recent years. Only a decade ago, an expert player could defeat any computer program in existence. Now all but the 100 or so strongest players in the world would lose to today’s best chess computers. However, Kasparov’s decisive wins in both games of his match against Deep Thought vividly demonstrate how much further researchers have yet to go in designing a champion chess machine.
Put together by a team of five graduate students at Carnegie Mellon University in Pittsburgh, Deep Thought played its first game in May, 1988. Since then, the custom-built computer has amassed a remarkable record, including several wins over players ranked as grandmasters and only a handful of losses.
Earlier this year, Deep Thought became the first machine to earn a chess rating that put it into the top category of all chess players. Last May, it won the world computer chess championship, confirming its status as the world’s best chess machine.
But the CMU team didn’t expect Deep Thought to beat Kasparov. At best, they thought the machine could do well enough to force at least one game into a draw.
The match’s real importance was the opportunity for researchers to learn from a chess master. “If you keep winning, you don’t learn,” CMU’s Thomas Anantharaman says.
Computer scientists and other researchers have been thinking about machine-based chess for a long time. In 1950, Claude E. Shannon, pioneer of information theory, explained why he thought chess is a challenge for researchers: “The problem is sharply defined, both in the allowed operations (the moves of chess) and in the ultimate goal (checkmate). It is neither so simple as to be trivial nor too difficult for satisfactory solution.”
Apart from the sheer intellectual challenge of the task of programming a computer to play chess, the game turns out to be useful for checking out new programming concepts that may eventually prove useful in other applications. In a sense, chess programs have the same role in developing machine intelligence that fruit flies, which reproduce quickly and go through many generations in a short time, have in genetic research.
Deep Thought’s performance is an apt illustration of how far an intelligent, speedy search can go toward mimicking human capabilities. All of today’s chess programs and machines are fundamentally alike in that they depend largely on a systematic, exhaustive search. A computer looks ahead from its current position along a branching tree of possibilities.
The program assigns a value to the end of each branch according to its strategic strength or weakness. These values are then compared, and the computer finally decides how to move. Deep Thought can scan nearly a million such positions per second.
But Deep Thought and other chess computers don’t play their games simply by working out every possible move and all its consequences for a given position. There are just too many possibilities for each one to be considered within the time limits that govern chess games.
Typical computer chess programs are fast enough to look ahead about four moves. Various pruning tricks shorten the search process by taking out many useless and obviously silly moves.
Another important shortcut for a program is to assume that its opponent is smart and will generally take one of the best moves available. The program need not search much beyond the point at which it identifies a particularly strong move its opponent can make. Then it can concentrate on responding to such a possible move.
Deep Thought, for instance, incorporates an innovative search procedure known as “singular extension,” which allows the machine to probe as many as 30 moves ahead along promising tracks instead of staying with a general search.
The chief weakness of a scheme relying mainly on a fast search is that the program is oblivious to problems and traps that lie beyond the reach of its search. That’s the kind of weakness that Kasparov exploited.
“The computer is too simple, too straight, too primitive,” Kasparov said before his first game. “If you know a computer well, you can anticipate its moves.”
Kasparov avoided the daring moves and slashing attacks that typify his most famous matches. Instead he deftly maneuvered Deep Thought into losing positions. Unable to search far enough ahead to gauge the effect of key moves and distracted from mounting a concerted attack, Deep Thought readily fell into the traps Kasparov set.
“Kasparov created positions that forced the computer to do the wrong things,” says CMU computer scientist and chess expert Hans Berliner, who developed Hitech, one of Deep Thought’s rivals in the computer chess field.
“This was a particularly clear demonstration of some of Deep Thought’s weaknesses,” says Murray Campbell, a member of the CMU team who is now working on a successor to Deep Thought at the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y.
Although the games against Kasparov revealed considerable shortcomings in Deep Thought’s play at the beginning of a game, they also showed the computer’s strength in making the best of a bad situation. It can stave off defeat for a long time, making the best possible moves while waiting for its opponent to commit a mistake. Unfortunately for Deep Thought, Kasparov played flawlessly.
“Eventually, the world champion will lose to a computer,” says Feng-hsiung Hsu, another member of the CMU team who is now at IBM. “The question is when.”
The answer may come with IBM’s project to build an advanced chess machine capable of evaluating a billion chess positions per second. “You can use technology to get increases in speed, and that’s an easy way to make progress,” Campbell says.
Adding chess knowledge is more difficult. The chess skills usually built into a program are generally very simple concepts that any amateur player would know, but those concepts combined with speed often create computers that play chess better than their human programmers. And programmers are trying to incorporate increasingly sophisticated chess knowledge to help computers make better decisions.
Anantharaman is looking into the possibility of designing a system that can learn from games played by expert human players. “Human beings are very good at finding things that work, but they can’t really tell you how important they are relative to each other, even though they somehow see it instinctively,” Anantharaman says. “Instead of trying to get a human expert to tell you exactly what to do, you let the program figure out for itself which strategies are good and how much weight to give them.”
On the other hand, studies show that chess experts look at only a handful of moves and deeply evaluate just a few of them. They tend to rely on an instantaneous perception of a chess position as a whole. And the human mind’s remarkable agility enables it to respond to unexpected situations. Computers don’t have this kind of global view.
Kasparov is confident that human ingenuity will provide the strategies necessary to stay a step ahead of any chess computer, perhaps by learning from the way increasingly sophisticated computers themselves play.
“I don’t think any computer will be able to beat the world’s best player before the end of this century,” he says.
