What Were the Last Moves
Marko Maliković, Mirko Čubrilo · International Review on Computers and Software (IRECOS) · 2010
This paper presents a formal system for reasoning about retrograde chess problems using Coq - a formal proof management system. The system is divided into two parts. The first part describes the environment that includes the axioms, definitions and hypotheses of chess objects, and also the functions for computing changes in states. The second part is developed for generating possible retrograde chess moves and includes Coq’s tactics combined with the use of tacticals (elements of Ltac - the Coq’s language for combining tactics). All of these tactics are defined as one Ltac function. This approach enables reasoning about retrograde chess problems with respect to reasoning about sequences of retrograde moves. In the aforementioned Ltac function, a number of heuristic solutions are implemented with the aim of solving the problems within a big search space such as retrograde chess analysis.