How to implement KPK ?

[hgm]

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 (int stm)
{
  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.

[lucasart]

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.

[hgm]

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[2][64][64][64]; // 512 KB
char bitbase[2*64*64*3];

char steps[] = {1, -1, 16, -16, 15, -15, 17, -17};

void
Init ()
{
  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: 211980+, 23085=, 27079-
black to move: 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.

[lucasart]

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

[Chan Rasjid]

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

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[2][64][64][64]; // 512 KB
char bitbase[2*62*64*6];

char steps[] = {1, -1, 16, -16, 15, -15, 17, -17};
void
Init ()
{
  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.

[hgm]

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[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&#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: 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.)

[hgm]

From probing a few hundred randomly generated positions I could not find an error. So it seems the code is OK.

[Chan Rasjid]

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[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&#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: 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: Select all

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.

[Evert]

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.

Returning a draw is fine when you detect that the position is a draw, but I wouldn't do anything if the position is not a draw. You already know that the position is either drawn or won, so if it isn't drawn what you have to do is make sure that the engine makes progress towards winning. You do that with just the regular scoring of passed pawns/king position in the end game. The engine will then automatically seek out lines where the pawn is advanced and eventually promotes (by the way, make sure you get the value of a passed pawn that is about to promote right; if it's too high the engine may prefer to keep the pawn around rather than promote it). Introducing a "bonus" for having a won position will confuse things and may cause problems if you don't always give that bonus in a won position (as per above: the engine could prefer keeping the pawn around because it sees promoting the pawn as a drop in score).

[hgm]

If they already play the right moves at low depth they must have knowledge (like a hefty bonus for King in front of Pawn, or for having opposition). They will all have a bonus for advancing the Pawn, and the quickest way to do that is supporting it with your King from behind, which is of course exactly what draws. But there is no way for the engine to see it draws before it actually reaches all the way across the board, which takes more depth.

Fairy-Max is a good example of what you get without any specific knowledge:

Code: Select all

 26   +8.20   10.9M   0:18.73   e1f2 e8f8 f2e3 f8g7 e3d4 g7f6 d4e4 f6e6
 25   +1.85   4.4M   0:08.19   e1f2 e8f8 f2e3 f8e7
 24   +1.86   4.0M   0:07.43   e1f2 e8d7 f2e3 d7e7 e3f4 e7e6 f4e4 e6d6 e4f5
 23   +1.86   3.6M   0:06.83   e1f2 e8d7 f2e3 d7e7 e3f4 e7e6 f4e4 e6d6 e4d4
 22   +1.87   3.0M   0:05.72   e1f2 e8d7 f2e3 d7e7 e3f4 e7d6 f4f5 d6e7 e2e4
 21   +1.90   2.0M   0:04.15   e1f2 e8d7 f2e3 d7d6 e3d4 d6e6 e2e4 e6d6 e4e5 d6e6 d4e4 e6e7 e4f5 e7d7
 20   +1.93   1.3M   0:02.88   e1f2 e8d7 f2e3 d7d6 e3d4 d6e6 e2e4 e6d6 e4e5 d6e7 d4e4 e7e6
 19   +1.51   761909   0:01.94   e1f2 e8d7 f2e3 d7d6 e3f4 d6e6 e2e3 e6f6 e3e4 f6g6 e4e5 g6g7 f4f5 g7f7 e5e6 f7e7 f5e5 e7e8 e5e4
 18   +1.48   612798   0:01.66   e1f2 e8d7 f2e3 d7d6 e3f4 d6e6 e2e4 e6f6 e4e5 f6e6 f4e4 e6e7 e4f5
 17   +1.44   478310   0:01.39   e1f2 e8d7 f2e3 d7d6 e3f4 d6d5 e2e4 d5d6 f4f5 d6e7 e4e5 e7f7 f5f4
 16   +1.44   322845   0:01.10   e1f2 e8d7 f2e3 d7d6 e3f4 d6d5 e2e4 d5d6 f4f5 d6c5
 15   +1.32   220508   0:00.88   e1f2 e8d7 f2e3 d7d6 e3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4 e6e7 e4f5 e7f7 e5e6
 14   +0.94   180226   0:00.74   e1f2 e8d7 f2e3 d7d6 e3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4
 14   +0.80   140703   0:00.59   e1d1 e8e7 e2e4 e7e6 d1e2
 14   +0.79   127866   0:00.54   e1f1 e8e7 e2e4 e7f7 f1e2 f7e6 e2f2 e6f6 f2e3
 13   +0.85   110176   0:00.47   e1f1 e8e7 e2e4 e7e6 f1e2 e6e5
 13   +0.83   99812   0:00.43   e2e3 e8f7 e1e2 f7f6 e3e4 f6e6 e2f2 e6e5 f2e3
 12   +0.80   88763   0:00.38   e2e3 e8f7 e1d2 f7e6 e3e4 e6e5 d2e3 e5f6 e3f2 f6e6
 12   +0.71   72541   0:00.30   e1f2
 12   +0.70   69094   0:00.28   e1f2 e8e7 f2e3 e7f6 e3f4 f6e6 e2e4 e6f6 e4e5 f6e6 f4e4 e6e7
 11   +0.87   47144   0:00.18   e1f2 e8e7 f2f3 e7e6 f3f4 e6d5 e2e4 d5d4 e4e5 d4d5
 10   +0.82   35746   0:00.15   e1f2 e8e7 f2f3 e7f6 f3g4 f6e5 g4g5 e5e4 g5f6 e4f4
 10   +0.75   30842   0:00.13   e1f1 e8f7 e2e4 f7e6 f1e2 e6e5 e2f3
  9   +0.75   26114   0:00.11   e1f1 e8f7 f1f2 f7f6 e2e4 f6e5 f2f3
  9   +0.66   20762   0:00.09   e1d2 e8d8 e2e4 d8d7 d2d3 d7e6
  8   +0.90   10710   0:00.06   e1d2 e8e7 d2d3 e7e6 d3e4 e6f6 e2e3 f6e6
  7   +0.94   8916   0:00.06   e1d2 e8e7 d2d3 e7f6 d3d4 f6f5
  7   +0.83   5931   0:00.03   e1f2 e8e7 e2e4 e7e6 f2e3 e6e5 e3f3
  7   +0.81   5386   0:00.01   e1f1 e8e7 e2e4 e7f6 f1g2 f6e6
  7   +0.77   3874   0:00.01   e1d1 e8e7 e2e4 e7e6 d1d2 e6e5 d2e3
  6   +0.74   2188   0:00.00   e1d1 e8e7 e2e4 e7e6 d1d2 e6e5
  6   +0.73   1912   0:00.00   e1f2 e8e7 e2e4 e7e6 f2e3 e6e5
  5   +0.92   1029   0:00.00   e1f2 e8e7 e2e4 e7e6 f2e3
  5   +0.71   759   0:00.00   e1d1 e8e7 e2e4 e7e6 d1e2
  4   +0.75   429   0:00.00   e1d1 e8e7 e2e4 e7e6
  4   +0.71   364   0:00.00   e1f1 e8e7 e2e4 e7e6
  4   +0.60   293   0:00.00   e1d2 e8e7 e2e4 e7e6
  3   +0.90   192   0:00.00   e1d2 e8e7 e2e4
  3   +0.84   158   0:00.00   e1f2 e8e7 e2e4
  3   +0.64   126   0:00.00   e1f1 e8e7 e2e4
  3   +0.59   89   0:00.00   e1d1 e8e7 e2e4
  2   +0.78   35   0:00.00   e1d1 e8e7
  2   +0.74   17   0:00.00   e1f2 e8e7
  1   +0.84   9   0:00.00   e1f2 

You can see that it considers many drawing moves (Kf1, Kd1, e3) before it finally sees the promotion.