Figure 6.3: After iteration 6, the expert gave the following description why the bishop is bad in position on the left: “The bishop is bad, because, taking the pawn structure into account, only one square is accessible to it.” The argu-ment “IMPROVED BISHOP MOBILITY=low” was added to this position, based on this description. However, in the next iteration, the machine learning method selected the position on the right, where the bishop is classified as “not bad”, as the counter-example. After the expert’s examination, the following significant dif-ference between the two positions was determined: in the position on the right, there are no bad pawns ahead of the bishop. Based on that, the argument to the position on the left was improved to “IMPROVED BISHOP MOBILITY=low AND BAD PAWNS AHEAD=high”.
6.5 Assessment and Discussion
The machine learning methods that were used on CRAFTY’s original positional fea-ture values were tested on the same data, supplemented with the newly obtained attribute values. All the accuracy and precision results were again obtained through 10-fold cross validation.
The results are presented in Table 6.6. They suggest that the performance of other algorithms could also be improved by adding appropriate additional attributes (com-pare to Table 6.2). However, using arguments (as with the method ABCN2), besides stimulating the expert to identify the need for useful additional attributes, also guides the method towards appropriate combinations of attributes, which is likely to lead to even more accurate models.
The main advantage of ABML over classical machine learning is the ability to take advantage of an expert’s prior knowledge in the induction procedure. This leads
6. OBTAINING KNOWLEDGE FOR A HEURISTIC-SEARCHBASEDPROGRAM
Table 6.5: The rules forBAD BISHOP=yes, obtained after the14th(final) iteration.
Positional feature #1 #2 #3 #4 #5 #6 #7
BAD PAWNS >14 >32
BAD PAWNS AHEAD >20 >18 >26 >28 >12
BLOCKED DIAGONAL >4 >16 >16
BLOCKED BAD PAWNS >0
positive examples 46 46 42 38 38 36 31
negative examples 0 0 0 0 0 0 0
Table 6.6: The machine learning methods’ performance with the data, supplemented with the newly obtained attribute values.
Method Classification accuracy Precision
Decision trees (C4.5) 85% 85%
Logistic regression 89% 91%
Rule learning (CN2) 91% 94%
Rule learning with arguments (ABCN2) 94% 96%
to hypotheses comprehensible to experts, as it explains learning examples using the same arguments as the expert did. In our case study this was confirmed by chess experts. According to them, the final set of rules are more alike to their understanding of the bad bishop concept than the initial rules were. Furthermore, the final rules were also recognized to be in accordance with the traditional definition of a bad bishop.
Our domain experts clearly preferred the ABML approach to manual knowledge acquisition. The formalization of the concept of bad bishop turned out to be be-yond the practical ability of our chess experts (a master and a woman grandmaster).
They described the process as time consuming and hard, mainly because it is diffi-cult to consider all relevant elements. ABML facilitates knowledge acquisition by fighting these problems directly. Experts do not need to consider all possibly rele-vant elements, but only elements relerele-vant for a specific case, which is much easier.
98
6.5. Assessment and Discussion
Moreover, by selecting only critical examples, the time of experts involvement is decreased, making the whole process much less time consuming.
Given our experimental findings in the domain of chess, we believe that our ap-proach to knowledge elicitation based on the ABML type of machine learning will be most helpful for obtaining positional features useful for heuristic-search based programs. Complex features such as BAD BISHOP that we formalized in our case study may not always be suitable for evaluation functions of competitive programs, where time spent on heuristic search is quite important (besides, appropriate weights of these features should be determined). Nevertheless, they could serve well for an-notation purposes. For example, when used in a software such as the chess annotating system presented in Chapter 5.
Chapter 7
Deriving Concepts and Strategies from Chess Tablebases
This chapter is an updated and abridged version of the following publication:
1. Guid, M., Moˇzina, Sadikov, A., and Bratko, I. Deriving Concepts and Strate-gies from Chess Tablebases. ACG 2009, Lecture Notes in Computer Science 6048 (eds. Herik, H.J. van den, and Spronck, Peter), pp. 195-207. Springer, 2010. [GMSB10]
In this chapter, we demonstrate a semi-automatic procedure for deriving con-cepts and strategies usable for intelligent tutoring purposes from chess tablebases, i.e., databases that contain perfect information. We focus on constructing human-friendly textbook instructions for teaching a difficult-to-master KBNK (king, bishop and knight versus a lone king) chess endgame. The instructions were obtained from a hierarchical model of semi-automatically generated goal-based rules, and repre-sent the knowledge of a search-based program that is capable of giving instructive annotations.
The chapter is organized as follows. Section 7.1 contains a short overview of related work on extracting knowledge from chess tablebases. In Section 7.2, we first present the obtained textbook instructions. The hierarchical model of ordered set of rules is given at the end of the section, together with an example game contain-ing automatically generated instructions based on these rules. In Section 7.3, we introduce the basics of our approach to goal-based rule learning, explain the guide-lines for interaction between the machine and the expert in order to obtain a
human-7. DERIVING CONCEPTS ANDSTRATEGIES FROMCHESSTABLEBASES
understandable rule-based model for playing a chess endgame, and describe how the instructions for KBNK were derived semi-automatically from our hierarchical rule-based model. In Section 7.4, we present the evaluation of the instructions by three renown chess teachers, and an evaluation of human-like style of play generated by our method by four international grandmasters. We conclude the chapter by some final remarks and intentions for further work.
7.1 Learning from Perfect Information
Chess tablebases [Tho86] have enabled people a glimpse of how a perfect play looks like. It seems, however, that people are ill adapted to understanding this perfection.
While tablebases are of enormous help to computers, people are for the most part puzzled by the style of play generated by tablebases. Yet, people would very much like to learn as much as possible, and there is no doubt that tablebases contain an enormous amount of potential knowledge – but in a form not easily accessible to a human mind.
There have been many attempts to extract knowledge from tablebases. Perhaps two best documented examples are a research project carried out by a chess study specialist John Roycroft [Roy88] and the work of grandmaster John Nunn resulting in two books on pawnless endings [Nun95; Nun02]. All the attempts, however, had at most limited success.
The goal of Roycroft’s study was that he would learn himself reliably to play the KBBKN endgame (king and two bishops vs. king and knight). This endgame was for a long time considered generally to be drawn, until the KBBKN tablebase was computed. The tablebase showed that the side with two bishops can usually force a win, but the winning play is extremely difficult and takes a long sequence of moves under optimal play by both sides. Many moves in the optimal play for the stronger side are completely obscure to a human. Roycroft tried to extract a human-executable winning strategy by the help of this tablebase, trying manually to discover important concepts in this endgame which would enable a human to win reliably. After a one year’s effort, the project ended with rather limited success when Roycroft’s accumulated skill for this endgame was still not quite sufficient to win actually against the tablebase in many of the won KBBKN positions.
The task of learning is not any easier for the computer. In an overview of the learning methods in games, F¨urnkranz indicated that machine learning of understand-102