Validation of machine-oriented strategies in chess endgames

Abstract

This thesis is concerned with the validation of chess endgame strategies. It is also concerned with the synthesis of strategies that can be validated. A strategy for a given player is the specification of the move to be made by that player from any position that may occur. This move may be dependent on the previous moves of both sides. A strategy is said to be correct if following the strategy always leads to an outcome of at least the same game theoretic value as the starting position. We are not concerned with proving the correctness of programs that implement the strategies under consideration. We shall be working with knowledge-based programs which produce playing strategies, and assume that their concrete implementations (in POP2, PROLOG etc.) are correct. The synthesis approach taken attempts to use the large body of heuristic knowledge and theory, accumulated over the centuries by chessmasters, to find playing strategies. Our concern here is to produce structures for representing a chessmaster's knowledge wnich can be analysed within a game theoretic model. The validation approach taken is that a theory of the domain in the form of the game theoretic model of chess provides an objective measure of the strategy followed by a program. Our concern here is to analyse the structures created in the synthesis phase. This is an instance of a general problem, that of quantifying the performance of computing systems. In general to quantify the performance of a system we need,- A theory of the domain. - A specification of the problem to be solved. - Algorithms and/or domain-specific knowledge to be applied to solve the problem.