Computers Compete in Sheraton Chess Match

In today's highly technical age, it is no surprise that computers are being programmed to play chess. Last week the Third Annual U.S. Computer Chess Championship was held at the Sheraton Boston Hotel, and a crowd of 300 watched as eight computers competed for first place.

The idea of programming computers to play chess is as old as the machines themselves, and dates back to 1864 when Charles Babbage speculated on how his analytic engines could be used for the game. The idea was not researched thoroughly until 1950 by an American, Claude Shannon (although several decades earlier a machine created a great sensation by beating many excellent players, until it was discovered that the device contained a chess-playing midget inside it).

Shannon's paper outlined the basic problems involved in programming a computer to play chess, and his work has served as a guide for all subsequent efforts in this field. There are two essential components to a chess program: a "tree-generating" device, and an evaluation function. The tree-generating device determines all combinations of legal moves to a fixed depth. For example, it has been estimated that in any given position, there are approximately 35 legal moves available to the player whose turn it is to move. Thus, if a program were to do a tree-search of 4 "ply" (2 moves by each player), it would examine 35 x 35 x 35 x 35, or about 1,000,000 different possibilities of move sequences.

The evaluation function then determines which positions are good, and which are bad, and finally decides upon an appropriate move. It is up to the programmer to decide upon the criteria for good and bad positions.

Last week's chess tournament was part of the Special Events program of the Association of Computing Machinery's annual convention. The best chess programs in the country participated, as well as several last-minute entries which included Bruce Leverett, a senior at Harvard.

The human programmers assisted their computers in only one way--they typed their opponents' last moves into their own teletypes, and then relayed the response. In addition, three 20-minute time-outs were allotted each team for technical difficulties. Other than these stipulations, the normal rules for chess were in force, including the requirement that each side make 40 moves in 2 hours.

The eight teams came from all over the country. Because it is costly and impractical to move large computers, telephone hook-ups were used to connect the machines to teletypes, which were located in the tournament hall. Total phone bills for the tournament amounted to almost $2000.

The highlight of the event was a game in the final round between the defending champion from Northwestern University, and last year's runner-up, from Carnegie-Mellon. The game was exciting, not only because both programs were undefeated, but also because it amounted to a clash between two different styles. The Northwestern program, named Chess 3.5, looked ahead 4 ply at most. However, its evaluation function was very sophisticated, and it assessed positions on the basis of material, pawn structure, control of the center, and safety of the king. The other program, Tech, could look ahead up to 13 ply. It was able to evaluate so many positions because the only criterion was material superiority, and it was not bogged down by other positional considerations. The programs battled to an even endgame, when Tech, perceiving material equality, became too complacent and happily made harmless moves. Chess 3.5 quickly built up an active position, then mercilessly broke through on the kingside and won the game.

James Gillogly, programmer of Tech and a Ph.D. candidate in Computer Science at Carnegie-Mellon, regarded the game as a contest between brute force and intelligence. His program is extremely simple and was developed in about six months, which is relatively quick. Gillogly believes that the pure technological approach to chess programming, which involves few strategic ideas, can serve "as a baseline against which more sophisticated programs can be compared, thereby determining whether the development of a complex program is worth the effort."

Leverett, who is concentrating in Physics and Chemistry at Harvard, entered the tournament for the first time. His program finished in a tie for last place, and was labeled "the joke of the tournament" by International Master David Levy, the tournament director. Leverett attributed his defeat to "poor programming" and vowed to scrap his program and start all over again.

Several of the programs have played in U.S. Chess Federation-sponsored human tournaments, with mediocre results. It is lucky for human beings that most programmers consider a "self-learning" component to a computer program unfeasible, for a victory by a chess program over an excellent chess-player would truly epitomize the triumph of modern technology over human imagination.