Explanation-Based Generalization in Game Playing: Quantitative Results

Abstract

Game playing has attracted researchers in Artificial Intelligence ever since its beginnings. By comparison with human reasoning, learning by operationalization of general knowledge, as formalized by the Explanation-Based Generalization (EBG) paradigm, appears to be highly plausible in this domain. Nevertheless, none of the previously published approaches is (provably) sufficient for the target concept, and at the same time applicable to arbitrary game states. We trace this paradox back to the lack of the expressive means of Negation as Failure in traditional EBG, and constructively support our claim by applying the respective extension proposed in [Schr96] to the chess endgame king-rook vs. king-knight. Methodically, endgames are well-suited for quantitative evaluation and allow to obtain more rigorous results concerning the effects of learning than in other domains. This is due to the fact that the entire problem space is known (and can be generated) in advance. We present the main results of a large-scale empirical study. The issues of training complexity, speedup for recognition and classification, as well as the question of optimal reasoning under time constaints are analyzed.