I have implemented a KPK algorithm based on what is found in the chess programming wiki. But it does not seem to work. There is a possibility the problem may not be the algorithm itself, but that my search has some subtle bugs somewhere.
From the wiki (excluding some exceptions for the pawn in files ABGH), the draws:
1) the pawn may be safely captured.
2) the lone king fronts the pawn, etc...
3) the kings in direct opposition, etc...
kpk()return score 0/1 on draw.
I think the wiki has an error as it seems to indicate an additional condition for 1) and 2)
to exclude positions where the lone king is at the last rank (should be stalemate).
The won positions:
1) when the pawn wins in a race with the lone king to the promotion square. The path of the pawn clear of its king.
2) when the pawn's king defends the stop(front square) and telestops(all squares ahead of the stop) of the pawn including the promote square from 1-3 squares.
kpk() return 8xPawn less distance to promote.
When neither drawn or won kpk() return 5xPawn and some simple evaluation terms.
My understanding is that such an implementation should be able to deal with the KPK endings without failing. Or is there something missing?
The following is my implementation. kMap[] is the attack bitboard of the king.
Code: Select all
static int evalkpk(const int side) {
const int xside = side ^ 1;
const int pCol = !bits[0][Pawn];
const int xpCol = pCol ^ 1;
const int P = pclist[pCol][Pawn][0].sq;
const int pK = king[pCol], loneK = king[xpCol];
const int promSq = PROMOTE_SQ(P, pCol);
const int pFrontSq = pCol ? P - 1 : P + 1;
const int pBackSq = pCol ? P + 1 : P - 1;
const int pFrontFrontSq = pFrontSq != promSq ? (pCol ? pFrontSq - 1 : pFrontSq + 1) : -1;
const int pOnMove = (pCol == side);
int x, y;
if ((kMap[king[side]] & bits[xside][Pawn] & ~kMap[king[xside]])) {
/* pawn safely captured */
return 1;
}
/* loneK front P; stalemate when loneK at last rank */
if (loneK == pFrontSq) {
if (pK == pBackSq && !pOnMove) {
return 1;
}
/* pK diagonal behind P */
if ((pCol ? pAttack[P]->w & BB(pK) : pAttack[P]->b & BB(pK)) && pOnMove) {
return 1;
}
}
/**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.
* stalemate when loneK at last rank
*/
if ((pCol ? loneK == pK - 2 : loneK == pK + 2)
&& kMap[pK] & rMap[pK]->rank & BB(P) && pOnMove) {
return 1;
}
/* Won :- pK defends all squares ahead P upto to 3 */
if (kMap[pK] & BB(pFrontSq)) {
x = v8Pawn - DIST(P, promSq);
if (promSq == pFrontSq) {
return (pOnMove ? x : -x);
}
if (kMap[pK] & BB(pFrontFrontSq)) {
if (promSq == pFrontFrontSq) {
return (pOnMove ? x : -x);
}
if (kMap[pK] & BB(pCol ? pFrontFrontSq - 1 : pFrontFrontSq + 1)) {
return (pOnMove ? x : -x);
}
}
}
/* P wins in race to promote.
P path ahead clear of pawn king */
if (!((pCol ? BB(P) - 1 : ~(BB(P) - 1)) & rMap[P]->file & BB(pK))) {
x = DIST(P, promSq);
y = DIST(loneK, promSq) - !pOnMove;
if (y > x) {
x = v8Pawn - DIST(P, promSq);
return (pOnMove ? x : -x);
}
}
/* NOT SURE THIS IS OK ?
* P race to promote fails and if pawn K lost in K-K race to protect P, draws.
* P on move
* */
x = DIST(pK, P);
y = DIST(loneK, P) - !pOnMove;
if (x <= y + 1) {
/* pawn king wins; P now safe; */
;
} else {
/* P fails to promote; pawn king fails to protect pawn;
* draw
* */
return 1;
}
x = v5Pawn
- DIST(P, promSq) * 10
- DIST(pK, P) * 5
+ DIST(loneK, P) * 5
- DIST(pK, promSq) * 2
+ DIST(loneK, promSq) * 2
- (loneK == pFrontSq || loneK == pFrontFrontSq) * 10
- ((pCol ? loneK == pK - 2 : loneK == pK + 2)) * 10; /* kings in opposition */
return (pOnMove ? x : -x);
}
Rasjid.