25,161
edits
Changes
KPK
,Created page with "'''Home * Evaluation * Game Phases * Endgame * Pawn Endgame * KPK''' A very common pattern in chess games is to be up exactly one pawn..."
'''[[Main Page|Home]] * [[Evaluation]] * [[Game Phases]] * [[Endgame]] * [[Pawn Endgame]] * KPK'''
A very common pattern in chess games is to be up exactly one [[Pawn|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.
=Bitbase=
Since only 3 pieces are involved, it can be handled easily by a 12 KByte per side, pre-calculated [[Endgame Bitbases|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|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 <ref>[[Max Bramer]] ('''1977''') ''KPK: using effective distance.'' [https://en.wikipedia.org/wiki/Open_University Open University], [https://en.wikipedia.org/wiki/Milton_Keynes Milton Keynes]</ref>.
=Imperfect Heuristics=
There is also an imperfect solution that yields reasonably good results - using [[Interior Node Recognizer|interior node recognizers]] detecting positions that are obviously won or drawn, but leaving "unclear" positions to evaluation and/or further [[Search|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|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|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:
<pre>
// 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;
}
}
</pre>
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 [[Pawn Spans|frontspan]] from leaving the rook file.
==KPK is won==
* Stronger king defends '''all''' [[Stop square|stop]] and [[Pawn Spans#StopandDistantStop|telestop(s)]], including the [[Promotion Square|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|stalemate]] [https://en.wikipedia.org/wiki/Key_square#An_exception exception] with the knight pawn.
* Defending king is (leaves after moving) outside the [[Rule of the Square#TheSquareofthePawn|square of the pawn]] <ref>[[King Pattern#SetwiseRuleoftheSquare|Set-wise Rule of the Square]] with [[Bitboards]]</ref>
: if the own king blocks the [[Pawn Spans|frontspan]], it is still won. However the defending king may further reach the "square of the pawn" due to the extra [[Tempo|tempo]] and one needs to apply some more rules to avoid knowledge holes in that cases.
=See also=
* [[Endgame Tablebases]]
* [[Retrograde Analysis]]
* [[Unstoppable Passer]]
<span id="SelectedPublications"></span>
=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.'' [https://en.wikipedia.org/wiki/Open_University Open University], [https://en.wikipedia.org/wiki/Milton_Keynes Milton Keynes]
* [[Max Bramer]] ('''1977'''). ''KPK: Some Quantitative Data.'' Technical Report, [https://en.wikipedia.org/wiki/Open_University 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''. [http://www.mli.gmu.edu/papers/69-78/77-2.pdf pdf]
* [[Ryszard Michalski]] and [[Pericles Negri]] ('''1977'''). ''An experiment on inductive learning in chess endgames''. [http://www.doc.ic.ac.uk/~shm/MI/mi8.html Machine Intelligence 8], [http://www.mli.gmu.edu/papers/69-78/77-1.pdf pdf]
* [[Max Bramer]] ('''1978'''). ''A Note on KPK.'' Technical Report, the [https://en.wikipedia.org/wiki/Open_University Open University]: Faculty of Mathematics, [https://en.wikipedia.org/wiki/Milton_Keynes 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]]
* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]
* [[Ard van Bergen]] ('''1985'''). ''An Ulti-Mate Look at the KPK Data Base''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[Ard van Bergen]] and [[Theo van der Storm]] ('''1986'''). ''The KPK Endgame: a Unit Correction''. [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]]
* [[Max Bramer]] ('''1986'''). ''KPK Endgame Databases: a Response From the Source.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Hans Zellner]] ('''1989'''). ''The KPK Database Revisited''. [[ICGA Journal#12_2|ICCA Journal, Vol. 12, No. 2]]
==1990 ...==
* [[Guy Haworth]], [[Meel Velliste]] ('''1998'''). ''[http://centaur.reading.ac.uk/4569/ Chess Endgames and Neural Networks]''. [[ICGA Journal#21_4|ICCA Journal, Vol. 21, No. 4]]
* [[Ulrich Thiemonds]] ('''1999'''). ''Ein regelbasiertes Spielprogramm für Schachendspiele''. [https://en.wikipedia.org/wiki/University_of_Bonn University of Bonn], [https://en.wikipedia.org/wiki/Diplom Diplom] thesis, [http://www.iai.uni-bonn.de/~idb/diplomarbeiten/thiemonds99.ps.gz zipped ps], [http://idb.informatik.uni-bonn.de/publications/da/da_thiemonds_1999.pdf pdf] (German) <ref>[http://idb.informatik.uni-bonn.de/publications/DA Diploma Theses — IDB]</ref> <ref>[http://www.iai.uni-bonn.de/~idb/ehemaligedipl.html Uni Bonn - AG Intelligente Datenbanken - Was sind intelligente Datenbanken?]</ref>
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=14578 Is this rule safe (how has K&Ps vs K&Ps databases? ...)] by [[Mark Lefler]], [[CCC]], June 20, 2007 » [[Now]], [[Pawn Endgame]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46651 KPK] by [[Ed Schroder|Ed Schröder]], [[CCC]], December 30, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46893 KPK bitbase] by [[Maarten Bults]], [[CCC]], January 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47557 How to implement KPK ?] by [[Rasjid Chan]], [[CCC]], March 21, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=57517 Yet another KPK endgame table generator: pfkpk] by [[Marcel van Kervinck]], [[CCC]], September 05, 2015 » [[Endgame Bitbases]] <ref>[https://github.com/kervinck/pfkpk kervinck/pfkpk · GitHub]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=59928 Test position that requires KKP evaluation] by [[Shawn Chidester]], [[CCC]], April 22, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60151 kpk bitbase, worthless?] by [[Alexandru Mosoi]], [[CCC]], May 12, 2016
=External Links=
* [https://en.wikipedia.org/wiki/King_and_pawn_versus_king_endgame King and pawn versus king endgame from Wikipedia]
: [https://en.wikipedia.org/wiki/Key_square Key square from Wikipedia]
* [https://github.com/kervinck/pfkpk kervinck/pfkpk · GitHub] » [[KPK]] [[Endgame Bitbases|Bitbase]] by [[Marcel van Kervinck]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57517 Yet another KPK endgame table generator: pfkpk] by [[Marcel van Kervinck]], [[CCC]], September 05, 2015</ref>
=References=
<references />
'''[[Pawn Endgame|Up one Level]]'''
A very common pattern in chess games is to be up exactly one [[Pawn|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.
=Bitbase=
Since only 3 pieces are involved, it can be handled easily by a 12 KByte per side, pre-calculated [[Endgame Bitbases|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|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 <ref>[[Max Bramer]] ('''1977''') ''KPK: using effective distance.'' [https://en.wikipedia.org/wiki/Open_University Open University], [https://en.wikipedia.org/wiki/Milton_Keynes Milton Keynes]</ref>.
=Imperfect Heuristics=
There is also an imperfect solution that yields reasonably good results - using [[Interior Node Recognizer|interior node recognizers]] detecting positions that are obviously won or drawn, but leaving "unclear" positions to evaluation and/or further [[Search|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|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|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:
<pre>
// 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;
}
}
</pre>
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 [[Pawn Spans|frontspan]] from leaving the rook file.
==KPK is won==
* Stronger king defends '''all''' [[Stop square|stop]] and [[Pawn Spans#StopandDistantStop|telestop(s)]], including the [[Promotion Square|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|stalemate]] [https://en.wikipedia.org/wiki/Key_square#An_exception exception] with the knight pawn.
* Defending king is (leaves after moving) outside the [[Rule of the Square#TheSquareofthePawn|square of the pawn]] <ref>[[King Pattern#SetwiseRuleoftheSquare|Set-wise Rule of the Square]] with [[Bitboards]]</ref>
: if the own king blocks the [[Pawn Spans|frontspan]], it is still won. However the defending king may further reach the "square of the pawn" due to the extra [[Tempo|tempo]] and one needs to apply some more rules to avoid knowledge holes in that cases.
=See also=
* [[Endgame Tablebases]]
* [[Retrograde Analysis]]
* [[Unstoppable Passer]]
<span id="SelectedPublications"></span>
=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.'' [https://en.wikipedia.org/wiki/Open_University Open University], [https://en.wikipedia.org/wiki/Milton_Keynes Milton Keynes]
* [[Max Bramer]] ('''1977'''). ''KPK: Some Quantitative Data.'' Technical Report, [https://en.wikipedia.org/wiki/Open_University 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''. [http://www.mli.gmu.edu/papers/69-78/77-2.pdf pdf]
* [[Ryszard Michalski]] and [[Pericles Negri]] ('''1977'''). ''An experiment on inductive learning in chess endgames''. [http://www.doc.ic.ac.uk/~shm/MI/mi8.html Machine Intelligence 8], [http://www.mli.gmu.edu/papers/69-78/77-1.pdf pdf]
* [[Max Bramer]] ('''1978'''). ''A Note on KPK.'' Technical Report, the [https://en.wikipedia.org/wiki/Open_University Open University]: Faculty of Mathematics, [https://en.wikipedia.org/wiki/Milton_Keynes 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]]
* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]
* [[Ard van Bergen]] ('''1985'''). ''An Ulti-Mate Look at the KPK Data Base''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[Ard van Bergen]] and [[Theo van der Storm]] ('''1986'''). ''The KPK Endgame: a Unit Correction''. [[ICGA Journal#9_1|ICCA Journal, Vol. 9, No. 1]]
* [[Max Bramer]] ('''1986'''). ''KPK Endgame Databases: a Response From the Source.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Hans Zellner]] ('''1989'''). ''The KPK Database Revisited''. [[ICGA Journal#12_2|ICCA Journal, Vol. 12, No. 2]]
==1990 ...==
* [[Guy Haworth]], [[Meel Velliste]] ('''1998'''). ''[http://centaur.reading.ac.uk/4569/ Chess Endgames and Neural Networks]''. [[ICGA Journal#21_4|ICCA Journal, Vol. 21, No. 4]]
* [[Ulrich Thiemonds]] ('''1999'''). ''Ein regelbasiertes Spielprogramm für Schachendspiele''. [https://en.wikipedia.org/wiki/University_of_Bonn University of Bonn], [https://en.wikipedia.org/wiki/Diplom Diplom] thesis, [http://www.iai.uni-bonn.de/~idb/diplomarbeiten/thiemonds99.ps.gz zipped ps], [http://idb.informatik.uni-bonn.de/publications/da/da_thiemonds_1999.pdf pdf] (German) <ref>[http://idb.informatik.uni-bonn.de/publications/DA Diploma Theses — IDB]</ref> <ref>[http://www.iai.uni-bonn.de/~idb/ehemaligedipl.html Uni Bonn - AG Intelligente Datenbanken - Was sind intelligente Datenbanken?]</ref>
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=14578 Is this rule safe (how has K&Ps vs K&Ps databases? ...)] by [[Mark Lefler]], [[CCC]], June 20, 2007 » [[Now]], [[Pawn Endgame]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46651 KPK] by [[Ed Schroder|Ed Schröder]], [[CCC]], December 30, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46893 KPK bitbase] by [[Maarten Bults]], [[CCC]], January 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47557 How to implement KPK ?] by [[Rasjid Chan]], [[CCC]], March 21, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=57517 Yet another KPK endgame table generator: pfkpk] by [[Marcel van Kervinck]], [[CCC]], September 05, 2015 » [[Endgame Bitbases]] <ref>[https://github.com/kervinck/pfkpk kervinck/pfkpk · GitHub]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=59928 Test position that requires KKP evaluation] by [[Shawn Chidester]], [[CCC]], April 22, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60151 kpk bitbase, worthless?] by [[Alexandru Mosoi]], [[CCC]], May 12, 2016
=External Links=
* [https://en.wikipedia.org/wiki/King_and_pawn_versus_king_endgame King and pawn versus king endgame from Wikipedia]
: [https://en.wikipedia.org/wiki/Key_square Key square from Wikipedia]
* [https://github.com/kervinck/pfkpk kervinck/pfkpk · GitHub] » [[KPK]] [[Endgame Bitbases|Bitbase]] by [[Marcel van Kervinck]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57517 Yet another KPK endgame table generator: pfkpk] by [[Marcel van Kervinck]], [[CCC]], September 05, 2015</ref>
=References=
<references />
'''[[Pawn Endgame|Up one Level]]'''
