Early Computer Chess Programs by Bill Wall

On March 9, 1949, Claude Shannon (1916-2001), a research worker at Bell Telephone Laboratories in New Jersey, presented a paper called “Programming a Digital Computer for Playing Chess.” The paper was presented at the National Institute for Radio Engineers Convention in New York. He described how to program a computer to play chess based on position scoring and move selection. He proposed basic strategies for restricting the number of possibilities to be considered in a game of chess.

In 1950, Shannon devised a chess playing program that appeared in the paper "Programming a computer for playing chess" published in Philosophical Magazine, Series 7, Vol. 41 (No. 314, March 1950). This was the first article on computer chess.

In 1950, Alan Turing (1912-1954) wrote the first computer chess program. The same year he proposed the Turing Test that in time, a computer could be programmed (such as playing chess) to acquire abilities rivaling human intelligence. If a human did not see the other human or computer during an imitation game such as chess, he/she would not know the difference between the human and the computer.

In 1951, Turing tried to implement his “Turbochamp” program on the Ferranti Mark I computer at Manchester University. He never completed the task. However, his colleague, Dr. Dietrich Prinz (born in 1903), wrote a chess playing computer program for the Ferranti computer that solved simple mates in two moves. The first program ran in November 1951. The program would examine every possible move until a solution was found. It took about 15 minutes to solve a mate in two moves.

By 1956 experiments on a Univac MANIAC I computer (capable of 11,000 operations a second and used to design hydrogen bombs) at Los Alamos, using a 6x6 chessboard, was playing chess. This was the first documented account of a running chess program. It used a chess set without bishops. It took 12 minutes to search 4 moves deep. Adding the two bishops would have taken 3 hours to search 4 moves deep. MANIAC I had a memory of 600 words, storage of 80K, 11KHz speed, and had 2,400 vacuum tubes. The team that programmed MANIAC was led by Stan Ulam (1909-1984), who invented nuclear pulse propulsion and designed the H-bomb with Edward Teller.

In 1957, Alex Bernstein, an IBM employee, created the first really complete chess program at IBM.  With his colleagues Michael Roberts, Thomas Arbucky and Martin Belsky, Bernstein created a chess program at the Massachusetts Institute of Technology. It ran on an IBM 704 (42,000 instructions per second), one of the last vacuum tube computers.  It took about 8 minutes to make a move. Bernstein got support from chess advisor Arthur Bisguier, who became an IBM employee and an international grandmaster in 1957. International Master Edward Lasker played the program, easily defeating it, but he commented that it played a ‘passable amateur game.’

The Bernstein Chess Program was the prototype of a selective forward pruning technique called the Shannon Type B (selective search) program. His program searched four plies and considered seven most plausible moves from each position, evaluating material, mobility, area control and king defense.

 In 1958, Allen Newell (1927-1992), Herbert Simon and Cliff Shaw developed the chess program CP-1 at Carnegie-Mellon.  It was the first chess program to be written in a high-level language and took about an hour to make a move.  Their NSS (Newell, Simon, Shaw) program combined algorithms that searched for good moves with heuristics that captured well-known chess strategies. Its most important innovation was the alpha-beta tree search. This is how it works. A computer evaluates a move and starts working on its second move. As soon as a single line shows that it will return a lower value than the first move, it can terminate the search. You can now chop off large parts of the search tree without affecting the final results. The NSS chess program ran on a Johnniac computer.

 In 1959, MIT freshmen Alan Kotok (1942-2006), Elwyn Berlekamp, Michael Lieberman, Charles Niessen, and Robert A. Wagner started working an a chess-playing program while students of  Professor John McCarthy (1927-  ) at the Massachusetts Institute of Technology (MIT).  They started with Bernstein’s program, then added alpha-beta pruning to minmax at McCarthy’s suggestion to improve the plausible move generator.  They wrote in Fortran, and a single move could take five to twenty minutes to complete. Their chess-playing program ran on an IBM 7090 mainframe computer.

 In 1962, the first MIT chess program was written.  It was the first chess program that played regular chess credibly.  It was chiefly written by Alan Kotok for his Bachelor of Science thesis project, assisted by John McCarthy (father of artificial intelligence) of MIT.  The program ran on an IBM 7090, looking at 1,100 positions per second.  The program was able to beat chess beginners.  Kotok, at age 20, published their work in MIT Artificial Intelligence Memo 41 and his B.S. thesis.

 Kotok went on to become one of DEC’s leading computer designers (chief architect of the PDP-10), and created the first video game and the gaming joystick.

 In 1965, McCarthy, who was now a professor at Stanford University since 1962, visited the Soviet Union.  There, a group at the Moscow Institute for Theoretical and Experimental Physics (ITEP), led by Alexander Kronrod, challenged his chess program to a match with their chess program, later called KAISSA.  A match was held over nine months in 1966-67.  The Kotok-McCarthy program lost the match 3-1. The Kotok-McCarthy program ran on an IBM 7090 computer. The Soviet chess program ran on an M-20 computer. Former world champion Mikhail Botvinnik was an advisor for the Soviet chess program. After the match, Konrod lost his directorship at ITEP and his professorship because of complaints from the physics users that ITEP resources were being wasted on chess.

 In 1965, Dr. Hubert Dreyfus, a professor of philosophy at MIT, later at Berkeley, was hired by RAND Corporation to explore the issue of artificial intelligence.  He wrote a 90-page paper called “Alchemy and Artificial Intelligence” (later expanded into the book What Computers Can’t Do) questioning the computer’s ability to serve as a model for the human brain.  He also asserted that no computer program could defeat even a 10-year-old child at chess.

 MacHack (Mac Hack or Mac Hac) was a computer chess program written by Richard Greenblatt, with assistance from Donald Eastlake, in the 1960s at MIT.  It is sometimes known as the Greenblatt Chess Program.  MacHack VI was the first chess program (a Shannon type B program) to play in human tournaments.  It was also the first to be granted a chess rating, and the first to draw and win against a person in tournament play.

 The name came from Project MAC (Multilevel Access Computer or Machine-Aided Cognition), which was a research project located at MIT.  The number VI refers to the DEC PDP-6 (200KHz) machine for which it was written.  DEC built the PDP-6 and gave the first prototype to Project MAC.  The PDP-6 had a speed of about 225,000 instructions per second.

 Greenblatt was very interested in artificial intelligence (AI).  He decided to use the computer operating system to actually do something in AI.  He had seen Kotok’s chess playing program and knew it was bad.  Since he was also a chess player, it was only logical that he work on a chess program that would go beyond Kotok’s chess programming effort, as well as other AI chess projects that had been attempted at various labs around the country.

 Greenblatt wrote the program after reading an MIT Artificial Intelligence memo on the limitation of computer chess.  He said he intended to write a chess-playing program good enough to beat a human.  Greenblatt’s thesis adviser, Marvin Minksy, tried to discourage Greenblatt, telling him that there was little home of making progress in chess-playing software.  Greenblatt managed to get four hours of PDP-6 time a day, then wrote code off-line when he wasn’t on the machine.  He began his work in November, 1966.

 Greenblatt added 50 heuristics (rules of thumb for making a move) to an older chess program written by Kotok.  MacHack was written in MIDAS macro assembly language on the PDP-6 computer that DEC donated to MIT.  Greenblatt wrote the chess program using only 16K of memory for the PDP-6 computer.  It evaluated about 10 positions per second. 

 MacHack was the first computer program to implement a transposition table and an opening ‘book.’  This innovation let the computer take advantage of the fact that about 25% of all move sequences transpose to the same end position.  Greenblatt was able to get his program playing chess in one week.  The program was debugged and given features over the next few months.  It used a plausible move generator to restrict the number of moves examined at each ply.  It examined 15 moves at ply one, 15 at ply two, 9 at ply three, and 9 at ply four.  In order to search to a five-ply depth, the program had to deal with a game tree of 127,575 moves.

 Greenblatt was offered a B.S. degree from MIT if he would write a thesis about his chess program.  He never did write his thesis.

 Greenblatt later founded Lisp Machine, Inc., and is considered one of the founders of the hacker community.

 On January 21-23, 1967, MacHack VI played in the Massachusetts Amateur Championship in Boston.  It was the first time an electronic computer played chess against human beings under regular tournament conditions.  Technical advice in the programming was given by Larry Kaufman (1966 American Open winner), Alan Baisley, and Robert A. Wagner.  They were all highly rated chess players and MIT students.  The computer played all five rounds and ended up with a score of 0.5-4.5, one draw (against J. Conroy, rated 1412) and four losses.  The program pulled off some nice combinations, but was weak in the endgame.  After the tournament, MacHack VI’s provisional rating was 1239 (Class D).  (Chess Life, February, 1967, page 23).

 In 1967, several MIT students and professors (organized by Seymour Papert) challenged Dreyfus to play a game of chess against MacHack VI.  Dreyfus accepted.  Herbert Simon, an AI pioneer, watched the match.  He said “It was a wonderful game - a real cliffhanger between two woodpushers with bursts of insights and fiendish plans…great moments of drama and disaster that go in such games.”    Dreyfus was being beaten by the computer when he found a move which could have captured the enemy queen.  The only way the computer could get out of this was to keep Dreyfus in checks with his own queen until he could fork the queen and king, then exchange them.  And that’s what the computer did.  Soon, Dreyfus was losing.  Finally, the computer checkmated Dreyfus in the middle of the board.

In the spring of 1967, MacHack VI became the first program to beat a human (1510 USCF rating) in a rated event, the Boston Amateur championship.  Machack VI won two games and drew two games.  MacHack VI was strong in the opening and middle game, but its endgame was very weak.  The weak endgame was due to its center-controlled heuristic interfered with the advancing passed pawns.

 By the end of the year, it had played in four chess tournaments. It won 3 games, lost 12, and drew 3. In 1967 MacHack VI was made an honorary member of the US Chess Federation. The MacHack program was the first widely distributed chess program, running on many of the PDP machines. It was also the first to have an opening chess book programmed with it.

 By the end of 1967, MacHack (Machack) VI was rated 1493 by the U.S. Chess Federation.  By the end of 1968, MacHack VI was rated 1529.  The average rating in the USCF was around 1500.

 By 1969, MacHack played in 18 chess tournaments and had played over 100 completed games.

 Later, MacHack was available on all PDP-10 computers (400,000 instructions per second).  A version was made available on many time-sharing computer services using DEC PDP series computers.  This led to a rapid proliferation of chess programs.  Within three years of MacHack VI’s debut, at least eight new programs appeared.  This led to the first tournament for computer programs in 1970.  MacHack remained active in chess competitions through 1972.