Playing a perfect game of chess is possible in theory. Just work out and memorize the best move for each of the 20,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible positions in a chess game. Then you've got it made.
The only drawback is that such a task would take even the fastest computer longer than the universe has existed. That's quite a while to wait for your opponent to make a first move. It's not much consolation that every subsequent move would be instantaneous.
That is one reason why computers may never play the perfect game of chess. But it's best to avoid the word "never" when discussing computers and chess. When the first computer chess program was written in 1953, it was crude and easily defeated. Even when an improved program began defeating some tournament players in the mid-1960s, a lot of people scoffed.
Now computer chess has come into its own, with the ability to defeat more than 99 percent of all players. Only masters and grandmasters are safe for now, and no one knows for how long.
The best computer programs are playing at master level or slightly below. The Mississippi state chess champion is a computer that defeated a master to win the title. That computer program is rated a provisional master, and another based in New Jersey plays even better.
In 10 years -- or 20 or 30 or longer -- a computer will be world chess champion, according to many experts. Carnegie-Mellon University in Pittsburgh has offfered a $100,000 Fredkin Prize to the programmer of the first computer that wins the world championship. The interest on the prize money is used for other prizes and competitions in computer chess.
The prospect of some microchips surpassing the best human at the chess board is daunting and controversial.
"There's no question that the Fredkin Prize will be won," said Hans Berliner, a computer scientist at Carnegie-Mellon and former world champion of correspondence chess. "It'll certainly happen in this century; my guess is about 1990."
Robert M. Hyatt, a computer instructor at the University of Southern Mississippi and programmer of the state champion, said a computer triumph over the world champion is inevitable, probably within 20 years.
"I don't see it as good or bad," he said. "I notice we still have the Kentucky Derby even after we have cars. I assume we'll always have chess."
But Edmar Mednis, an international grandmaster who lives in New York, said computers never will challenge the best human players. "I think a computer can never do what we can do," he said.
Good chess, Mednis noted, requires enormous insight into such intangibles as improved playing positions. A player's decision whether to advance a pawn or to castle or to accept a gambit may be based not on numerical calculations but on intuition about better positions. These intuitions, Mednis said, are based on some fundamental principles -- keep knights away from the edge of the board, dominate the center -- but they cannot be applied as hard-and-fast rules because the situation may dictate an exception.
Mednis said computers are superb for looking ahead several moves and avoiding some kinds of stupid errors, but he doubted that programs will ever threaten a world champion with consummate understanding of the game.
"It's damn good, really, but just because you're damn good doesn't mean you'll be world champion," he said. "Just because a person can run a mile in four minutes doesn't mean he can run it in two. The going gets tougher, and I think that is this situation, too."
A British international master, David Levy, won a famous bet he made in 1968 that a computer could not beat him within 10 years. In 1978, Levy renewed that bet for only five years, and has had no takers. Levy, who runs a computer game company, didn't make the renewal for 10 years because soon his own computer programs will be able to beat him at the game, said Levy's business partner, Kevin O'Connell.
The world champion in computer chess is Belle, programmed by Ken Thompson and Joseph H. Condon of Bell Telephone Laboratories in New Jersey. Belle relies upon what is known in the business as "brute force," the analysis of almost 30 million positions in the three minutes available for an average move. The other approach in computer chess, which has not done so well, is more selective and examines fewer positions with more sophistication.
The programs also include instantaneous responses in certain familiar positions. Belle's library has 350,000 positions memorized with automatic responses. Sometimes the computer is programmed to choose at random between two or more equally good moves, so that an opponent cannot study past games and know exactly how Belle will react to a certain position.
Even so, Belle and other computers remain fairly predictable, and a good player who studies past games will learn how to play to the computer's weaknesses and avoid its strengths. What the computers are superb at is looking ahead in unorthodox ways and finding ramifications of possible moves.
Belle's intelligence so charmed the U.S. Customs Service that agents impounded the computer in early May as it was on its way to Moscow for an exhibition. They said it could be of military use to the Soviets and did not release it for a month.
Hans Berliner, the Carnegie-Mellon researcher, said of Belle, "It has made some moves which maybe no human could have made. No human could have seen to the end of it and followed it."
For example, a king and a rook always have been considered easy prey for a king and a queen, but Belle found a good, though not perfect, defense for the king and a rook. Now Berliner is using a computer to analyze king-and-pawn end-games. "I hope that in a year we'll play this as well as anyone in the world," he said.
In an average middle game, Belle looks ahead eight half-moves, four by each player. But in unusual situations, where there are few pieces left or few possible moves, computers can look ahead much further. Cray Blitz, the Mississippi champion, once found a forced checkmate 42 half-moves away.