ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

How to implement KPK ?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Chan Rasjid



Joined: 09 Mar 2006
Posts: 567
Location: Singapore

PostPost subject: How to implement KPK ?    Posted: Thu Mar 21, 2013 3:43 am Reply to topic Reply with quote

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.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 3:43 am
      Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 7:46 am
            Re: How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 8:27 am
                  Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 10:07 am
                        Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 10:33 am
                        Re: How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 6:10 pm
                              Re: How to implement KPK ? Don Dailey Tue Apr 02, 2013 6:56 pm
            Re: How to implement KPK ? Lucas Braesch Thu Mar 21, 2013 11:03 am
                  Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 11:52 am
                        Re: How to implement KPK ? Lucas Braesch Thu Mar 21, 2013 12:04 pm
                        Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 6:36 pm
                              Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 9:00 pm
                              Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 8:15 am
                                    Re: How to implement KPK ? Evert Glebbeek Sat Mar 30, 2013 8:42 am
                                          Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 12:12 pm
                                                Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 12:20 pm
                                                      Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 12:42 pm
                                                            Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 2:03 pm
                                                                  Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 6:29 pm
                                                      Re: How to implement KPK ? Wylie Garvin Sat Mar 30, 2013 12:50 pm
                                                            Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 1:53 pm
                                                Re: How to implement KPK ? Evert Glebbeek Sat Mar 30, 2013 2:03 pm
                                                      Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 2:26 pm
                                                            Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 6:38 pm
                                                                  Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 8:13 pm
                                                                        Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 8:58 pm
                                                                              Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 10:58 pm
                                                                                    Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 11:51 pm
                                                                                          Re: How to implement KPK ? H.G.Muller Sun Mar 31, 2013 7:35 am
                                                                                          Re: How to implement KPK ? Sven Schüle Sun Mar 31, 2013 9:02 am
                                                                                          Re: How to implement KPK ? H.G.Muller Sun Mar 31, 2013 9:09 am
                                                                                          Re: How to implement KPK ? Sven Schüle Sun Mar 31, 2013 9:13 am
                                                                                          Re: How to implement KPK ? Steven Edwards Mon May 13, 2013 2:14 am
                                                                                          Re: How to implement KPK ? Don Dailey Mon May 13, 2013 2:20 am
                                          Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 12:18 pm
                                    Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 9:08 am
      Re: How to implement KPK ? Chan Rasjid Sun May 12, 2013 10:27 pm
            Re: How to implement KPK ? Ronald de Man Sun May 12, 2013 11:11 pm
                  Re: How to implement KPK ? Chan Rasjid Mon May 13, 2013 7:39 am
            Re: How to implement KPK ? Don Dailey Mon May 13, 2013 2:14 am
            Re: How to implement KPK ? Steven Edwards Tue May 14, 2013 7:19 am
                  Re: How to implement KPK ? Chan Rasjid Tue May 14, 2013 2:45 pm
                        Re: How to implement KPK ? Chan Rasjid Tue May 14, 2013 2:50 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
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




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads