Portal de Periódicos da CAPES

How Can Humans Learn from Computers?

2010; International Computer Games Association; Volume: 33; Issue: 4 Linguagem: Inglês

10.3233/icg-2010-33406

2468-2438

Dap Hartmann,

Speech and dialogue systems

In his PhD thesis, FIDE Chess Master Matej Guid combines three interrelated research endeavors: (1) Measuring human problem solving performance; (2) Improving human problem solving performance; (3) Improving the understanding of heuristic search in computer game playing.The scope of this research project is limited to human and computer game playing, and chess was chosen as the experimental domain.A logical choice when you are a FIDE Master and Ivan Bratko is your thesis supervisor.To answer the question How can we develop methods based on computer heuristic search for evaluating human problem solving performance?Guid carried out a computer analysis of the (problem solving) performance of World Chess Champions.Every game played in every (classical) World Championship match between 1886 (Steinitz -Zukertort) and 2006 (Kramnik -Topalov) was analyzed by CRAFTY (starting at move 12 and using no opening book) to a depth (iteratively) of 12 ply (plus quiescence search).Under these conditions, it is doubtful whether CRAFTY performs at a World Champion level.Guid discusses the credibility of a heuristic search based estimator and provides a probabilistic model of ranking by 'an imperfect referee' to demonstrate that this does not pose a problem.So, the imperfect referee CRAFTY serves as a solid benchmark against which all former human World Champions were assessed.The following data were collected for each search depth (from 2 to 12 ply): the best move (and score), the second-best move (and score), and the score of the move that was actually played in the game.These data were fed into an algorithm that used various criteria to decide who was the greatest Chess World Champion between 1886 and 2006.The most important criterion was the average difference in the evaluation values between the moves actually played and the best moves found by CRAFTY.This method is somewhat biased and favors positional players over tactical players.The winner is José Raúl Capablanca (World Champion from 1921-1927), followed by Vladimir Kramnik (2000Kramnik ( -2007)).Wilhelm Steinitz came in last while Bobby Fischer, rather surprising perhaps, is in 11 th place (out of the 14 World Champions).Guid also presents a few other metrics to rank these former World Champions, such as blunder rates and percentage of best moves played.Cuba will undoubtedly be delighted by the outcome of this experiment.However, Guid shows that, on average, Capablanca was faced with 'much easier' positions than Steinitz.The metric that Guid developed to determine the difficulty of a position confirms the established view that "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."