In the article “Is chess the drosophila of artificial intelligence? A social history of an algorithm“, Nathan Ensmenger writes about the history of artificial intelligence and chess computers as well as providing a detailed description of the main chess algorithm, minimax tree search. Here are some notes on the article:
- Russian mathematician Alexander Kronrod was credited for first stating that “chess was the drosophila of artificial intelligence” in 1965 to justify the use of expensive computers for playing chess.
- In 1946, Turing suggested that chess playing computers would be an example of a thinking machine and in 1953 he wrote the first program that could play chess; however, there were no computers around that could run his program.
- In 1950, Claude Shannon wrote the first paper on chess algorithms and proposed two main approaches: type ‘A’ brute force minimax search and type ‘B’ which used heavy heuristics to carefully examine a much smaller number of positions. Type ‘A’ turned out to be superior for chess and governed the vast majority of chess computer research. Shannon introduced the terms “ply” and “pruning”.
- Chess minimax algorithms were attractive because they were simple to program and modify, they required only a little memory, and they worked. Chess was attractive to AI because there were well-known standards for play (Elo chess ratings) and ever improving computing hardware created ever improving, measurable performance in computer chess play, providing some defense against the critics of AI during the AI winter. (see e.g. Lighthill Report)
- Unlike the drosophila in genetics research, the simplistic minimax algorithm never lead to improved theoretical understanding in AI and may have even hindered the progress of AI.
- When Deep Blue beat Gary Kasparov, it was capable of “11,380,000,000 floating point operations per second, making it one of the top 300 supercomputers in the entire world at the time.”
Perhaps surprisingly, the article does not discuss the major improvements made to computer chess by Fabien Letouzey (Fruit) and Vasik Rajlich (Rybka) in 2006 and 2007. Though these programs increased the power of chess computers by 200 Elo points over one year, they had little or no impact on AI. I guess 200 Elo points does not seem like much compared to the 2000 Elo gain of computer chess programs between 1960 and today. The 2000 point gain has been due to both hardware and software improvements but does not seem to stem from advances in AI. In fact, modern chess programs do not seem to use any modern machine learning algorithms. (Please write a comment about this if I am wrong!)