Chess and Machines
“Even if we could teach a computer to play chess merely as well as a -- to use Norbert Wiener’s simile -- majority of the human race (no offense meant), we would be furnishing definite proof that a machine can solve problems of sufficient complexity to defy the reasoning ability of millions of people throughout their lives.”
-Edward Lasker, The Adventure of Chess.
In 1769, a Viennese expert in hydraulics and acoustics, Wolfgang von Kempelen, exhibited an interesting conjurer’s trick to the Imperial Court of King Joseph II. It was a life-sized figure of a Turk seated behind a chessboard on top of a chest. The chest appeared to be filled with cogs and gears, which von Kempelen would demonstrate in the course of a game of chess against a human challenger. The Turk would invariably win, and its entertainment value was the same as any magic act; how did he do that? It was obvious to all that no machine could possibly play chess.
After von Kempelen’s death, the Turk was bought by a Bavarian musician and showman, Johann Maelzel. Maelzel had already built and exhibited mechanical devices of his own; a mechanical trumpet player, and the Panharmonicum, which played a variety of orchestral instruments. (Beethoven composed pieces specifically for these devices). Maelzel took over the Turk and was successful far beyond anything he could have imagined, making huge amounts of money. Never claiming that the device itself actually played chess, he made it part of the show to demonstrate the impossibility of hiding a human inside the Turk.
Even today we are not sure how the Turk actually operated. We know there was a man hidden inside the device, and that he used an arrangement of levers called a pantograph to make the Turk’s arm move his pieces, but beyond that, we have only guesses. We will never know for certain because the Turk was destroyed by a fire in 1854.
Another device, called Ajeeb and dressed as an Egyptian, was built in 1868 and had a similar career. Ajeeb also beat all comers, and at one time the “inside man” was American master Harry Pillsbury. Ajeeb too, was destroyed in a fire, this one at Coney Island in 1929.
However, in the late 19th century, something much more interesting and more directly related to computer chess was happening at the Escuela Technica Superior de Ingenieros de Cuminos (The School of Road Works) at Spain’s Polytechnic University. Leonardo Torres y Quevedo had devised a pressure sensor connected to a rudder which would keep torpedoes at a constant depth. Torres y Quevedo was impressed by the “intelligence” of the sensor in performing its limited task. It functioned much more efficiently than any human could, and Torres y Quevedo wondered if there might be more thing a device might be “taught” to do. So, in 1890 he built a prototype device which would play the chess ending of White King and Rook against a human with the Black King. Not only did the device win, it also said “check” and “mate”. A final version was exhibited at the Paris World Fair in 1914, but the World War prevented any further work.
In 1939, the British Foreign Office established the Department of Communications at Bletchley, 50 miles north of London. Their purpose was to build a device which would crack German coded messages no matter how the ingenious German encoding device known as “Enigma” was set. In order to accomplish this task, the Foreign office had to go beyond cryptanalysis experts, so they also employed mathematicians, electronic engineers, linguistics, crossword puzzle buffs and chess players.
The man most responsible for the success of the project was Alan Turing, a prominent and eccentric mathematician and a chess buff. Earlier, Turing had proposed a theoretical computing machine which would simulate the operation of any other machine. This “Turing machine” became part of the foundation of modern computer theory.
At Bletchley, Turing built a device to decode Enigma messages. Known as “the bomb” or “Ultra”. Turing’s machine worked so well that Allied leaders frequently had German messages decrypted and translated before their intended recipients got them.
Turning’s device was not a computer, however. After the war, Turing got a large grant from the British government to build a general purpose electronic computer. Although he had established the mathematical concept for such a machine in 1936, building a working model was not easy. Turing talked to reporters about it in 1946, calling it an “automatic computing engine”, and in the same interview discussed the possibilities of computer chess. He was quoted as saying “That is a question we may be able to settle in about 100 years time”.
But Turing had worked out the formulas necessary for a chess program, and in 1951 or 1952 he used it in an actual game. Working his program from notes on paper, Turing played Alick Glennie, who was an admittedly weak player. Glennie reported that Turing had trouble operating his own program because it often chose wrong moves that Turing knew were wrong. The game took about two or three hours, and ended when Turing’s program lost its Queen. Turing was quoted as saying the program has resigned “on the advice of his trainer”. In his spare time, Turing began programming the Manchester University computer to play chess, but died before he could complete his work.
In the United States, Dr. Claude E. Shannon of Bell Labs described in March of 1949 how an electronic computer could be programmed to play chess. Shannon was interested in computer chess only because most people felt that chess required “thought”. If a computer could be programmed to play chess, Shannon felt, that would hold great theoretical implications for the future of computers. Two of Shannon’s proposals are still of interest. He defined the two schools of chess programs, brute force (rapidly looking at all possible moves) vs. heuristic programming (choosing moves based on some set of rules). Shannon favored brute force because that approach takes advantage of the computer’s obvious strengths. He also suggested that machines be programmed to learn directly from their mistakes, a refinement that in the main has thus far eluded programmers.
In Los Alamos, New Mexico in 1956, Ulam and Stein actually programmed a computer to play a simplified version of chess (a six by six square board, leaving out the Bishops, limiting pawns to a one square advance on opening and omitting castling). They wanted to know whether a computer could make responsible moves solely based on the basis of material gain and increased mobility. The computer played itself first, revealing an inordinate fear of being in check. After a few improvements, the program, MANIAC I, became the first computer program to win a game against a human - an unnamed volunteer who had learned the game only a week before. Capable of 11,000 operations per second, MANIAC I used exhaustive search to look ahead four plies (a ply, is a half move. Thus a computer would examine all the computer’s possible moves, all possible replies by the opponent, all computer’s responses to those, and all the opponent’s responses.) in 12 minutes per move.
In an article in the June 1958 Scientific American, Alex Bernstein, a mathematician and a very strong chess player, and Michael Roberts described how they, Timothy Arbuckle and M. A. Belsky had programmed an IBM 704 to play chess. Their program ran on 8,000 punch cards, and required that its opponent punch his moves into a card and then feed it into a reader. The machine a 4-ply search like the Alamos program, but also added two new considerations, King defense and area control. Bernstein’s program also used a ratio to consider material evaluation, which was an advance over the simple point system used previously. Running at about 42,000 operations per second, this program was able to play a fair amateur game at the rate of a move every eight minutes.
The next year, Herbert Simon, Allen Newell and Clifford Shaw of the Rand Corporation and Carnegie Institute of Technology came up with a very complex program that could play at the medium amateur level. It took about an hour per move, but because it represented such a huge leap in computer chess technology, it led Herbert Simon to predict that within 10 years a computer would be the world chess champion.
In 1965, Professor Hubert L. Dreyfus evaluated the play of MANIAC II (an improved MANIAC which played on a full eight by eight board), Bernstein’s program for the IBM 704, and a program of his own, and announced “Still no chess program can play even amateur chess”. By December of that year, Dr. Dreyfus had lost a game to MAC HACK, developed by Richard Greenblatt and Donald Eastlake of M.I.T. MAC HACK was another breakthrough, able to defeat about 80 percent of non-tournament level players. Greenblatt and Eastlake were good programmers with a very fast computer for the time, the PDP-6. Their “plausible move generator”, with 50 criteria for a move, cut down on the number of moves the machine had to consider. And there was one other important factor; most opponents resigned too soon. Believing that MAC HACK’s strong opening and middle game represented its ability, few humans got as far as MAC HACK’s dreadful endgame. By 1968, when MAC HACK VI was demonstrated at the International Federation of Information Processing (IFIPS) meeting in Edinburgh, its rating was 1500 Elo. (The system developed by Arpad Elo assigns a player a numerical rating based on his (or its) record against other rated players.)
After this, things began happening very quickly. Between 1967 and 1970, eight new programs appeared in the United States alone, and in 1970, the first U.S. Computer Chess Championship took place. CHESS 3.0, created by David Slate, Larry Atkin and Keith Gorlen of Northwestern University, swept the tournament, winning all three of its games. The CHESS program as version 3.5 in 1971 and 3.6 in 1972 also won all of its games in the next two U.S. championships. The 1972 contest featured notes on the games by Samuel Reshevsky, a master player and ex-U.S. champion.
In 1974, CHESS 4.0 appeared, a completely new version which marked a switch from selective search to full-width search, in keeping with Dr. Shannon’s predictions of the greater suitability of the brute-force approach. Unfortunately, this was the version that lost the first World Computer Chess Championship in Stockholm. It placed second to KAISSA from the Soviet Union, a program on which Mikhail Botvinnik, the ex-World Champion, had worked. In all fairness, it should be pointed out that CHESS did not play KAISSA in the tournament, and in an unofficial game played after the event, the outcome was adjudicated a draw after the 65th move. In the second World Computer Championship held in Toronto in 1977, CHESS 4.6 won in a clean sweep, although again, it did not meet KAISSA during the match. This time, however afterwards, CHESS beat KAISSA in 44 moves.
In 1978, it was time to play the “Levy challenge”. Ten years earlier, the International Master David Levy had bet two computer scientists £500 that no computer chess program would be able to beat him in ten years’ time. When the match came around, the bets had increased to £1,250, and Levy played a series of matches against CHESS 4.5, KAISSA, MAC HACK V1 and CHESS 4.7. Levy won every match, and only CHESS 4.7 was able to score a point against him. While disappointing to its programmers, its one win against Levy represented the first time a computer had won a game against an International Master.
Omni Magazine then offered £4,000 to the first program to beat Levy. Levy increased the stakes to £5,000, and in 1983, he was challenged by the creators of CRAY BLITZ, the winner of the 1983 World Computer Championship. Levy played CRAY BLITZ in April of 1984, and although he did not lose a game, Levy did compliment the programmers by studying CRAY BLITZ’s games in detail.
CRAY BLITZ was also beaten as North American Computer Champion in October of 1985 by HITECH, designed by Hans Berliner, Carl Eberling and Murray Campbell of Carnegie Mellon University. Berliner designed a unique processor he called the searcher which employs 64 chips, one for each square on the board. Each chip examines the entire board for moves and determines the best one. The searcher the ranks the 64 choices, and the game tree is searches as deep as 14 plies based on the searcher’s ranking. So far, HITECH has had an easy time playing computer opponents.
Earlier, we quoted from Edward Lasker’s The Adventure of Chess. Lasker stated that if a computer could play chess merely as well as the vast majority of the human race, “we would be furnishing definite proof that a machine can solve problems of sufficient complexity to defy the reasoning ability of millions of people throughout their lives”. Your CHESSMASTER 2100 far exceeds Lasker’s requirement. The creators of THE CHESSMASTER 2100 gratefully acknowledge the pioneering efforts of those programmers whose earlier chess programs paved the way for the state-of-the-art program you now own.
Excerpt taken from THE FIDELITY CHESSMASTER 2100 Manual.