How to implement KPK ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: How to implement KPK ?

Post by Don » Mon May 13, 2013 2:14 am

My KPk routine scores win and draw but also superimposes a positional score which is calculated special for this ending. It's probably overkill but is a vestige of the early days when computers could not search very deeply. What I do is give a little incentive for king and pawn advancement so that even on a 1 ply search it won't flounder around.

On a really shallow search a program can paint itself into a corner where it falls into a repetition and runs itself out of winning moves. It can never return to a previous position without it being scored as a draw by repetition.

Chan Rasjid wrote:Finally, I am able to get my KPK routine to work just as 'perfectly' as how all other programs play the KPK endings. I am using the KPK bitbase which Gert Mueller put up in the public domain. So it seems all fine - should have no bugs. Many thanks to Gert.

It was exasperating trying to get my KPK codes to work. With bitases, it should be simple to implement the KPK routine. Basically, it is to return zero when probe to bitbase shows a draw. For a win, what I found needed is just to evaluate the distance to promotion for the pawn. The other evaluation is just that the lone king stays clear from the pawn and the promotion square. It is this simple. Yet it was not working!

What actually made it work this time around is I disabled all the lines of codes that involves fifty and repetition draws in my search functions. I think there are bugs. I have yet to examine what was wrong.

There is something that need to be noted about the KPK routine. For some 'difficult' KPK endings, it seems necessary to have the two pawn/lone king race to promotion and also the Kings' race to get near the pawn. Without these coding, the play may fail. I don't clearly know the reason yet.

My evalKPK() codes is here:

Code: Select all

int evalkpk(const int side) {
    const int pcol = !bits[0][Pawn], xpcol = pcol ^ 1;
    const int pK = king[pcol], loneK = king[xpcol], p = firstone(bits[pcol][Pawn]);
    const int promsq = PROMOTE_SQ(p, pcol);
    int probeWk, probeBk, probeWp;
    int win, index, stm;
    int x, d1, d2;

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

    /* pawn/loneK race to promote. */
    if (!(FORWARD_ROW_BITS(p, pcol) & rMap[p]->file & bits[pcol][King])) {
        /* path ahead clear */
        d1 = DIST(p, promsq);
        d2 = DIST(loneK, promsq) - (side ^ pcol);
        if (d2 > d1) {
            /* promote success */
            x = v8Pawn - DIST(p, promsq);
            return (side == pcol ? x : -x);
        }
    }

    /* kings' race to protect pawn. */
    d1 = DIST(p, pK);
    d2 = DIST(p, loneK) - (side ^ pcol);

    if &#40;d1 <= d2 + 1&#41;; /* protect success */
    else &#123;
        /* pawn lost */
        x = 2 + d2;
        return &#40;side == pcol ? x &#58; -x&#41;;
    &#125;

    /* probe kpk bitbase &#40;as white with the pawn&#41; */
    if &#40;pcol == 0&#41; &#123;
        /* my internal chess board square mapping is unusual, &#40;a1, a2, a3,...) -> &#40;0, 1, 2, ...)
         * convert to mapping of bitbase */
        probeWk = sqMapA1B1&#91;pK&#93;;
        probeBk = sqMapA1B1&#91;loneK&#93;;
        probeWp = sqMapA1B1&#91;p&#93;;
        stm = side;
    &#125; else &#123;
        /* flip everything  */
        probeWk = 63 - sqMapA1B1&#91;pK&#93;;
        probeBk = 63 - sqMapA1B1&#91;loneK&#93;;
        probeWp = 63 - sqMapA1B1&#91;p&#93;;
        stm = side ^ 1;
    &#125;

    index = 2 * (&#40;probeBk >> 3&#41; + 8 * probeWk + 8 * 64 * (&#40;probeWp - 8&#41; >> 1&#41;) + 1 * stm;
    /* probe bitbase; 1 == win, 0 == draw */
    win = &#40;bitbase&#91;index&#93; >> &#40;probeBk & 7&#41;) & 1;

    if (!win&#41; &#123;
        return &#40;side == pcol ? 2 &#58; -2&#41;;
    &#125;

    /* Now a win. The evaluation needed is this simple! */
    x = v7Pawn
            - 1 * DIST&#40;p, promsq&#41;
            + 4 * DIST&#40;loneK, p&#41;
            + 4 * DIST&#40;loneK, promsq&#41;;

    return &#40;side == pcol ? x &#58; -x&#41;;
This is a difficult KPK position which requires coding for the piece races:
[D]4k3/8/8/8/K7/8/4P3/8 w - - 5 1[/D]

Best Regards,
Rasjid.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: How to implement KPK ?

Post by Don » Mon May 13, 2013 2:20 am

sje wrote:Does KPK show up over the board? The real question here is: how frequently does KPK show up in the search tree. And the answer is: surprisingly often.

I have the complete DTM KPK tablebases for either side to move. They are FREE for anyone who might want to use them, as is the code needed to access them.
It may show up a lot in the tree, but from a pure programming improvement standpoint it has no measurable effect on the strength of the program. But I still really like having it in the program.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

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

Re: How to implement KPK ?

Post by Chan Rasjid » Mon May 13, 2013 7:39 am

syzygy wrote:
Chan Rasjid wrote:Finally, I am able to get my KPK routine to work just as 'perfectly' as how all other programs play the KPK endings. I am using the KPK bitbase which Gert Mueller put up in the public domain.
If you use a bitbase, why so much testing before you probe it?

Just probe it and if is a win, return a winning value that is a bit smaller than the value for K+Q versus K minus a value proportional to the distance of the pawn to promotion. If this does not work, don't hack your KPK routine further, but debug your search.
I think I understand what you mean.

Maybe it is just my natural instinct to harbour distrust - in the completeness of Gert Muller's bitbase :D

There is indeed a further search bug - or rather a search issue. I have a parameter for root search to return when the pv repeats N times. It was set to 16 and it was insufficient. Setting it to 32 is ok. But then this repeat of pv at root is an issue I have not settled on. If I disable it, it may just search till depth 64 and I don't like it too much.

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

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: How to implement KPK ?

Post by sje » Tue May 14, 2013 7:19 am

Chan Rasjid wrote:This is a difficult KPK position which requires coding for the piece races:
[D]4k3/8/8/8/K7/8/4P3/8 w - - 5 1[/D]
How can the half move counter be five when the full move number is one? The FEN input scanner should really check for this.

Anyways,
[d]4k3/8/8/8/K7/8/4P3/8 w - - 0 1[/d]

Symbolic says:

Code: Select all

&#91;&#93; dtbm
Ka3 Even
Ka5 Even
Kb3 MateIn23
Kb4 MateIn23
Kb5 MateIn23
e3 Even
e4 Even

&#91;&#93; dg
1 Kb3 Kd7 2 Kc3 Kc6 3 Kc4 Kd6 4 Kd4 Ke6 5 Ke4 Kd6 6 Kf5 Ke7 7 Ke5 Kd7 8 Kf6 Kc6
9 Ke6 Kb5 10 Kd6 Ka6 11 Kd7 Ka5 12 e4 Ka4 13 Kd6 Ka3 14 e5 Ka2 15 Kc5 Ka1 16
Kc4 Ka2 17 e6 Kb2 18 e7 Kc2 19 e8=Q Kd2 20 Qe4 Kc1 21 Kc3 Kd1 22 Qe5 Kc1 23
Qe1# 1-0

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

Re: How to implement KPK ?

Post by Chan Rasjid » Tue May 14, 2013 2:45 pm

Hello,
sje wrote:
Chan Rasjid wrote:This is a difficult KPK position which requires coding for the piece races:
[D]4k3/8/8/8/K7/8/4P3/8 w - - 5 1[/D]
How can the half move counter be five when the full move number is one? The FEN input scanner should really check for this.

Anyways,
[d]4k3/8/8/8/K7/8/4P3/8 w - - 0 1[/d]

Symbolic says:

Code: Select all

&#91;&#93; dtbm
Ka3 Even
Ka5 Even
Kb3 MateIn23
Kb4 MateIn23
Kb5 MateIn23
e3 Even
e4 Even

&#91;&#93; dg
1 Kb3 Kd7 2 Kc3 Kc6 3 Kc4 Kd6 4 Kd4 Ke6 5 Ke4 Kd6 6 Kf5 Ke7 7 Ke5 Kd7 8 Kf6 Kc6
9 Ke6 Kb5 10 Kd6 Ka6 11 Kd7 Ka5 12 e4 Ka4 13 Kd6 Ka3 14 e5 Ka2 15 Kc5 Ka1 16
Kc4 Ka2 17 e6 Kb2 18 e7 Kc2 19 e8=Q Kd2 20 Qe4 Kc1 21 Kc3 Kd1 22 Qe5 Kc1 23
Qe1# 1-0
I too notice the error in the FEN position - the fifty counter should be 0. There is some bugs in xboard with editing positions when remnant information from previous games/positions corrupts the fifty counter on saving. I discovered it as I have to look into the fifty counter as the bug in my search was a corrupt fifty counter.

Now my KPK rountine is working perfectly. It is just probe KPK bitbase and then returning a value. The return for a probe win is the 'optimally correct' value as pointed out by Ronald - just 8xPawns - distance_to_promote.

My analysis output is (the only correct PV before queening?) :
info depth 41, score +7871 cp, time 7381 ms, nodes 22541387 nps 3053974, pv
a4b3 e8f7 b3c4 f7e6 c4d4 e6d6 e2e3 d6e6 d4e4 e6f6 e4d5 f6e7 d5e5 e7f7 e5d6 f7e8 e3e4 e8d8 e4e5 d8e8 d6e6 e8d8 e6f7 d8d7 e5e6 d7d6 e6e7 d6e5 e7e8q e5d4 e8d8 d4c3
Best Regards,
Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

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

Re: How to implement KPK ?

Post by Chan Rasjid » Tue May 14, 2013 2:50 pm

The game in pgn :
1. Kb3 Kd7 2. Kc4 Kd6 3. Kd4 Ke6 4. Ke4 Kd6 5. Kf5 Kd5 6. e4+ Kd6 7. Kf6
Kd7 8. e5 Kc6 9. e6 Kc5 10. e7 Kd4 11. e8=Q Kc4 12. Qe3 Kd5 13. Qf4 Kc5 14.
Ke6 Kb6 15. Kd6 Kb5 16. Qe4 Kb6 17. Qb4+ Ka6 18. Kc6 Ka7 19. Qb7#
{White mates} 1-0

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

Post Reply