KPK

Home * Evaluation * Game Phases * Endgame * Pawn Endgame * KPK

A very common pattern in chess games is to be up exactly one pawn and then try to trade down to a won KP vs K endgame. So this is a very fundamental ending that good chess programs should understand.

Contents

Bitbase

Since only 3 pieces are involved, it can be handled easily by a 12 KByte per side, pre-calculated bit table that returns the status of this ending from any of the 64*64*4*6 = 98304 distinct configurations for the pawn on one wing. It is always a win or draw for the side with the pawn. Boolean win or not information requires some distance heuristics though to ensure progress.

Perfect Heuristics

This ending can also be determined perfectly with a set of heuristics ¹.

Imperfect Heuristics

There is also an imperfect solution that yields reasonably good results - using interior node recognizers detecting positions that are obviously won or drawn, but leaving "unclear" positions to evaluation and/or further search. An example of such a set of heuristics is given below:

KPK is drawn

In the case that the pawn can be immediately captured, might be delegated to the quiescence search
Defending king stands directly in front of the pawn, the other king - directly behind it, weaker side to move
Defending king as above, the other king diagonally behind the pawn, stronger side to move
Kings stand in the vertical opposition and the pawn is on the right/left side of the king of the stronger side, which is about to move
In the above position the stronger side moves a pawn, giving check
Assuming the squares are numbered 0..63, H1 being 0, the following code marks positions as drawn:

// a feeble attempt at using corresponding squares
if ( isPiece(WHITE,KING, pawn_sq-7) || isPiece(WHITE,KING, pawn_sq-8) || isPiece(WHITE,KING, pawn_sq-9) ) {
   if ( isPiece(BLACK,KING, pawn_sq+15) || isPiece(BLACK,KING, pawn_sq+16) || isPiece(BLACK,KING, pawn_sq+17) ) {
     if (to_move == WHITE && ROW(blackKingLoc) != ROW_8 ) return DRAW;
   }
}

Please note that the code must exclude positions where the defending king is on the last rank. Additionally there are drawn rook pawn cases where the defender prevents the king on the pawn's frontspan from leaving the rook file.

KPK is won

Stronger king defends all stop and telestop(s), including the promotion square up to three squares. With defender to move, one has to consider whether the pawn can be captured, since defended stop square does not necessarily imply the pawn is defended as well. Additionally, there is a stalemate exception with the knight pawn.
Defending king is (leaves after moving) outside the square of the pawn ²

if the own king blocks the frontspan, it is still won. However the defending king may further reach the "square of the pawn" due to the extra tempo and one needs to apply some more rules to avoid knowledge holes in that cases.

Selected Publications

1970 ...

Soei Tan (1972). Representation of knowledge for very simple pawn endings in chess. Report MIP-R-98; School of Artificial Intelligence, University of Edinburgh
Max Bramer (1977) KPK: using effective distance. Open University, Milton Keynes
Max Bramer (1977). KPK: Some Quantitative Data. Technical Report, Open University, Faculty of Mathematics.
Mike Clarke (1977). A quantitative study of KPK. Advances in Computer Chess 1, pp. 108-118
Pericles Negri (1977). Inductive Learning in a Hierarchical Model for Representing Knowledge in Chess End Games. pdf
Ryszard Michalski, Pericles Negri (1977). An experiment on inductive learning in chess endgames. Machine Intelligence 8, pdf
Max Bramer (1978). A Note on KPK. Technical Report, the Open University: Faculty of Mathematics, Milton Keynes, England.

1980 ...

Don Beal, Mike Clarke (1980). The Construction of Economical and Correct Algorithms for King and Pawn against King. Advances in Computer Chess 2
Max Bramer (1980). An Optimal Algorithm for KPK using Pattern Knowledge. Advances in Computer Chess 2
Alen Shapiro, Tim Niblett (1982). Automatic Induction of Classification Rules for Chess End game. Advances in Computer Chess 3
David Slate (1984). Interior-node Score Bounds in a Brute-force Chess Program. ICCA Journal, Vol. 7, No. 4
Ard van Bergen (1985). An Ulti-Mate Look at the KPK Data Base. ICCA Journal, Vol. 8, No. 4
Ard van Bergen, Theo van der Storm (1986). The KPK Endgame: a Unit Correction. ICCA Journal, Vol. 9, No. 1
Max Bramer (1986). KPK Endgame Databases: a Response From the Source. ICCA Journal, Vol. 9, No. 3
Hans Zellner (1989). The KPK Database Revisited. ICCA Journal, Vol. 12, No. 2