Co-ordinate Square: Solution to Many Chess Pawn Endgames

Abstract

The solution to a number of Artificial Intelligence problems depends upon knowledge representation. The theory of Co-ordinate Squares is a framework for representing the relevant ideas in a large class of king and pawn endinas. Some endgame problems which require twenty to thirty plies of analysis using a more traditional representation, a branchi"l tree of moves, can be efficiently solved using this theory, which is analogous to Waltz' scene analysis alaorithm. The Co-ordinate Squares theory, which has received considerable attention in the chess literature over the last half century, is Implemented using a constraint propagation technique. The constraint is that the defendina kina must precisely co~rdinate with the attacking king to avoid losing. For any particular square the attacking kil)g occupies, there are only a few possible (co~rdinating} squares the defending king could occupy without transposing into a known lost position. As the attacking king moves from one square to another, the defending king must co-ordinate, move from a co-ordinate of the one square to ·a coordinate of the other. We will give a reduction algorithm which propagates this constraint in order to determine the coordinate squares.