How to implement KPK ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: How to implement KPK ?

Post by Sven »

hgm wrote:Well, it depends on the depth. I don't think it will be possible without King term if you restrict the search depth to 1 ply, for instance. In situations other than a simple rule-of-squares race, you need more King moves than Pawn moves to win against best defence. E.g. with Ke4, Pe3 vs Ke6 (btm) after Kd6 both Kf5 and Kf4 are winning, but only Kf5 is progress. So if because of move-gen ordering it happens to prefer Kf4, it would never make progress. Relying on rep-draw code to force progress is a tricky thing, because it also often backfires; In the given example you might think that the second time it would play Kf5 because it now recognizes Kf4 as a draw, but in fact there won't be a second time, because after Kd6, Kf4, Ke6 the only winning move Ke4 is now tainted as rep-draw, so it will accept that the position is drawn now, and pick a random drawing move.

Restricting the search to 1 ply might seem a bit extreme, but it is of course exactly what you do if you want to build a recognizer for this end-game.
In my view the typical application of a KPK recognizer that uses a bitbase is the normal search which also has repetition detection. None of these problems should occur there: in the given example the search will prefer Kf5 after 4 iterations.

Iteration 1 might return 1.Kf4 as PV move, as you say.
Iteration 2: 1.Kf4 Ke6 (win).
Iteration 3: 1.Kf4 Ke6 2.Ke4 (win).
Iteration 4: 1.Kf4 Ke6 2.Ke4 Kd6 (rep draw). But now it still finds 1.Kf5 (e.g. Ke7 2.Ke5 Kd7) as new PV at the root.

Restricting the search to 1 ply is not "typical" in my eyes. A perfect recognizer that you can use in a 1-ply search would be based on a DTM tablebase, not a bitbase, so that you always select among those moves which have the shortest path to mate. Using a bitbase together with a complex evaluation does not make much sense to me.

In many practical cases where a KPK position is reached within a deeper search of a "bigger" endgame you will not need the complex evaluation part at all since the "win" or "draw" information itself will already lead to a cutoff.

Sven
User avatar
hgm
Posts: 27772
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How to implement KPK ?

Post by hgm »

Except of course that it is

Iteration 3: 1.Kf4 Ke6 2.Ke4 (rep draw)...

I agree that a recognizer for KPK makes no sense, and that any realistic search would not need the King to measure progress. In fact it would not even need the Pawn to measure progress, as it is so simple that you would see the promotion instantly.

This is not in general true, however. KQKP can be a serious problem, and a bitbase is no help, as the normal search will also immediately see that it is not a good idea to allow the Pawn to promote. KQKR and KBNK are also nasty cases where bitbases offer no help.

Note that exact DTM knowledge is not a necessary condition for always taking the fastest path. There exist other distance measures that would also have that property.
Last edited by hgm on Sun Mar 31, 2013 11:22 am, edited 1 time in total.
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: How to implement KPK ?

Post by Sven »

hgm wrote:Except of course that it is

Iteration 3: 1.Kf4 Ke6 2.Ke4 (rep draw)...
Yes, I see you are right, you started your example with the black King on e6 and the move "0...Kd6".
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: How to implement KPK ?

Post by Don »

[/quote]
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.
[/quote]

Bizarre quote. A did a statistical study a good while back on all endgame piece configurations and this one is actually very common.

Out of 518,322 computer generated games it appears (and stays for at least 3 or 4 ply) in about 2.5% of the games. If games are adjourned you may not see it. The games where it appears are won about 64% of the time by the pawn.

One of the most common things in chess is to be 1 pawn up trying to win and these often trade down to KpvsK.

The statistics are almost the same in win frequency for KRPvsR, another common ending. These are even more common, occuring about 3 or 4 percent of the time. Note that these sometimes can trade down to KPvsK.

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
Chan Rasjid
Posts: 588
Joined: Thu Mar 09, 2006 4:47 pm
Location: Singapore

Re: How to implement KPK ?

Post by Chan Rasjid »

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.
syzygy
Posts: 5555
Joined: Tue Feb 28, 2012 11:56 pm

Re: How to implement KPK ?

Post by syzygy »

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.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: How to implement KPK ?

Post by sje »

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.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: How to implement KPK ?

Post by Don »

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&#40;const int side&#41; &#123;
    const int pcol = !bits&#91;0&#93;&#91;Pawn&#93;, xpcol = pcol ^ 1;
    const int pK = king&#91;pcol&#93;, loneK = king&#91;xpcol&#93;, p = firstone&#40;bits&#91;pcol&#93;&#91;Pawn&#93;);
    const int promsq = PROMOTE_SQ&#40;p, pcol&#41;;
    int probeWk, probeBk, probeWp;
    int win, index, stm;
    int x, d1, d2;

    /* safe capture of pawn */
    if &#40;kMap&#91;king&#91;side&#93;&#93; & bits&#91;side ^ 1&#93;&#91;Pawn&#93; & ~kMap&#91;king&#91;side ^ 1&#93;&#93;) &#123;
        return &#40;side == pcol ? 2 &#58; -2&#41;;
    &#125;

    /* pawn/loneK race to promote. */
    if (!&#40;FORWARD_ROW_BITS&#40;p, pcol&#41; & rMap&#91;p&#93;->file & bits&#91;pcol&#93;&#91;King&#93;)) &#123;
        /* path ahead clear */
        d1 = DIST&#40;p, promsq&#41;;
        d2 = DIST&#40;loneK, promsq&#41; - &#40;side ^ pcol&#41;;
        if &#40;d2 > d1&#41; &#123;
            /* promote success */
            x = v8Pawn - DIST&#40;p, promsq&#41;;
            return &#40;side == pcol ? x &#58; -x&#41;;
        &#125;
    &#125;

    /* kings' race to protect pawn. */
    d1 = DIST&#40;p, pK&#41;;
    d2 = DIST&#40;p, loneK&#41; - &#40;side ^ pcol&#41;;

    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 4:27 pm

Re: How to implement KPK ?

Post by Don »

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: 588
Joined: Thu Mar 09, 2006 4:47 pm
Location: Singapore

Re: How to implement KPK ?

Post by Chan Rasjid »

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.