Computers choose: who was the strongest player?

Who was The Strongest Chess Player of All Time?

Computer Analysis of World Chess Champions

By Matej Guid and Ivan Bratko
University of Ljubljana, Faculty of Computer and Information Science, Artificial Intelligence Laboratory, Ljubljana, Slovenia. This article is based on a paper by the same authors published in the ICGA Journal; full reference is given below.

Who is the best chess player of all time? Chess players are often interested in this question to which there is no well founded, objective answer, because it requires a comparison between chess players of different eras who never met across the board. With the emergence of high-quality chess programs a possibility of such an objective comparison arises. However, so far computers were mostly used as a tool for statistical analysis of the players' results.

Our approach was different: we were interested in the chess players' quality of play regardless of the game score, which we evaluated with the help of computer analyses of individual moves made by each player. A method to assess the difficulty of positions was designed, in order to take into account the differences in players' styles and to compensate for the fact that calm positional players in their typical games have less chance to commit gross tactical errors than aggressive tactical players. We also give a carefully chosen methodology for using computer chess programs for evaluating the true strength of chess players.

The fourteen classic-version World Champions, from the first World Chess Championship in 1886 to the present, were evaluated. Matches for the title of »World Chess Champion«, in which players contended for or were defending the title, were selected for analysis. Several different criteria were designed. The basis for evaluation was the difference between the position values resulting from the moves played by the human and the moves chosen as best by the chess program. We also calculated the average number of blunders and observed how would the players perform providing they would all deal with equally complex positions. Our analyses, among other things, also clearly show that the percentage of best moves played depends on analysed position itself and that is in very high correlation with the difference of best two moves evaluations (according to the computer): the bigger the difference between best two moves evaluations – the easier it is to find the best move. By observing the average material quantity during the games, we tried to determine players inclination to simplify positions.

Generally, our computer analysis seems to have produced sensible results that can be nicely interpreted by a chess expert. Anyway, many will find some of the results quite surprising. The winner according to the main criterion, where we measured average deviations between evaluations of played moves and best evaluated moves according to the computer, is Jose Raul Capablanca, the 3rd World Champion.

As we did in the study, this result should be interpreted in the light of the comparatively low complexity of positions in Capablanca's games. Anyway, he was also on top according to other criteria where we measured quality of play and was only beaten according to one criterion (albeit a very important one), namely the quality of play provided that all players dealt with equally complex positions, by the present World Champion, Vladimir Kramnik. Both Capablanca and Kramnik distinctly deviated from the rest of the players.

Separatelly, we conducted analysis of the latest World Championship match between Kramnik and Topalov. The results (mean loss per move: Kramnik 0.1220, Topalov 0.1328; only the games with classical time control were taken into account) tell that Kramnik's play was somewhat better, while the overall quality of play in the match was on quite decent level (comparing to other World Championship matches), although the record (Kramnik's 0.0903 in the London 2000 match against Kasparov) was really not in danger. Note that the lower this measure the better the performance.

The chess program Crafty was used to perform the analyses. We needed an open source program in order to slightly modify it, as is described in the article. One may argue that Crafty is weaker than at least some of the fourteen World Champions who were taken into consideration. However, altogether more than 37,000 positions were evaluated and even if evaluations are not always perfect, for our analysis they just need to be sufficiently accurate on average since small occasional errors cancel out through statistical averaging. Anyway, we would like to encourage other researchers that might have access to source code of the strongest commercial chess programs, to modify and run them in the way we proposed, in order to obtain a comparison between various different engines as well.

The basic criterion for evaluating World Champions was the average difference between moves played and best evaluated moves by computer analysis. According to this analysis, the winner was the third World Champion, Jose Raul Capablanca. This result should be interpreted in the light of the comparatively low complexity of positions in Capablanca's games which is quite in line with the known assessments in the chess literature of his style. For example, Garry Kasparov in his set of books My Great Predecessors when commenting Capablanca's games speculates that Capablanca occasionally did not even bother to calculate deep tactical variations. The Cuban simply preferred to play moves that were clear and positionally so strongly justified that calculation of variations was simply not necessary. He also describes Capablanca with the following words: “He contrived to win the most important tournaments and matches, going undefeated for years (of all the champions he lost the fewest games).” and “his style, one of the purest, most crystal-clear in the entire history of chess, astonishes one with his logic.”

The results of blunder-rate measurement are similar. We expected positional players to perform better by this criterion than tactical players, since in quiet positions there were less opportunities to blunder. Note the excelent result of Tigran Petrosian who is widely renowned as a pure positional player. In compliance with this observation, Steinitz, who lived in an era of tactical romantic chess, took clearly last place.

Capablanca is renowned for playing a 'simple' chess and avoiding complications, while it is common that Steinitz and Tal faced many 'wild' positions in their games. The results of complexity measurement clearly coincide with this common opinion.

The method for assesing the complexity of positions is described in detail in the original article (see also the reference below). Graph of errors made by players at different levels of complexity clearly indicates the validity of the chosen measure of complexity of positions; the players made little errors in simple positions, and the error rate increased with increasing complexity.

We used the above mentioned metric of position complexity to determine the distribution of moves played across different intervals of complexity, based on positions that players had faced themselves. This, in turn, largely defines their style of play. For example, Capablanca had much less dealing with complex situations compared to Tal, who is to be regarded as a tactical player.

The main deficiency of the two criteria, as detailed in the previous subsections, is in the observation that there are several types of players with specific properties, to whom the criteria do not directly apply. It is reasonable to expect that positional players in average commit fewer errors due to the somewhat less complex positions in which they find themselves as a result of their style of play, than tactical players. The latter, on average, deal with more complex positions, but are also better at handling them and use this advantage to achieve excellent results in competition. We wanted to determine how players would perform when facing equally complex positions. The winner was the fourteenth World Champion Vladimir Kramnik. Kramnik also had the best performance of all the matches; his average error in his match against Kasparov (London, 2000) was only 0.0903. We also tried to determine how well the players would play, should they all play in the style of Capablanca, Tal, etc. It is interesting to notice that Kasparov would outperform Karpov, providing they both played in Tal's style.

The percentage of best moves played alone does not actually describe the quality of a player as much as one might expect. In certain types of position it is much easier to find a good move than in others. Experiments showed that the percentage of best moves played is highly correlated to the difference in evaluations of the best and second-best move in a given position. The greater the difference, the better was the percentage of player's success in making the best move.

Based on that observation, another criterion was the expected number of best moves played providing that all players dealt with positions with equal difference between the best two moves, as was described in the previous section. It represents another attempt to bring the champions to a common denominator. See the results right below.

Kramnik, Fischer, and Alekhine had the highest percentage of best moves played, but also the above-mentioned difference was high. In contrast, Capablanca, who was right next regarding the percentage of the best move played, on average dealt with the smallest difference between the best two moves. The winner by this criterion was once again Capablanca. He and Kramnik again clearly outperformed the others.

The purpose of calculating the average material quantity, that is the sum of the numerically expressed values of all pieces on board, was not to determine the quality of play, but to collect additional information on a player's style of play. We mainly tried to observe a player's inclination to simplify positions.

Among the players who stand out from the others, Kramnik obviously dealt with less material on board (remember his early queen exchanges in his Berlin Wall games against Kasparov?). The opposite could be said for Steinitz, Spassky, and Petrosian.

The authors

Matej Guid has received B.Sc. degree in computer science at the University of Ljubljana. He works on his Ph.D. thesis at Artificial intelligence Laboratory, Faculty of Computer and Information Science of Ljubljana University. His present research includes machine learning, computer chess, heuristic programming and robot learning by experimentation. At the present time he works on programming an automated Chess Tutor that will be able to intelligently comment chess games in a language comprehensible to humans. Chess has been one of Matej's favourite hobbies since he was a little kid, he was also a junior champion of Slovenia a couple of times.

Ivan Bratko is professor of computer science at University of Ljubljana, Slovenia. He is head of Artificial intelligence Laboratory, Faculty of Computer and Information Science of Ljubljana University, and has conducted research in machine learning, knowledge-based systems, qualitative modelling, intelligent robotics, heuristic programming and computer chess (do you know the famous Bratko-Kopec test?). Professor Bratko has published over 200 scientific papers and a number of books, including the best-selling Prolog Programming for Artificial Intelligence. Chess is one of his favourite hobbies.

The original paper was published in the ICGA Journal, Vol 29, No. 2, June 2006, pages 65-73. It was also presented at the 5th International Conference on Computers and Games, May 29-31 2006, Turin, Italy, and was published in the proceedings book.