The thesis is a contribution to computer science and artificial intelligence. The re-search done in the scope of the thesis was performed in the framework of human and computer game playing, and the game of chess was used as the experimental domain.
Many researchers used the game-playing platform and the domain of chess in their experiments, the explicit or implicit message of their works being that the results for chess are generalizable to other domains. Although we did not aim at providing spe-cific evidence for that, we believe that the below stated contributions to science also have a potential of being extendable to several other games, as well as to some other domains where heuristic search is applicable.
20
1.8. Contributions to Science
The main contributions of the thesis are as follows.
1. A new method, based on computer heuristic search, for the assessment of hu-man problem solver’s perforhu-mance, and an analysis of appropriateness of this method. [Chapters 2 and 3]
2. A new method for the assessment of thedifficulty, for a human, of a given set of problems, based on the computer’s solving of these problems. [Chapter 4]
3. A novel approach, based on computer heuristic search, to automated gener-ation of human understandable commenting of decisions in problem solving.
[Chapter 5]
4. A novel approach to the formalization of complex patterns for the purpose of annotating problem solving decisions and/or intelligent tutoring. [Chapter 6]
5. A novel approach to semi-automatic synthesis of human-understandable knowl-edge suitable for teaching how to solve problems in a given problem domain.
[Chapter 7]
6. An extensive analysis of the monotonicity property of successful heuristic eval-uation functions for games. Namely, that backed-up values of the nodes in the search space have to tend to monotonically approach to the terminal values of the problem state space with the depth of search. This means that backed-up heuristic values therefore do not approximate some unknown “true” or “ideal”
heuristic values with increasing depth of search, in contrast to what is gener-ally assumed in the literature, and that successful heuristic evaluation functions shouldnot respect the minimax relation. That is, backed-up heuristic evalua-tion values should not be invariant along the game tree, as game-theoretical values in the theoretical minimax model are. [Chapter 8]
7. An empirical proof of a novel finding that the rate of changed decisions that arise from search to different depths depends on:
• the quality of knowledge in evaluation functions, and
• the true value (relative to a fixed search depth) of a node in the search space. [Chapter 9]
Part I
Search and Knowledge
for Estimating Human Problem
Solving Performance
Chapter 2
Computer Analysis of World Chess Champions
This chapter is an updated and abridged version of the following publication:
1. Guid, M. and Bratko, I. Computer Analysis of World Chess Champions.ICGA Journal, Vol. 29, No. 2, pp. 65-73, 2006. [GB06]
It also includes some materials from the following publication:
1. Guid, M., Per´ez, A., and Bratko, I. How Trustworthy is CRAFTY’s Analysis of World Chess Champions? ICGA Journal, Vol. 31, No. 3, pp. 131-144, 2008.
[GPB08]
In this chapter, we introduce a method, based on computer heuristic search, for evaluating problem-solving performances of World Chess Champions, top-level hu-man experts in the game of chess.
Establishing heuristic-search based computer programs as an appropriate tool for estimating problem-solving performance in chess may seem impossible, since it is well known that both programs’ evaluations and programs’ decisions tend to change as depth of search increases. It is very likely that computer chess programs will continue to change their decisions with searching deeper in heuristic-search based computer analyzes for many years to come, and that the frequencies of changes will remain significant for all feasible search depths. Not to mention that the cease of decision changes at some particular search depth does not guarantee optimal play at all. Also, it is even unclear what “optimal” is? For a human, it is not necessarily
2. COMPUTERANALYSIS OFWORLDCHESSCHAMPIONS
the shortest path to win, but a kind of “easiest” and most reliable one, that is one that minimizes the risk – the probability for a human to make a mistake. It is, however, not feasible to determine such probabilities. All these issues seem like a giant obstacle on the way to establishing heuristic-search based methods as competent problem-solving performance estimators, especially in complex games like chess.
Nevertheless, we will demonstrate that heuristic search can be used reliably for the purpose of evaluating problem-solving performance. In this chapter, we present the rankings of World Chess Champions based on the scores obtained at the highest practically feasible search depth. This may seem as the only reasonable alterna-tive, since it is well known that the programs’ chess strength increases with depth of search. In Chapter 3, however, we will show that the rankings based on the obtained scores are surprisingly stable over a large interval of search depths, at least for the players whose score significantly deviates from the others.
2.1 Can Heuristic Search be Useful for Estimating Problem Solving Performance?
There are many arguments in favor of heuristic-search based computer programs being an appropriate tool for estimating problem-solving performance. In contrast to humans, they:
1. have an enormous computing power, 2. use numerical values as evaluations, 3. adhere to the same rules all the time, 4. are not influenced by emotions.
Computer programs therefore have a capability of being more consistent than human observers, and can deal with incomparably more observations in a limited time. In chess, they are particularly good at evaluating tactical positions, where a great deal of computation is required.
As the basis for estimating each player’s performance we chose the average dif-ferences between heuristic evaluations of the players’ decisions and heuristic evalu-ations of computer’s decisions, both obtained after a fixed depth of search. This may 26