Synthesis of Chess and Chess-like Endgames by Recursive Optimisation

Abstract

A new algorithm is presented for synthesising correct and optimal game-playing programs directly from the specifications. The programs deal with chess-like endgames. The algorithm is based on the principle of self-optimisation allowing the program-construction process to be time-feasible.

A LISP implementation of the synthesising algorithm has generated a program for playing optimally a three-piece endgame on a specialised board. The program established the general KB/RK configuration as a win for White, and constructed a maximin of 39 moves; moreover it provided an analysis of the maximin position. The experimental results are presented.

Finally, the relationship to other game-playing work is discussed, and the applicability of the algorithm to more general domains is considered.