Chess and artificial intelligence

Master search heuristics

The ability of a machine to play chess well has taken on symbolic meaning since the first precomputer devices more than a century ago. In 1890 a Spanish scientist, Leonardo Torres y Quevado, introduced an electromagnetic device—composed of wire, switch, and circuit—that was capable of checkmating a human opponent in a simple endgame, king and rook versus king. The machine did not always play the best moves and sometimes took 50 moves to perform a task that an average human player could complete in fewer than 20. But it could recognize illegal moves and always delivered eventual checkmate. Torres y Quevado acknowledged that the apparatus had no practical purpose. As a scientific toy, however, it gained attention for his belief in the capability of machines to be programmed to follow certain rules.

No significant progress in this area was made until the development of the electronic digital machine after World War II. About 1947 Alan Turing of the University of Manchester, England, developed the first simple program capable of analyzing one ply (one side’s move) ahead. Four years later a Manchester colleague, D.G. Prinz, wrote a program capable of solving mate-in-two-move problems but not actually playing chess.

A breakthrough came in 1948, when the research scientist Claude Shannon of Bell Telephone Laboratories in Murray Hill, New Jersey, U.S., presented a paper that influenced all future programmers. Shannon, like Torres y Quevada and Turing, stressed that progress in developing a chess-playing program would have a wider application and could lead, he said, to machines that could translate from language to language or make strategic military decisions.

Shannon appreciated that a computer conducting an entire game would have to make decisions using incomplete information because it could not examine all the positions leading to checkmate, which might lie 40 or 50 moves ahead. Therefore, it would have to select moves that were good, not merely legal, by evaluating future positions that were not checkmates. Shannon’s paper set down criteria for evaluating each position a program would consider.

This evaluation function is crucial because even a rudimentary program would have to determine the relative differences between thousands of different positions. In a typical position White may have 30 legal moves, and to each of those moves Black may have 30 possible replies. This means that a machine considering White’s best move may have to examine 30 × 30, or 900, positions resulting from Black’s reply, a two-ply search. A three-ply search—an initial move by White, a Black reply, and a White response to that—would mean 30 × 30 × 30, or 27,000, different final positions to be considered. (It has been estimated that humans examine only about 50 positions before choosing a move.)

Turing’s evaluation function was dominated by determining which side had more pieces in various future positions. But Shannon suggested that each position could be weighed using positional criteria, including the condition of pawns and their control of the centre squares, the mobility of the other pieces, and specific cases of well-placed pieces, such as a rook on an open (pawnless) file or on the seventh rank. Other criteria were used by later programmers to refine and improve the evaluation function. All criteria had to be quantified. For example, a human master can quickly evaluate the mobility of bishops or the relative safety of the king. Early programs performed the same evaluation by counting the number of legal bishop moves or the squares under control around a player’s king.

Computer chess

Computers began to compete against humans in the late 1960s. In February 1967 MacHack VI, a program written by Richard Greenblatt, an MIT undergraduate, drew one game and lost four in a U.S. Chess Federation tournament. Its results improved markedly, from a performance equivalent to a USCF rating of 1243 to reach 1640 by April 1967, about the average for a USCF member. The first American computer championship was held in New York City in 1970 and was won by Chess 3.0, a program devised by a team of Northwestern University researchers that dominated computer chess in the 1970s.

Technical advances accelerated progress in computer chess during the 1970s and ’80s. Sharp increases in computing power enabled computers to “see” much further. Computers of the 1960s could evaluate positions no more than two moves ahead, but authorities estimated that each additional half-move of search would increase a program’s performance level by 250 rating points. This was borne out by a steady improvement by the best programs until Deep Thought played above the 2700 level in 1988. When Deep Blue, its successor, was introduced in 1996, it saw as far as six moves ahead. (Gary Kasparov said he normally looks only three to five moves ahead, adding that for humans more are not needed.)

Also helping computer progress was the availability of microprocessors in the late 1970s. This allowed programmers unattached to universities to develop commercial microcomputers that by the 1990s were nearly as strong as programs running on mainframes. By the late 1980s the strongest machines were capable of beating more than 90 percent of the world’s serious players. In 1988 a computer, HiTech, developed at Carnegie Mellon University, defeated a grandmaster, Arnold Denker, in a short match. In the same year another Carnegie Mellon program, Deep Thought, defeated a top-notch grandmaster, Bent Larsen, in a tournament game.

HiTech used 64 computer chips, one for each square on the board, and was capable of considering up to 175,000 positions per second. Feng-Hsiung Hsu, a Carnegie Mellon student, improved on HiTech with a custom-designed chip. The result, Chiptest, won the North American Computer Championship in 1987 and evolved into Deep Thought, a program powerful enough to consider 700,000 positions a second. Although its evaluation skills were not as well developed as HiTech’s—and far below that of a human grandmaster—Deep Thought was sponsored by International Business Machines Corporation (IBM) in an effort to defeat the world’s best player by the mid-1990s in a traditional time limit.

At faster speeds even personal computers were able to defeat the world’s best humans by 1994. In that year a Fritz 3 program, examining 100,000 positions per second, tied for first place with Kasparov, ahead of 16 other grandmasters, at a five-minute tournament in Munich, Germany. Later in the year Kasparov was eliminated from a game/25 tournament in London after losing a two-game match against Genius running on a Pentium personal computer.

In 1991 Deep Thought’s team said the program, renamed Deep Blue, would soon be playing at the equivalent of a 3000 rating (compared with Kasparov’s 2800), but this proved excessively optimistic. The main improvement was in the computer running the chess program. IBM developed, and used chess to test, a sophisticated new multiprocessing system (later used at the 1996 Olympic Games in Atlanta, Georgia, U.S., to predict the weather) that employed 32 microprocessors, each with six programmable chips designed specifically for chess. Deep Thought, by comparison, had one microprocessor and no extra chips. The new hardware enabled Deep Blue to consider as many as 50 billion positions in three minutes, a rate that was about a thousand times faster than Deep Thought’s.

Deep Blue made its debut in a six-game match with PCA champion Kasparov in February 1996. The $500,000 prize fund and IBM’s live game coverage at their World Wide Web site attracted worldwide media attention. The Kasparov–Deep Blue match in Philadelphia was the first time a world champion had played a program at a slow (40 moves in two hours) time format. Deep Blue won the first game, but Kasparov modified his style and turned the later games into strategic, rather than tactical, battles in which evaluation was more important than calculation. He won three and drew two of the remaining games to win the match 4–2.

In a six-game rematch held May 3–11, 1997, in New York City, an upgraded Deep Blue was able to consider an average of 200 million positions per second, twice its previous speed. Its algorithm for considering positions was also improved with advice from human grandmasters.

By adopting a new set of conservative openings, Kasparov forced Deep Blue out of much of its prematch preparation. After resigning the second game, in a position later found to be drawable, Kasparov said he “never recovered” psychologically. With the match tied at one win, one loss, and three draws, Deep Blue won the decisive final game in 19 moves.

Computer extension of chess theory

Computers have played a role in extending the knowledge of chess. In 1986 Kenneth Thompson of AT&T Bell Laboratories reported a series of discoveries in basic endgames. By working backward from positions of checkmate, Thompson was able to build up an enormous number of variations showing every possible way of reaching the final ones. This has been possible with only the most elementary endgames, with no more than five pieces on the board. Thompson’s research proved that certain conclusions that had remained unchallenged in endgame books for decades were untrue. For example, with best play on both sides, a king and queen can defeat a king and two bishops in 92.1 percent of the initial starting positions; this endgame had been regarded as a hopeless drawn situation. Also, a king and two bishops can defeat a king and lone knight in 91.8 percent of situations—despite human analysis that concluded the position was drawn. Thompson’s research of some five-piece endgames required considering more than 121 million positions.

Because of their ability to store information, computers had become invaluable to professional players by the 1990s, particularly in the analysis of adjourned games. However, computers have severe limits. In the 1995 PCA championship, Kasparov won the 10th game with a heavily analyzed opening based on the sacrifice of a rook. According to his aides, the prepared idea was tested on a computer beforehand, and the program evaluated the variation as being in the opponent’s favour until it had reached the end of Kasparov’s lengthy analysis.

The availability of top-notch microcomputers poses a major problem for postal chess. A principal difference between over-the-board chess and all forms of correspondence chess is that in the latter players are permitted to analyze a position by moving the pieces and by consulting reference books. By the 1990s most serious postal players used a computer database containing thousands of games categorized by opening moves. However, if the use of computers is extended to finding the best moves in the middlegame or endgame, postal chess becomes computer chess. The International Correspondence Chess Federation said in 1993 that “the existence of chess computers is a reality and for correspondence chess the use of chess computers cannot be controlled.”