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: Re: How to implement KPK ?    Posted: Sat Mar 30, 2013 8:15 am Reply to topic Reply with quote

hgm wrote:
I see KPK quite often.

Anyway, to further the public-domain cause, the following code actually runs, and prints some numbers that seem to make sense (like the number of stalemates, which matches what I calculated by hand). I even put in the initial double-push, which is important for rule-of-squares situations.

Btw, this is the dumb algorithm, which does not use any unmoves. It just attempts regular moving from all not-yet-decided positions, to look for a move to a won position for white, and to a non-lost position for black.

Code:
/* Public-domain KPK bitbase code by H.G. Muller */

#define WTM 0
#define BTM 1

char dtc[2][64][64][64]; // 512 KB
char bitbase[2*64*64*3];

char steps[] = {1, -1, 16, -16, 15, -15, 17, -17}; // 0x88 King steps

void
Init ()
{ /* 3 = bK captured, 2 = can capture bK, 1 = won, 0 = undecided, -1 = broken or wK captured */
  int wk, bk, p;
  for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) {
    if(bk == wk) dtc[BTM][wk][p][bk] = 3, dtc[WTM][wk][p][bk] = -1; else
    if(wk == p) dtc[BTM][wk][p][bk] = dtc[WTM][wk][p][bk] = -1; else
    if(bk ==  p) dtc[BTM][wk][p][bk] = -3; else // with WTM black just captured P
    if(p >= 56) dtc[WTM][wk][p][bk] = 1; // promoted and on move = win
  }
}

void
Pass (int stm, int first, int def, int esc)
{
  int wk, bk, p, d;
  for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) {
    int k = stm == WTM ? wk : bk;
    int O88 = (k & 070) + k; // 0x88 square number of King
    if(dtc[stm][wk][p][bk]) continue; // already decided
    dtc[stm][wk][p][bk] = def;  // assume lost if btm, undecided if wtm
    if(bk != p && stm == WTM) { // pawn not captured, so can move
      if(p+8 != bk && (dtc[BTM][wk][p+8 ][bk] > first || p < 16 &&
         p+16 != bk && dtc[BTM][wk][p+16][bk] > first))  { dtc[WTM][wk][p][bk] = esc; continue; }
      if(p+7 == bk && (p & 7) != 0)  { dtc[WTM][wk][p][bk] = 2; continue; }
      if(p+9 == bk && (p & 7) != 7)  { dtc[WTM][wk][p][bk] = 2; continue; }
    }
    for(d=0; d<8; d++) {
      int to = O88 + steps[d];
      if(to & 0x88) continue; // off board
      to -= to>>1 & 070;
      if(stm == WTM ? dtc[BTM][to][p][bk] > first : dtc[WTM][wk][p][to] <= first)
      { dtc[stm][wk][p][bk] = esc; break; }
    }
  }
}

void
Pack ()
{
  int wk, bk, p, i;
  for(wk=0; wk<64; wk++) for(p=8; p<56; p+=2) for(bk=0; bk<64; bk++) { // calculate probe address and bit
    int index = (bk >> 3) + 8*wk + 8*64*(p-8>>1);
    bitbase[2*index] |= (dtc[WTM][wk][p][bk] > 0) << (bk & 7);
    bitbase[2*index+1] |= (dtc[BTM][wk][p][bk] > 0) << (bk & 7);
  }
}

void
Build ()
{
  int i;
  Init();
  Pass(WTM, 2, 0, 2); Pass(BTM, 1, -2, 0); // calculate King captures and

stalemates
  for(i=0; i<25; i++) // won't take more than 25 moves
    Pass(WTM, 0, 0, 1), Pass(BTM, 0, 1, 0);
  Pack();
}


Printing the stats of the positions with the Pawn on rank 2-7 afterwards gives:

Code:
white to move: 124960+, 41044=, 6096-, 0 stalemate, 24508 K-capture
black to move: 97604+, 89866=, 6066-, 18 stalemate, 0 K-capture


where + means won to white, = means draw, - illegal by white's fault or black stalemated. (White stalemates are not separately identified, they count with the other draws.)

Muller's public domain kpk bitbase generator should be working. I probe the bitbase for a few kpk positions and they are in agreement with match results when the positions are played by stockfish vs komodo.

The various programs I have all could play kpk endings perfectly. Even the weakest, simplex, which is about at the level of my engine, could do so. I noticed that when these engines analyse a typical kpk position, the PV remains almost unchanged (the first four moves) from a very early depth of 9 or 10 till 30 or more plies. But my implementation of the kpk evaluation is still not working. In analysis mode, the PV keeps changing.

My kpk evaluation returns 0/1 when it is a draw. If a win, it will return 5 x pawn and some simple evaluation terms. Maybe, someone who have implemented kpk sucessfully may check my codes to see if it should work. If it should work, then it means there are bugs in my search that somehow escaped detection.

The code for my kpk evaluator has the probe codes for Muller's bitbase:
Code:

int evalkpk(const int side) {
    const int pCol = !bits[0][Pawn];
    const int pOnMove = (pCol == side);
    const int pK = king[pCol], loneK = king[pCol ^ 1], p = firstone(bits[pCol][Pawn]);
    int probeWk, probeBk, probeWp;
    int win, index, stm;

    if (kMap[king[side]] & bits[side ^ 1][Pawn] & ~kMap[king[side ^ 1]]) {
        /* insurance - safe capture of pawn */
        return 1;
    }

    /* probe kpk bitbase (as white with the pawn) */
    if (pCol == 0) {
        /* my internal chess board square mapping is unusual, (a1, a2, a3,...) -> (0, 1, 2, ...)
         * convert to mapping of bitbase */
        probeWk = sqMapA1B1[pK];
        probeBk = sqMapA1B1[loneK];
        probeWp = sqMapA1B1[p];
        stm = side;
    } else {
        /* flip everything  */
        probeWk = 63 - sqMapA1B1[pK];
        probeBk = 63 - sqMapA1B1[loneK];
        probeWp = 63 - sqMapA1B1[p];
        stm = side ^ 1;
    }

    index = 2 * ((probeBk >> 3) + 8 * probeWk + 8 * 64 * ((probeWp - 8) >> 1)) + 1 * stm;
    /* probe bitbase; 1 == win, 0 == draw */
    win = (bitbase[index] >> (probeBk & 7)) & 1;

    if (!win) {
        return 1;
    }

    const int promSq = PROMOTE_SQ(p, pCol);
    const int pFrontSq = pCol ? p - 1 : p + 1;
   
    int x = v5Pawn
            - DIST(p, promSq)
            - (pFrontSq == loneK ? 8 : 0)
            - (DIST(pK, p) > DIST(loneK, p) ? 8 : -8)
            - (DIST(pK, pFrontSq) > DIST(loneK, pFrontSq) ? 8 : -8)
            - (DIST(pK, promSq) > DIST(loneK, promSq) ? 16 : -16);

    ASSERT_COLOR_SYMM(side ? (pCol ? x : -x) : (pCol ? -x : x));
    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