A history of computer chess – from the “Mechanical Turk” to “Deep Blue”

 

Baron Wolfgang von Kempelen’s “Mechanical Turk,” an elaborate hoax. Courtesy, GearLog.com

An “elaborate hoax”

In 1769 the Hungarian-born engineer Baron Wolfgang von Kempelen (1734-1804) built a chess playing machine for the amusement of the Austrian Queen Maria Theresa. It was a purely mechanical device – a chess-playing automaton later revealed to be a hoax. Its outstanding aptitude, it was later revealed, originated from a man hidden inside the device. Interestingly, it was described in an essay by Edgar Allan Poe, “Maelzel’s Chess-Player.”

In March of 1949, Claude Shannon (1916-2001), a research worker at Bell Telephone Laboratories in New Jersey 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, 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 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 fifteen minutes to solve a mate in two moves.

In 1946 the Hungarian/American mathematician John von Neumann was given the task of designing a powerful calculation machine to speed up the task. In 1950 a giant machine called MANIAC I was delivered. It was filled with thousands of vacuum tubes and switches and could execute 10,000 instructions per second. It was also programmable.

By 1956, Univac’s MANIAC I computer was capable of playing chess using a 6″x6″ chessboard.  This was the first documented account of a running chess program. It used a chess set without bishops.  It took twelve minutes to search four moves deep.  Adding the two bishops would have taken three hours to search four moves deep. MANIAC I was programmed by Stan Ulam who designed the Hydrogen bomb with Edward Teller.

In 1957, Alex Bernstein, an IBM employee, created the first really complete chess program. With three colleagues, Bernstein created a chess program at the Massachusetts Institute of Technology.  It ran on an IBM 704, one of the last vacuum tube computers.  It took about eight minutes to make a move. International Master Edward Lasker played the program, easily defeating it, but he commented that it played a ‘passable amateur game.’

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 (rules of thumb for making a move) that captured well-known chess strategies.  The NSS chess program ran on a JOHNNIAC computer.

Artificial intelligence in computer chess

In 1962, the first chess program at the Massachusetts Institute of Technology was written.  It was the first chess program that played chess credibly.  It was chiefly written by Alan Kotok (1942-2006), assisted by John McCarthy (father of artificial intelligence) of MIT. The program ran on an IBM 7090, and was able to beat chess beginners. Kotok went on to become one of DEC’s leading computer designers (chief architect of the PDP-10), and created the first video game (Spacewar!) and the gaming joystick.

In 1965, McCarthy, who had been 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 own, later called KAISSA.  A match was held over nine months in 1966-67.  The Kotok-McCarthy program lost the match 3-1.  The Soviet chess program ran on an M-20 computer. 

MacHack (Mac Hack or Mac Hac) was a computer chess program written by Richard Greenblatt, an MIT expert in artificial intelligence, with Donald Eastlake, in the 1960s. MacHack VI was the first chess 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. Its 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 for which it was written.  DEC built the PDP-6 and gave the first prototype to Project MAC. 

Greenblatt added fifty heuristics 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 ten positions per second. 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.  The computer played all five rounds and ended up with a score of 0.5-4.5, one draw.  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.

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.

Sargon Computer Chess

The original SARGON was written by Dan and Kathleen ‘Kathe’ Spracklen in a Z80-based computer called Wavemate Jupiter III using assembly language through TDL Macro Assembler.

The name “Sargon” was taken from either of the historical kings Sargon of Akkad (the first king to use his empire to try to conquer the known world) or Sargon of Assyria. (Ironically, neither ruler would have been able to play chess since it was not invented until long after their reigns.) One other possibility is that it was taken from a character in the original Star Trek series. The name was originally written entirely in capitals because early computer operating systems such as CP/M did not support lower-case file names.

SARGON was introduced at the 1978 West Coast Computer Faire, where it won the first computer chess tournament held strictly for microcomputers. This success encouraged the authors to seek financial income by selling the program directly to customers. Since magnetic media were not widely available at the time, the authors placed an advert in Byte Magazine and mailed photocopied listings that would work in any Z80-based microcomputer. Later they were contacted by Hayden Books and a book was published.

In 1985, three doctoral students created the chess-playing program Chiptest. This would develop into Deep Thought, a program that shared first place with Grandmaster Tony Miles in the 1988 U.S. Open championship and defeated the brilliant sixteen year-old Grandmaster Judit Polgar in 1993 in a thirty-minute game.

Deep Blue

In May of 1997, IBM’s Deep Blue, a chess program running on a high-powered computer, defeated world champion Gary Kasparov in a six-game series. The computer was designed to consider several billion possibilities at once. But it also uses a series of complicated formulae that take into consideration the state of the game. These formulae, among other factors, weigh the relative material value of pieces (e.g. queens are more useful than knights) and position (e.g. can you attack more squares than your opponent?), safety of the king and the pace of the game.

Deep Blue also kept a record of several past matches to see how it could make best use of what was available. Kasparov found this out – the hard way. On the other hand, when he played some unorthodox moves, he had the computer totally flustered.

References:

“Mastering the Game: A History of Computer Chess” Computer History Museum, current exhibition.

“MacAttack” Chess.com, May 13, 2008.

“IBM Deep Blue vs. Gary Kasparov,” Quantum Gambits, Ocbober 8, 2009.

Friedel, Frederick: “A Short History of Computer Chess.” Chessbase. N.d.

Surendran, Dinoj. “A Brief History of Computer Chess.” Zimaths, Vol. 2, Issue 1, October, 1996.

IBM Deep Blue website.

Read Full Post »