CHESS AND ARTIFICIAL INTELLIGENCE

Chess and artificial intelligence Figure 5: The Turk, a chess-playing pseudo-automaton, shown with its cabinet doors open, allowing 1/4 Machines capable of playing chess have fascinated people since the latter half of the 18th century, when the Turk, the first of the pseudo-automatons, began a triumphal exhibition tour of Europe. Like its 19th-century successor Ajeeb, the Turk was a cleverly constructed cabinet that concealed a human master. The mystery of the Turk was the subject of more than a dozen books and a widely discussed article written by Edgar Allan Poe in 1836. Several world-class players were employed to operate the pseudo-automatons, including Harry Nelson Pillsbury, who was Ajeeb during part of the 1890s, and Isidor Gunsberg and Jean Taubenhaus, who operated, by remote control, Mephisto, the last of the pseudo-automatons, before it was dismantled following World War I. See Figure 5. 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, Eng., 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, N.J., 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.