In chess, the number of legal positions is 10^40, whereas the number of different possible games has been calculated to be approximatively 10^123. These figures are impressive. For this reason, Chess has been known as “the game that embraces the infinite”. To give an idea of the complexity of this ancient board game, we can think that the possible combinations of the game-tree after just 8 moves are about 85 billion, a number close to that of the stars in the Milky Way, which has been estimated to be about 100 billion[1].
This universe, hidden in the 64 black and white squares of the chess board, which has been the theater of epic battles and chimeric riddles, has always fascinated mathematicians, philosophers, and strategists of every age and culture.
The idea of creating a machine able to play a chess game is also quite ancient and traces back to the 18th century. The first chess machine, called “The Turk” was invented by Wolfgang von Kemplen to impress the Empress Maria Theresa of Austria in 1769. Despite in its 84 years of activity, The Turk has defeated famous opponents as Napoleon Bonaparte and Benjamin Franklin, it eventually revealed to be a hoax, as it was actioned by a man that was hidden inside (there is also an Edgar Allan Poe short story about it).
A modern recreation of the von Kemplen’s machine
The first program able to play an entire chess game, from the opening to the end, was developed by Alan Turing, English mathematician and father of the Turing machine, which is considered the archetype of modern computers. The algorithm, named Turochamp, was written on paper in 1948 and was able to play an entire chess game, choosing how to move pieces after calculating the possible moves of the opponent. Although the program was quite complex at that time, and evaluated moves using a scoring system based on pieces’ value and position, the possibility of checkmate and other factors, its playing strength revealed to be weak. Anyway, Turing was not able to execute the program on a computer before his death, which occurred in 1954. Neverthless, Turochamp was extremely important for the development of subsequent chess engines.
The first victory of a machine over a human is dated 1956. The players were the program Los Alamos Chess and a technician of the Los Alamos Laboratory (New Mexico, where the program was developed), who had been instructed about the rules of chess a week before. Actually, due to its poor computing power, the program was able to play only on a 6×6 board, in a chess variant called “anti-clerical” because it lacked bishops.
The 6×6 board used by Los Alamos Chess
In the same year (1956) the term “Artificial Intelligence” was introduced for the first time by John McCarthy at the Conference of Darthmouth. Years later, Herbert Simon (Nobel prize for Economics in 1978), one of the major protagonists of the famous conference, suggested chess as the ideal setting for experiments in Machine Learning. Since then, chess and AI have been inseparably bounded, as the chess board was considered the perfect ground to test the strength of the algorithms (many compared the relationship between chess and AI to that of drosophila and genetics)[2].
In the 70s and 80s, the development of chess engines and computers was prodigious, thanks to the advances in scientific research, especially in game theory and combinatorics. From that moment on, the higher computing power started threatening human supremacy in chess. In those years, new programs were able to defeat not just amateurs but even top players, although the historic breakthrough took place on 10th February 1996, when Garry Kasparov, the reigning world champion, was defeated by Deep Blue, an IBM computer designed to play chess. Kasparov had actually won the game by 4-2 but was irremediably beaten a year later, in 1997, from the updated version of the IBM computer, unofficially nicknamed “Deeper Blue”.
Chess enthusiasts watch the match between Kasparov and Deep Blue
To overcome even the best player in the world, IBM computers employed a method called alpha-beta pruning, quite different from modern neural networks which are used today to develop AI interfaces. The idea was to focus on two values, alpha and beta, in order to evaluate moves and combinations to maximize the score of the computer (alpha) and minimize the score of the opponent (beta), “solving” the game by brute-force.
The AI community, despite being pleased by the great attention received worldwide, was eventually disappointed that Deep Blue was so far away from what AI fathers had imagined 40 years before. Instead of having a machine able to play chess as a human, using creativity and intuition, they had a computer that evaluated 200 million moves per second, and managed to win only because of its computing power. In this regard, years later Kasparov himself stated: “Deep Blue was only intelligent the way your programmable alarm clock is intelligent. Not that losing to a $10 million alarm clock made me feel any better.” [3]
During the 2000s artificial chess engines definitely seized the supremacy over humans. Although some Great Masters were able to obtain some victories using “anti-computer” strategies, playing defensively and looking for an end-game advantage (more difficult to spot for a machine), the development of computer chess was unstoppable and since 2009 chess engines started systematically defeating top players, becoming available also on smartphones.
In the last decade engines based on neural networks saw the light, and nowadays they are dominating computer chess championships. Those new engines work in a different way as they don’t need databases to learn how to play and they are able to win without the brute-force approach. AlphaZero, a software developed by DeepMind (a Google company since 2014) learned playing chess by training against himself, developing a very creative style of play, much closer to that of humans. In 2017 AlphaZero defeated Stockfish, which was the greatest chess engine based on brute-force. The team of Stockfish (which in 2020 is back on the top of the charts) has announced that will introduce in its engines Machine Learning algorithms based on neural networks.
Will be neural networks the tool that will make us able to “solve” the ancient riddles of chess, finding the way to play the perfect match? Time will tell!
[1] Rasskin-Gutman, D. (2009). Chess metaphors: artificial intelligence and the human mind. MIT Press.
[2] Ensmenger, N. (2012). Is chess the drosophila of artificial intelligence? A social history of an algorithm. Social Studies of Science, 42(1), 5-30.
[3] Kasparov, G. (2010). The Chess Master and the Computer. The New York Review of Books, Vol. 57, No. 2
Comments are closed.
