Chess is the Drosophila of artificial intelligence. --- Alexander Kronrod, Russian mathematician
In 1965, the Russian mathematician Alexander Kronrod said, "Chess is the Drosophila of artificial intelligence." However, computer chess has developed much as genetics might have if the geneticists had concentrated their efforts starting in 1910 on breeding racing Drosophila. We would have some science, but mainly we would have very fast fruit flies. --- from AI as Sport, by John McCarthy
Chess is one of the world's most popular games. Its popularity and complexity make it an interesting research domain for artificial intelligence. It is a perfect information game, meaning that both players know the entire state of the game at any given time, but that doesn't make it easy for either humans or machines to master. Chess playing machines have been the subject of human interest for hundreds of years, but only on the last few decades have they been able to compete with (and beat) the top human players.
Challenges for AI Research
- A board position, or state, is a specific layout of the pieces on the chess board. The state space of chess is the number of board positions we can get to from the initial board state. This number is larger than the number of atoms in the universe!
- Since a particular board position can occur in multiple games, the number of possible chess games is even bigger than the size of the state space.
- While good chess playing machines can be built, completely solving the game looks to be very difficult. How could a computer possibly represent more distinct things than there are atoms in the universe?
- Current research is attempting to solve "end-games", where the game is mostly played out and only a few pieces remain. The end-games where 5 or 6 pieces remain have been solved, and researchers are currently attempting to solve the 7 piece end-game. Storing the data for the 5 piece end-games requires about 7 GB of memory, and the 6 piece end-games require over a 1 TB.
- "Machines" that played chess appeared in the 1700 and 1800s, but they were all hoaxes.
- In the 1950s, the first papers on programs to play chess were published by Claude Shannon and Alan Turing.
- In the 1956, the alpha-beta search algorithm was invented. Alpha-beta is a very common search technique for adversarial games, including chess.
- In the 1960s, computer chess programs started playing each other.
- In the 1970s, computer chess programs began being successful in tournaments with humans.
- In the 1980s, computers started beating masters and grandmasters in tournament play, and also received master titles of their own.
- In 1997, Deep Blue beat Gary Kasparov, the world champion, in a six game match.
- Current chess programs continue to beat the world champions. Chess programs now have their own tournaments.