Yet another KPK endgame table generator: pfkpk

[mvk]

I just finished cleaning up my KPK bitbase generator and probing interface and put it on github:
https://github.com/kervinck/pfkpk

On the RPI it completes generation in 0.05 seconds.
It is agnostic to square indexing, in the sense that it can be adapted to any of the 8 possible board geometries with just a minor local change.
I'm pretty sure the results are fully correct. Test cases are included.
License is BSD-style, free for anyone to use.

On my laptop generation takes 1.5 milliseconds:

Code: Select all

make
cc -std=c99 -pedantic -Wall -O3 -o pfkpk pfkpk.c kpk.c
./pfkpk
kpkGenerate CPU time [seconds]: 0.001581
kpkTable size [bytes]: 32768
kpkSelfCheck: OK
kpkProbe 24/24: OK

Enjoy.

[Gerd Isenberg]

Very nice piece of code! I like the agnosticism to square indexing.

[cdani]

Congratulations for this nice work!

[brtzsnr]

Very nice and thanks for having it under a permissive license.

Do you know how much kpk are worth ELO wise? I'm considering whether to add full endgame table bases support, or just kpk only, or no special endgame knowledge.

[hgm]

I don't expect it to be much. Most of the cases will be adequately handled by general heuristics that you need anyway to not play like an idiot in multi-Pawn end-games. Like that being outside the 'square' of an opponent passer means the Pawn promotes (if your own passer does not promote sufficiently far ahead of it).

It also depends what you use as alternative. In the simple demo engine I wrote I put some heuristics to recognize some 'classical' draw positions (attacking King 1 rank ahead of Pawn and defender has opposition, or attacking King next to Pawn and defender in front of it, in opposition if on last rank or in far opposition).

There is very little gain in recognizing everything, as most positions will resolve themselves one way or the other very quickly. E.g. if the Pawn is on 7th, you either lose the Pawn or stalemate on the next ply, or you will win. As the passer on 7th in itself will already cause a winning score, there really isn't anything that needs correction. It is only the opposition and Pawn-before-King cases that cause problems, because the Pawn side can then stall advancing the Pawn very long, making it reach 6th or 7th rank just at the horizon no matter how deep you search, and still count himself rich for possession of it. In positions where he is going to lose the Pawn, the search will find that decisively, and speeding it up by a recognizer hardly gains anything. Especially if you extend after conversion to a Pawn ending.

[mvk]

Very nice and thanks for having it under a permissive license.

Do you know how much kpk are worth ELO wise? I'm considering whether to add full endgame table bases support, or just kpk only, or no special endgame knowledge.

I don't know. This is a side project for me.

In fact I have removed all programmed knowledge of special endgames from Rookie in exchange for relying on Syzygy tables, because there is no reason to assume that at least the 5pc tables are not available and I don't want to have redundant code. KPK is such a special case. The other important ones being KBNK, KRPKR and KQPKQ, KP(a)KB with the wrong bishop.

Then there is NOW's trick to use a KPK table to evaluate passers in general pawn endings. I don't know what to think of that.

Not everything is about elo. Engines are also used for analysis. Completeness is a consideration for that use case. And of course, the occasional failure to handle basic cases gets a lot of exposure, even if elo-wise it doesn't do much. Null move failures come to mind, or not winning KRK, or missing a bishop or rook promotion in a study.

[hgm]

The other important ones being KBNK, KRPKR and KQPKQ, KP(a)KB with the wrong bishop.

I guess you mean KBP(a)K for the latter. These are indeed exactly those for which I had planned to add knowledge in the demo engine. Still have to do KQKP and KRPKR; I expect the latter to have the most impact on Elo. (Perhaps the only one...)

KBNK has a bit of a different character from KPK, KQKP etc.: the latter are recognizers that immediately cut off the search with a draw score (dividing the score provided by the current evaluation by 8 or so). For KBNK you don't want to prune anything, but just alter the evaluation to break the symmetry between corners. Currently I have a pit of a primitive way to apply a drawishness correction, namely by specifying a right-shift. This allows only facors 0.5, 0.25, 0.125, ... (I plan to change this to a general multiplication factor in steps of1/64 or so). Still, when a1 is the wrong corner, and apply a factor 0.25 to a-b1-2 and a factor 0.5 to the remaining part of the a-d1-4 quadrant, it has no problem mating in KBNK even with search depth restricted to 7. A factor 0.25 is a bit on the high side, however, although the naive evaluation in KBNK is of course quite high. So it ends up at 1.7-2.0, which is still not so discouraging for converting to it if you only can do it in the wrong corner that it would cost you any points; presumable alternatives with eval > 2.0 would also easily win. But I would feel easier if I could apply a factor (0.5 + d/8), where d is the distance of the bare King to the closest wrong corner. Then the KBNK score would still be > 3 there.