Search and Knowledge for Human and Machine Problem Solving

In Artificial Intelligence (AI), there exist formalised approaches and algorithms for general problem solving. These approaches address problems that require combinatorial search among alternatives, such as planning, scheduling, or playing of games like chess. In these approaches, problems are typically represented by various kinds of graphs, and problem solving corresponds to searching such graphs. Due to their combinatorial complexity, these problems are solved by heuristic search methods where problem-specific heuristics represent the solver’s knowledge about a concrete problem domain. Thus such computer-based approaches to problem solving roughly consist of two components: search among alternatives, and problem-specific knowledge. Computer methods of heuristic search are also a good model of human problem solving. In human problem solving, however, these two components take very different dimensions compared with machine problem solving. A human expert typically uses much richer domain-specific knowledge whereas the computer has the advantage of incomparably faster search compared to the human. The thesis presents some novel aspects on the comparison and combination of search and knowledge in human and machine problem solving, in particular with respect to possibilities of developing heuristic-search methods for evaluating and improving problem-solving performance. Among others, the following scientific questions are addressed. How can a computer be used to assess a human’s problemsolving performance? How can a machine problem solving model be used to assess the difficulty of a given set of problems for a human? How can machine problem solving be used in tutoring, for teaching a human to solve problems in a given problem domain? How can knowledge represented in a form suitable for the computer, be transformed into a form that can be understood and used by a human? In this thesis we explore these questions in the framework of human and computer game playing, and use the game of chess as the experimental domain. In Part I of the thesis, “Search and Knowledge for Estimating Human Problem Solving Performance,” we demonstrate that heuristic-search based programs can be useful estimators of human problem-solving performance. We introduced a novel method, based on computer heuristic search, for evaluating problem-solving performance in chess (with possible extensions to other games), and provided an analysis of appropriateness of this method. Experimental results and theoretical explanations were provided to show that, in order to obtain a sensible ranking of the chess players using our method, it is not necessary to use a computer that is stronger than the chessplayers themselves. We also designed a heuristic-search based method for assessing the average difficulty of a given set of chess positions (problem situations). In Part II, “Search and Knowledge for Improving Human Problem Solving Performance,” we presented a novel, heuristic-search based approach to automated generation of human understandable commenting of decisions in chess. We also demonstrated a novel approach to the formalization of complex patterns for the purpose of annotating chess games using computers. Finally, we introduced a procedure for semi-automatic synthesis of knowledge suitable for teaching how to solve problems in a given domain. We verified appropriateness of this procedure in a case study where we applied it to obtain human-understandable textbook instructions for teaching a difficult chess endgame. Part III, “On The Nature of Heuristic Search in Computer Game Playing,” aims at improving the understanding of properties of heuristic search and consequences of the interaction between search and knowledge that typically occurs in both human and machine problem solving. Monotonicity property of heuristic evaluation functions for games was revisited. Namely, that backed-up values of the nodes in the search space have to tend to approach monotonically to the terminal values of the problem state space with the depth of search. We pointed out 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 generally assumed in the literature. We also discussed some of possible impacts of this property on the theory of game playing, and pointed out that heuristic evaluations obtained by searching to different search depths are not directly comparable, in contrast to what is generally assumed both in literature and in practical applications. Finally, we studied experimentally factors which influence the behavior of diminishing returns with increased search. Empirical proof was provided that the rate of changed decisions that arise from search to different depths depends on (1) the quality of knowledge in evaluation functions, and (2) the value of a node in the search space