How Kasparov beat a Genius

The world's best chess player has avenged his defeat by a computer worth less than pounds 2,000. Helen Johnstone reports

Last weekend the world chess champion, Gary Kasparov, wreaked his revenge on the opponent who had inflicted possibly the most humiliating defeat of his career.

In a two-game match in Cologne, he swept away the doubts that have hung over his ability since he was knocked out of the Intel Speed Chess Grand Prix in London last September, not by a human rival, but by a computer. A PC worth less than pounds 2,000 eliminated him and left him hitting his head in anguish.

The match in Cologne was Kasparov's opportunity to level the score. Stepping out of the soundproof glass booth after winning the first game and drawing the second, Kasparov said he was "relieved" rather than pleased with the victory. Several times during the first game he had looked dangerously close to losing, and despite being in a strong position for much of the second, Kasparov was left with just four minutes on the clock when the game ended in a draw. "I could have lost," he admitted.

It is 45 years since the first theoretical paper on a chess-playing computer appeared, though it was not until much later that programs of any power were developed. During the Sixties two rival approaches were developed. Some programmers relied on brute force, telling the computer to calculate as many moves as possible. Others followed an artificial intelligence route, hoping to find a way to emulate the reasoning of human players. By using vast numbers of documented games, they hoped to discover the rules on which the players based their moves.

To the embarrassment of the AI experts, their systems were soon being knocked out of computer chess tournaments by machines using brute processing power. "Putting strategic principles into a computer is much more difficult than expected," says Peter Millican, a senior lecturer in AI and Philosophy at Leeds University and an international master in correspondence chess. "Doing that wasn't as effective as making things go really fast."

By September last year, enough power was available in an Olivetti PC with a 90MHz Pentium processor, running the pounds 89 Chess Genius 2 software, to beat the world's number one chess player. A processor that could analyse 100,000 positions a second and software that had been developed and updated for more than a decade proved to be a tougher match than Kasparov had expected.

Kasparov is angered by the portrayal of that game as a victory for machine over man. "It's not a human being playing a machine. It's a human being playing a machine prepared by other human beings."

The human behind the Chess Genius software is a British programmer, Richard Lang. He started writing the software as a hobby in 1981, but after winning the world computer chess championships a few years later, began on its development full time.

Lang had spent the months in between the Intel Speed Chess Grand Prix and the match in Cologne ironing out some of the flaws in the software and making the system more efficient. The Genius 3 program had even been in "training" for the match. "I play it against other computers, automatically, then try to work out why it has lost," he says. "But you can't prepare against Kasparov."

Kasparov also trained for the match, putting in about 36 hours of play against the Genius software. That meant adapting his style to suit the play of a computer, rather than a human. The British Grand Master, Danny King, says the computer plays in a way no human would, often missing moves that are obvious to an experienced player. "A computer can analyse 100,000 positions a second. What a fantastic achievement. But does this help you to play good chess?" In the same situation, the human might analyse just one position: the right one.

The software chooses its moves based on factors such as its ability to gain pieces, to occupy important sectors of the board or to create a good defensive position. As it analyses each move, the computer allocates it a "score" based on such criteria, until one move stands out as the best or it has spent long enough searching. A randomness in the final choice ensures that it will never play exactly the same game twice. It can also be adjusted according to the strength of the opponent: when Chess Genius meets someone, it will play cautiously, because tiny slips will be ruthlessly exploited.

As chess players begin to understand the way the computers work, they are starting to adapt their game. "The worst thing about them is their materialism," says King. "Humans are beginning to accommodate that and bring it into their play."

It was this weakness that Kasparov exploited in the first of the two games in Cologne. Offering the computer the chance to take two pawns, Kasparov lured the Pentium into a trap that destroyed its position on the board and led ultimately to its defeat.

In the second game, the Pentium played a strong, if unusual defence, which experts identified as a strategy last used in the Twenties. Although it kept Kasparov to a draw, the defensive play allowed him to coast to an overall win.

The computer is also failing to make a mark in matches in which players have a long time to analyse their moves. With 25 minutes for each, as in London and Cologne, the match is fairly even. Beyond 25 minutes, humans seem to have an advantage. Not only are humans less likely to be rushed into mistakes, computers hit an effect called the "combination explosion".

As the computer analyses its potential moves, it looks perhaps three or four moves into the future, calculating all the likely responses and follow-up moves. But each time it tries to look a further move into the game, the number of possibilities it needs to examine is multiplied perhaps 30 to 40 times.

In correspondence chess, where players can spend days working on each move before sending the decision to their opponent by postcard, Peter Millican says he would never trust a computer to come up with the best move. Even if he left his Pentium-based PC to work on the problem over-night, it would not be capable of looking deep enough into the match. "The kind of thinking you have to go in for is much more long term. It may only be consummated 20 moves down the line."

But as each new generation of processor doubles the power of the previous one, it may not be long before the computer becomes unbeatable. "I think it's three years away," says Intel's European marketing director, Mike Couzens.

"I've never had any doubt that computers would beat the best humans," says Don Beal, a lecturer at Queen Mary and Westfield College in London and an organiser of the International Computer Chess Association. "It's surprising that humans have lasted so long."

Celebrating after the Cologne match, Kasparov said he did not think the computer would consistently outplay humans in his chess career. "We [humans] haven't reached our potential," he said. "It is important for us to take [computer chess] seriously, but this should be a separate event. You need to be isolated for a while from human chess."