Combining Knowledge and Search to Yield Infallible Endgame Programs 1

Abstract

A provably correct program for the competition of passed Pawns in the KPKP endgame has been developed, using a method described due to Barth and Barth (1992). The method combines the application of strict rules with α-β search. The rules cover a large part of the positions of the endgame. For each such position they define an interval guaranteed to contain the true value. An α-β search finds the values for all positions not covered and removes uncertainties left by too wide intervals in rule-valued positions. Thus, the method yields a correct evaluation for every position and, furthermore, the rules governing the position or its successors provide some tutorial insight to the user about the reasons behind the evaluations. Moreover, automatic validation assures that mistakes in the rules will be discovered and then can be eliminated in dialogue.

Only a few simple rules are essential to the KPKP algorithm, all of which are well-known to skilful chess-players. Some of them are almost trivial, yet they have to be formulated with cautious precision and to be cast into an algorithmic format. Surprising oddities come to light in the process.

The behaviour of the program has been tested by solving many studies and by analyzing some game positions discussed in the literature.