TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Chan Rasjid

Joined: 09 Mar 2006
Posts: 567
Location: Singapore

Post subject: How to implement KPK ?    Posted: Thu Mar 21, 2013 3:43 am

Hello,

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: 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); }

Best Regards,
Rasjid.
_________________
Don't believe when you're told "There's no free lunch!" There is Linux.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 3:43 am
H.G.Muller Thu Mar 21, 2013 7:46 am
Chan Rasjid Thu Mar 21, 2013 8:27 am
H.G.Muller Thu Mar 21, 2013 10:07 am
H.G.Muller Thu Mar 21, 2013 10:33 am
Chan Rasjid Thu Mar 21, 2013 6:10 pm
Don Dailey Tue Apr 02, 2013 6:56 pm
Lucas Braesch Thu Mar 21, 2013 11:03 am
H.G.Muller Thu Mar 21, 2013 11:52 am
Lucas Braesch Thu Mar 21, 2013 12:04 pm
H.G.Muller Thu Mar 21, 2013 6:36 pm
H.G.Muller Thu Mar 21, 2013 9:00 pm
Chan Rasjid Sat Mar 30, 2013 8:15 am
Evert Glebbeek Sat Mar 30, 2013 8:42 am
Sven Schüle Sat Mar 30, 2013 12:12 pm
Chan Rasjid Sat Mar 30, 2013 12:20 pm
Sven Schüle Sat Mar 30, 2013 12:42 pm
Chan Rasjid Sat Mar 30, 2013 2:03 pm
Sven Schüle Sat Mar 30, 2013 6:29 pm
Wylie Garvin Sat Mar 30, 2013 12:50 pm
Chan Rasjid Sat Mar 30, 2013 1:53 pm
Evert Glebbeek Sat Mar 30, 2013 2:03 pm
H.G.Muller Sat Mar 30, 2013 2:26 pm
Sven Schüle Sat Mar 30, 2013 6:38 pm
H.G.Muller Sat Mar 30, 2013 8:13 pm
Sven Schüle Sat Mar 30, 2013 8:58 pm
H.G.Muller Sat Mar 30, 2013 10:58 pm
Sven Schüle Sat Mar 30, 2013 11:51 pm
H.G.Muller Sun Mar 31, 2013 7:35 am
Sven Schüle Sun Mar 31, 2013 9:02 am
H.G.Muller Sun Mar 31, 2013 9:09 am
Sven Schüle Sun Mar 31, 2013 9:13 am
Steven Edwards Mon May 13, 2013 2:14 am
Don Dailey Mon May 13, 2013 2:20 am
Chan Rasjid Sat Mar 30, 2013 12:18 pm
H.G.Muller Sat Mar 30, 2013 9:08 am
Chan Rasjid Sun May 12, 2013 10:27 pm
Ronald de Man Sun May 12, 2013 11:11 pm
Chan Rasjid Mon May 13, 2013 7:39 am
Don Dailey Mon May 13, 2013 2:14 am
Steven Edwards Tue May 14, 2013 7:19 am
Chan Rasjid Tue May 14, 2013 2:45 pm
Chan Rasjid Tue May 14, 2013 2:50 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumChess Players ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum