Chess has always fascinated programmers and cognitive scientists. Over many years, computer chess was the yardstick used to measure the capabilities of computers when compared to humans. Eventually, chess proved to be a more difficult problem than originally thought, but even so on May 11 1997 a computer defeated the reigning world champion, Gary Kasparov, in a dramatic chess tournament.

The first chess program was written by the German inventor Konrad Zuse as just an example of the expressive power of his "Plankalkül", a high-level programming language that he developed from 1942 to 1945. The program was never implemented and the code was not published until 1972. Therefore, the privilege of being considered the "father" of computer chess is usually assigned to the American mathematician Claude Shannon, who in two articles published in 1950 described how to program a computer to play the game. Shannon distinguished between a Type A strategy, in which all combinations of moves (the own and

the opponent's) are examined up to a maximum depth level, and a type B strategy in which only promising branches of the tree of possibilities are further expanded. Early computer chess programs applied a type A strategy, although in 1951 Alan Turing, the British computer pioneer, specified a program to play chess that tried to follow preferably those branches in which a piece is captured.

Playing chess with a computer requires using an evaluation function which can discriminate between a good and a bad move. The evaluation method used by Zuse, for example, consisted in assigning a constant weight to every piece on the board and adding all numbers together. This is a rather poor evaluation function, since positional advantages are not taken into account and any two given moves which do not lead to material gain have the same value, although one of them could be excellent and the other terrible. Since no evaluation function is known which can guarantee a win in chess, "heuristic" methods are used which give certain weight to certain features of the current position ( dominance of the center, mobility of the queen, etc.) and summarize them in a single number.

All early computer chess programs used brute force, that is, extensive search in the tree of moves guided by a heuristic evaluation function. The method described by Shannon in 1950 is known today as the "minimax algorithm". It consists of selecting the best possible move, under the assumption that the adversary will also answer with his best move. The player moving a piece tries to maximize his gain according to the evaluation function, the adversary tries to minimize it. The interplay of both intentions yields the "minimax" solution, already described by John von Neumann in his study of the theory of games.

The first fully-fledged chess program to actually run on a computer was written by Alex Bernstein and others for an IBM 704 in 1957. It inspected all future four plies (a move by black or white is called a ply) in around 8 minutes and could win against amateurs. A smaller program that played on a 6 by 6 board had been implemented one year before on the MANIAC I, a computer built at Los Alamos National Laboratories. But the first chess program that actually played in a real tournament was the legendary MacHack VI, written by Richard Greenblatt for a PDP-6 at MIT. Later, it was available on all PDP-10 computers, a machine very popular at universities and research centers.

Although Herbert Simon and Allen Newell predicted in 1956 that a computer program would become world champion in only ten more years, several decades passed before a computer could win a match against the world champion. The reason seems to be that good human players are capable of identifying patterns in the chess board that led them to inspect only a handful of possible moves. Whereas computer chess programs can play decently because they examine thousands or millions of moves per second, a human player applies a higher-level strategy. Good moves "pop up" in the mind of a great master, the way we recognize a human face in the crowd. The process of recognition itself is not open to introspection. We can do it, but we don't know why. To their credit, Simon and Newell refined the minimax strategy by applying "alfa-beta pruning", a technique that identifies unfavorable branches in the move tree and removes them early.

In 1989 Deep Thought, a parallel chess machine built by a team led by Feng-hsiung Hsu, became the world champion in computer chess. Deep Thought achieved this result by using a large library of opening games and raw computing power. Although the machine could examine 2 million moves per second, Gary Kasparov easily defeated the program that same year. That would change the moment IBM hired the developers of Deep Thought with the medium term plan of overpowering Kasparov. The IBM machine, Deep Blue, a parallel computer with 32 processors and 256 special chips, defeated Kasparov under tournament conditions for the first time in 1996, but lost the series 4-2. Just a year later Kasparov would lose the rematch 3.5 to 2.5 in a much publicized event transmitted over the Internet. Once the world champion had been defeated, computer chess became a kind of solved problem and the artificial intelligence community moved to more challenging areas.

Shannon, Claude E., "Programming a computer for playing chess", Philosophical Magazine Vol. 41:256-275, 1950.

Zuse, Konrad, Der Plankalkül, Berichte der Gesellschaft für Mathematik und Datenverarbeitung, Nr. 63, Sankt Augustin, 1972.

Levy, David, and Monty Newborn, How Computers Play Chess, Computer Science Press New York, 1991.

Hsu, Feng-hsiung; Thomas Anantharaman; Murray Campbell; and Andreas Nowatzyk, "A grandmaster chess machine,'' Scientific American, 263:4, October 1990, 44-50.

Margarita Esponda