How to implement KPK ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

How to implement KPK ?

Post by Chan Rasjid » 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: 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 &#40;x <= y + 1&#41; &#123;
        /* pawn king wins; P now safe; */
        ;
    &#125; else &#123;
        /* P fails to promote; pawn king fails to protect pawn; 
         * draw
         *   */
        return 1;
    &#125;

    x = v5Pawn
            - DIST&#40;P, promSq&#41; * 10
            - DIST&#40;pK, P&#41; * 5
            + DIST&#40;loneK, P&#41; * 5
            - DIST&#40;pK, promSq&#41; * 2
            + DIST&#40;loneK, promSq&#41; * 2
            - &#40;loneK == pFrontSq || loneK == pFrontFrontSq&#41; * 10
            - (&#40;pCol ? loneK == pK - 2 &#58; loneK == pK + 2&#41;) * 10; /* kings in opposition */

    return &#40;pOnMove ? x &#58; -x&#41;;
&#125;

Best Regards,
Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: How to implement KPK ?

Post by hgm » Thu Mar 21, 2013 7:46 am

Why not just use the bitbase? It is only 64KB.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: How to implement KPK ?

Post by Chan Rasjid » Thu Mar 21, 2013 8:27 am

hgm wrote:Why not just use the bitbase? It is only 64KB.
Because there is no free lunch :D

Though magic bitboard move generation should be the best, there is no codes that is in the public domain. I am still using my rotated birboard.

Same for bitbase.

Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: How to implement KPK ?

Post by hgm » Thu Mar 21, 2013 10:07 am

You could write your own code to generate it, and put it in the public domain. :idea:

That seems simpler, and much less bug-prone then the code you are trying to write now.

Let me make a first attempt. (Completely untested...)

Code: Select all

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

#define WTM 0
#define BTM 1

char dtc&#91;2&#93;&#91;64&#93;&#91;64&#93;&#91;64&#93;; // 512 KB
char bitbase&#91;2*62*64*6&#93;;

char steps&#91;&#93; = &#123;1, -1, 16, -16, 15, -15, 17, -17&#125;;
void
Init ()
&#123;
  int wk, bk, p;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    if&#40;bk == wk&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1, dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;wk == p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;bk ==  p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; else // with WTM black just captured P
    if&#40;p >= 56&#41; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; // promoted and on move = win
  &#125;
&#125;

void
BlackPass ()
&#123;
  int wk, bk, p, d;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    int O88 = &#40;bk & 070&#41; + bk; // 0x88 square number
    if&#40;dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93;) continue; // already decided
    dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; // assume lost, if no escape will be found
    for&#40;d=0; d<8; d++) &#123;
      int to = O88 + steps&#91;d&#93;;
      if&#40;to & 0x88&#41; continue; // off board
      if&#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;to&#93; <= 0&#41; &#123; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 0; break; &#125; // escape
    &#125;
  &#125;
&#125;

void
WhitePass ()
&#123;
  int wk, bk, p, d;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    int O88 = &#40;wk & 070&#41; + wk; // 0x88 square number
    if&#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93;) continue; // already decided
    if&#40;bk != p&#41; &#123; // pawn not captured, so can move
      if&#40;p+8 != bk && dtc&#91;BTM&#93;&#91;wk&#93;&#91;p+8&#93;&#91;bk&#93; > 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+7 == bk && &#40;p & 7&#41; != 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+9 == bk && &#40;p & 7&#41; != 7&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
    &#125;
    for&#40;d=0; d<8; d++) &#123;
      int to = O88 + steps&#91;d&#93;;
      if&#40;to & 0x88&#41; continue; // off board
      if&#40;dtc&#91;BTM&#93;&#91;to&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; break; &#125;
    &#125;
  &#125;
&#125;

void
Pack ()
&#123;
  int wk, bk, p, i;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=8; p<56; p++) &#123;
    int index = &#40;bk >> 3&#41; + 8*wk + 8*64*&#40;p-8&#41;;
    bitbase&#91;2*index&#93; |= &#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
    bitbase&#91;2*index+1&#93; |= &#40;dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
  &#125;
&#125;

void
Build ()
&#123;
  int i;
  Init&#40;);
  for&#40;i=0; i<100; i++) // won't take more than 100 moves
    WhitePass&#40;), BlackPass&#40;);
  Pack&#40;);
&#125;

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: How to implement KPK ?

Post by hgm » Thu Mar 21, 2013 10:33 am

The white pass and black pass look very similar, so perhaps it is more elegant to merge them into one routine:

Code: Select all

void
Pass &#40;int stm&#41;
&#123;
  int wk, bk, p, d;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    int k = stm == WTM ? wk &#58; bk
    int O88 = &#40;k & 070&#41; + k; // 0x88 square number of King
    if&#40;dtc&#91;stm&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93;) continue; // already decided
    dtc&#91;stm&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = stm;  // assume lost if btm, undecided if wtm
    if&#40;bk != p && stm == WTM&#41; &#123; // pawn not captured, so can move
      if&#40;p+8 != bk && dtc&#91;BTM&#93;&#91;wk&#93;&#91;p+8&#93;&#91;bk&#93; > 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+7 == bk && &#40;p & 7&#41; != 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+9 == bk && &#40;p & 7&#41; != 7&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
    &#125;
    for&#40;d=0; d<8; d++) &#123;
      int to = O88 + steps&#91;d&#93;;
      if&#40;to & 0x88&#41; continue; // off board
      if&#40;stm == WTM ? dtc&#91;BTM&#93;&#91;to&#93;&#91;p&#93;&#91;bk&#93; > 0 &#58; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;to&#93; > 0&#41;
      &#123; dtc&#91;stm&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = !stm; break; &#125;
    &#125;
  &#125;
&#125;

void
Build ()
&#123;
  int i;
  Init&#40;);
  for&#40;i=0; i<100; i++) // won't take more than 100 moves
    Pass&#40;WTM&#41;, Pass&#40;BTM&#41;;
  Pack&#40;);
&#125;
I guess the bk == p positions should be set to -1 in Init(), and not to 1; the Pass() code does not ever test the state of the daughter position in dtc when it captures the black King with a Pawn, but just assigns a win. So the only testing of this position that ever is important is when the black King stepped onto the Pawn, whether on the previous ply or longer before that. The btm cases have to be marked as draw, to prevent black being forced to 'step off' the Pawn again by zugzwang when white does not have a King move to capture the black King, and tries another one.

User avatar
lucasart
Posts: 2957
Joined: Mon May 31, 2010 11:29 am
Contact:

Re: How to implement KPK ?

Post by lucasart » Thu Mar 21, 2013 11:03 am

hgm wrote:Why not just use the bitbase? It is only 64KB.
mine is 24 KB: 64*64*24*2 = 24576 * 8 bits = 24 KB. But it's not public domain and never will be: GPL stays GPL, that's the whole point of it.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: How to implement KPK ?

Post by hgm » Thu Mar 21, 2013 11:52 am

Ah, you make use of left-right symmetry. Nice idea. I now did that too, by adding a >>1 to the Pawn square during packing, and incrementing it in steps of 2. This should throw away all positions where the Pawn is on an odd file. (A bit wasteful, as the generation still uses the full set of positions, but the assumption was this would be infinitely fast anyway, or that speed would not be important because you save it on a file.)

The following code is tested in the sense that it compiles (there was a missing semicolon), and runs without segfaulting (I had forgotten to convert the 0x88 to-square back to a normal square index.)

Code: Select all

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

#define WTM 0
#define BTM 1

char dtc&#91;2&#93;&#91;64&#93;&#91;64&#93;&#91;64&#93;; // 512 KB
char bitbase&#91;2*64*64*3&#93;;

char steps&#91;&#93; = &#123;1, -1, 16, -16, 15, -15, 17, -17&#125;;

void
Init ()
&#123;
  int wk, bk, p;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    if&#40;bk == wk&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1, dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;wk == p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;bk ==  p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else // with WTM black just captured P
    if&#40;p >= 56&#41; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; // promoted and on move = win
  &#125;
&#125;

void
Pass &#40;int stm&#41;
&#123;
  int wk, bk, p, d;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    int k = stm == WTM ? wk &#58; bk;
    int O88 = &#40;k & 070&#41; + k; // 0x88 square number of King
    if&#40;dtc&#91;stm&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93;) continue; // already decided
    dtc&#91;stm&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = stm;  // assume lost if btm, undecided if wtm
    if&#40;bk != p && stm == WTM&#41; &#123; // pawn not captured, so can move
      if&#40;p+8 != bk && dtc&#91;BTM&#93;&#91;wk&#93;&#91;p+8&#93;&#91;bk&#93; > 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+7 == bk && &#40;p & 7&#41; != 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+9 == bk && &#40;p & 7&#41; != 7&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
    &#125;
    for&#40;d=0; d<8; d++) &#123;
      int to = O88 + steps&#91;d&#93;;
      if&#40;to & 0x88&#41; continue; // off board
      to -= to>>1 & 070;
      if&#40;stm == WTM ? dtc&#91;BTM&#93;&#91;to&#93;&#91;p&#93;&#91;bk&#93; > 0 &#58; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;to&#93; > 0&#41;
      &#123; dtc&#91;stm&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = !stm; break; &#125;
    &#125;
  &#125;
&#125;

void
Pack ()
&#123;
  int wk, bk, p, i;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=8; p<56; p+=2&#41; &#123;
    int index = &#40;bk >> 3&#41; + 8*wk + 8*64*&#40;p-8>>1&#41;;
    bitbase&#91;2*index&#93; |= &#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
    bitbase&#91;2*index+1&#93; |= &#40;dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
  &#125;
&#125;

void
Build ()
&#123;
  int i;
  Init&#40;);
  for&#40;i=0; i<100; i++) // won't take more than 100 moves
    Pass&#40;WTM&#41;, Pass&#40;BTM&#41;;
  Pack&#40;);
&#125;
When I run it, it prints

Code: Select all

white to move&#58; 211980+, 23085=, 27079-
black to move&#58; 140386+, 113694=, 8064-
where = and - together count the non-won positions (which are not properly distinguished by the algorithm), and + the number of listed wins.

[Edit] O, I guess it still needs a stalemate correction.

User avatar
lucasart
Posts: 2957
Joined: Mon May 31, 2010 11:29 am
Contact:

Re: How to implement KPK ?

Post by lucasart » Thu Mar 21, 2013 12:04 pm

hgm wrote:Ah, you make use of left-right symmetry. Nice idea.
This is no idea of mine. It's a great classic, and rather trivial. Many have done it before me. Some might have done it even before I was born :wink:
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: How to implement KPK ?

Post by Chan Rasjid » Thu Mar 21, 2013 6:10 pm

hgm wrote:You could write your own code to generate it, and put it in the public domain. :idea:

That seems simpler, and much less bug-prone then the code you are trying to write now.

Let me make a first attempt. (Completely untested...)

Code: Select all

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

#define WTM 0
#define BTM 1

char dtc&#91;2&#93;&#91;64&#93;&#91;64&#93;&#91;64&#93;; // 512 KB
char bitbase&#91;2*62*64*6&#93;;

char steps&#91;&#93; = &#123;1, -1, 16, -16, 15, -15, 17, -17&#125;;
void
Init ()
&#123;
  int wk, bk, p;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    if&#40;bk == wk&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1, dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;wk == p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;bk ==  p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; else // with WTM black just captured P
    if&#40;p >= 56&#41; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; // promoted and on move = win
  &#125;
&#125;

void
BlackPass ()
&#123;
  int wk, bk, p, d;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    int O88 = &#40;bk & 070&#41; + bk; // 0x88 square number
    if&#40;dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93;) continue; // already decided
    dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; // assume lost, if no escape will be found
    for&#40;d=0; d<8; d++) &#123;
      int to = O88 + steps&#91;d&#93;;
      if&#40;to & 0x88&#41; continue; // off board
      if&#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;to&#93; <= 0&#41; &#123; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 0; break; &#125; // escape
    &#125;
  &#125;
&#125;

void
WhitePass ()
&#123;
  int wk, bk, p, d;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=0; p<64; p++) &#123;
    int O88 = &#40;wk & 070&#41; + wk; // 0x88 square number
    if&#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93;) continue; // already decided
    if&#40;bk != p&#41; &#123; // pawn not captured, so can move
      if&#40;p+8 != bk && dtc&#91;BTM&#93;&#91;wk&#93;&#91;p+8&#93;&#91;bk&#93; > 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+7 == bk && &#40;p & 7&#41; != 0&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
      if&#40;p+9 == bk && &#40;p & 7&#41; != 7&#41;  &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; continue; &#125;
    &#125;
    for&#40;d=0; d<8; d++) &#123;
      int to = O88 + steps&#91;d&#93;;
      if&#40;to & 0x88&#41; continue; // off board
      if&#40;dtc&#91;BTM&#93;&#91;to&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; &#123; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; break; &#125;
    &#125;
  &#125;
&#125;

void
Pack ()
&#123;
  int wk, bk, p, i;
  for&#40;wk=0; wk<64; wk++) for&#40;bk=0; bk<64; bk++) for&#40;p=8; p<56; p++) &#123;
    int index = &#40;bk >> 3&#41; + 8*wk + 8*64*&#40;p-8&#41;;
    bitbase&#91;2*index&#93; |= &#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
    bitbase&#91;2*index+1&#93; |= &#40;dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
  &#125;
&#125;

void
Build ()
&#123;
  int i;
  Init&#40;);
  for&#40;i=0; i<100; i++) // won't take more than 100 moves
    WhitePass&#40;), BlackPass&#40;);
  Pack&#40;);
&#125;
As Deng Xiaopeng said: "It does not matter if a cat is red or black as long as it catches the mouse" - but don't take too long.

As Dr. Robert Hyatt said: "In my forty years in computer chess, I have yet to see a game that played to a KPK ending." - but there is always a tomorrow.

As Herr Muller said: "I have already put the KPK bitbase generator in the public domain. If you don't understand simple retrograde analysis starting from the promotion squares and about the concept of un-make, you should not be in chess programming. Go! Join a choir and make some sound!" - don't be too certain that that someone would't be signed up by Sony later.

As another said:"If your program can't outplay Houdini 5, don't give the excuse that it is because you have no KPK bitbase or that you discovered a bug in your KPK routine. Just say - ' Robert is really a genius'"

It does not matter very much if I use the KPK bitbase. If there is a bug in my search, then it will still not be able to play a KPK ending.

Best Regards,
Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: How to implement KPK ?

Post by hgm » Thu Mar 21, 2013 6:36 pm

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: Select all

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

#define WTM 0
#define BTM 1

char dtc&#91;2&#93;&#91;64&#93;&#91;64&#93;&#91;64&#93;; // 512 KB
char bitbase&#91;2*64*64*3&#93;;

char steps&#91;&#93; = &#123;1, -1, 16, -16, 15, -15, 17, -17&#125;; // 0x88 King steps

void
Init ()
&#123; /* 3 = bK captured, 2 = can capture bK, 1 = won, 0 = undecided, -1 = broken or wK captured */
  int wk, bk, p;
  for&#40;wk=0; wk<64; wk++) for&#40;p=0; p<64; p++) for&#40;bk=0; bk<64; bk++) &#123;
    if&#40;bk == wk&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 3, dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;wk == p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -1; else
    if&#40;bk ==  p&#41; dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = -3; else // with WTM black just captured P
    if&#40;p >= 56&#41; dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; = 1; // promoted and on move = win
  &#125;
&#125;

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

void
Pack ()
&#123;
  int wk, bk, p, i;
  for&#40;wk=0; wk<64; wk++) for&#40;p=8; p<56; p+=2&#41; for&#40;bk=0; bk<64; bk++) &#123; // calculate probe address and bit
    int index = &#40;bk >> 3&#41; + 8*wk + 8*64*&#40;p-8>>1&#41;;
    bitbase&#91;2*index&#93; |= &#40;dtc&#91;WTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
    bitbase&#91;2*index+1&#93; |= &#40;dtc&#91;BTM&#93;&#91;wk&#93;&#91;p&#93;&#91;bk&#93; > 0&#41; << &#40;bk & 7&#41;;
  &#125;
&#125;

void
Build ()
&#123;
  int i;
  Init&#40;);
  Pass&#40;WTM, 2, 0, 2&#41;; Pass&#40;BTM, 1, -2, 0&#41;; // calculate King captures and 

stalemates
  for&#40;i=0; i<25; i++) // won't take more than 25 moves
    Pass&#40;WTM, 0, 0, 1&#41;, Pass&#40;BTM, 0, 1, 0&#41;;
  Pack&#40;);
&#125;
Printing the stats of the positions with the Pawn on rank 2-7 afterwards gives:

Code: Select all

white to move&#58; 124960+, 41044=, 6096-, 0 stalemate, 24508 K-capture
black to move&#58; 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.)

Post Reply