imotiv

Popular Posts

Monday, January 14, 2013

History of chess computers


History of Chess Computers


In 1945 Alan Turing (1912-1954) used chess-playing as an example of what a computer could do. Turing himself was a weak chess player.

In 1946 Alan Turing made his first reference to machine intelligence in connection with chess-playing.
In 1947, Alan Turing specified the first chess program for chess.
In 1948 the UNIVAC computer was advertised as the strongest computer in the world. So strong, that it could play chess and gin rummy so perfectly that no human opponent could beat it.
In 1948 Turing challenged Donald Michie to see who could first write a simple chess-playing algorithm.
In March, 1949 Claude Shannon (1916-2001) described how to program a computer and a Ferranti digital machine was programmed to solve mates in two moves. He proposed basic strategies for restricting the number of possibilities to be considered in a game of chess. Shannon was an avid chess player. He first proposed his idea of programming a computer for chess at the National Institute for Radio Engineers (IRE) Convention in New York.
In 1950, Alan Turing 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 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 November 1951, Dr. Dietrich Prinz wrote the original chess playing program for the Manchester Ferranti computer. The program could solve simple mates in two moves.
In 1952 Alick Glennie, who wrote the first computer compiler, defeated Alan Turing’s chess program, TurboChamp. He was the first person to beat a computer program at chess. Turing never finished his chess-playing program.
In 1953 Turing included an example of his chess program in action in chapter 25 (Digital Computers Applied to Games) of the book Faster than Thought by B. Bowden.
By 1956 experiments on a Univac MANIAC I computer (11,000 operations a second) at Los Alamos, using a 6×6 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.
In 1957 a chess program was written by Alex Bernstein at MIT for an IBM 704. It could do 42,000 instructions per second and had a memory of 70 K. This was the first full-fledged game of chess by a computer. It did a 4-ply search in 8 minutes.
In 1957 Herbert Simon said that within 10 years, a digital computer would be the world’s chess champion.
In 1958 the alpha-beta pruning algorithm for chess was discovered by three scientists at Carnegie-Mellon (Allen Newell, John Shaw, and Herbert Simon). Here is how it works. A computer evaluates a move and starts working on its second move. As soon a single line shows that it will return a lower value than the first move, it can terminate the search. You could now chop off large parts of the search tree without affecting the final results.
In 1958, a chess program (NSS) beat a human player for the first time. The human player was a secretary who was taught how to play chess one hour before her game with the computer. The computer program was played on an IBM 704. The computer displayed a level of chess-playing expertise greater than an adult human could gain from one hour of chess instruction.
In 1959 some of the first chess computer programmers predicted that a chess computer would be world chess champion before 1970.
In 1962 the first MIT chess program was written. It was the first chess program that played regular chess credibly. It was written by Alan Kotok for his B.S. thesis project, assisted by John McCarthy of Stanford. The program ran on an IBM 7090, looking at 1100 positions per second.
In 1963 world chess champion Botvinnik predicted that a Russian chess playing program would eventually defeat the World Champion.
In 1965 the Soviets designed a chess program developed at the Institute for Theoretical and Experimental Physics (ITEP) in Moscow. ITEP’s programming team was led by Georgi Adelson-Velskiy.
On November 22, 1966 a USSR chess program began a correspondence match with the Kotok-McCarthy MIT chess program. The match lasted 9 months and was won by the Soviet computer, with 3 wins and 1 loss.
The first chess computer to play in a tournament was MAC HACK VI, written for a DEC PDP-6 with 16K of memory. It was written at MIT in assembly language (MIDAS) by Richard Greenblatt and could evaluate 10 positions per second. The computer entered the 1966 Massachusetts Amateur championship, scoring 1 draw and 4 losses for a USCF rating of 1243.
In the spring of 1967, MacHACK VI became the first program to beat a human (1510 USCF rating), at the Massachusetts State Championship held in Boston. 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 MAC HACK 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.
In 1968 International Master David Levy made a $3,000 bet that no chess computer would beat him in 10 years. He won his bet. The original bet was with John McCarthy, a distinguished researcher in Artificial Intelligence at Stanford. The bet was made at the 1968 Machine Intelligence Workshop in Edinburgh University.
At the end of 1968, MAC Hack VI had a USCF rating of 1529. The average rating in the USCF was around 1500.
In 1970 the first all-computer championship was held in New York and won by CHESS 3.0 (CDC 6400), a program written by Slate, Atkin and Gorlen at Northwestern University. Six programs had entered the first Association for Computing Machinery (ACM) North American Computer Championships. The event was organized by Monty Newborn. The other programs were DALY CP, J Brit, COKO III, SCHACH, and the Marsland CP.


No comments:

Post a Comment