How to implement KPK ?

[Sven]

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).

Why would you need any king properties for evaluating a bitbase-won position? Wouldn't it be fully sufficient to use the distance to promotion to guide the search (where you only use one king property if the winner's king is on the promotion path so the distance gets incremented by one)? Advancing the pawn at the wrong time will be covered by getting a draw score from probing, and the same applies to "wrong" king moves leading to a draw.

Sven

Exactly as I understand!

Yes, but I get the impression that your evaluation is a bit too complex and has some parts which are not needed. For instance, if you already know that the position is won then IMO it does not matter whether the enemy king is on the square in front of the pawn. There are only very few cases where this can occur in a won position (e.g. wKd6, Pc7, bKc8, btm) and the search will immediately find the winning line on its own. Also your two conditions regarding the distances of the kings to the pawn square and their distances to the square in front of the pawn are almost redundant, i.e. at most one of them would be sufficient. Finally I believe that you should give a bigger weight to the distance to promotion itself, e.g. by applying a factor of 8. Otherwise your program might frequently miss to play the fastest path to promotion since it gives equal weight to "good" king moves.

As I already mentioned, I would only take care about the friendly king's position at all if it is on the promotion path.

Sven

Have you not heard of the proverb -
"A drowning man will clutch at a straw". And you don't do it it with comely elegance .

And we have all been living and nourished with bad evaluation since chess programming began!

Well, wasn't it you asking for support regarding your KPK evaluation?

Your latest statement I have read, after you switched to bitbase usage, was "But my implementation of the kpk evaluation is still not working.". After switching to the bitbase approach there are basically only three parts left where it can go wrong: 1) the search itself, 2) the code to evaluate bitbase-won positions, 3) the bitbase probing code. I'd assume you should look at 2) first.

What exactly "is not working", what are the symptoms?

Sven

[Sven]

It depends on how detailed you want to indicate progress. Advance of the Pawn represents progress, but it could take 8 ply to force a winning advance. So if you will always search at least 8 ply that is OK. If you also want the engine to make progress when it searches less than 8 ply, you would have to define 'partial goals' based on the King position. Like also awarding points for advancing the King (e.g. 4 times less than for advancing the Pawn) to at most 3 ranks in front of the Pawn.

If pawn advancement alone (more precisely: promotion distance) is really insufficient for an effective search in KPK positions when bitbase support is present (I doubt that) then of course you can add king advancement. But here I don't think you need such a complex condition like "at most 3 ranks in front of the pawn", since we are only talking about bitbase-won positions, and within the (usually small) set of won positions with identical promotion distance it is probably optimal to have the friendly king as close as possible to the promotion square. If that means to be four ranks in front of the pawn then so be it, as long as it is still won! I wouldn't even care about the enemy king's location in that case.

Sven

[hgm]

I added the condition because it would make it obvious that the King bonus could never be more than that for advancing the Pawn one step, no matter where the King is. But of course this also could be achieved by making the King advance bonus 1/8 of the Pawn advance bonus.

Advancing the King too far can be a dead end: suppose your Pawn is on e2, the King on f6 and the defending King on d7. Kf7 advances the King, and is still won. But the opponent then moves Kd6, and the only way to keep the win is now to move the King back to f6, and you just wasted two moves. The opponent can then move back to d7, allowing you to advance again, etc.

Normally I evaluate passers through tables attackBonus[ownKing-passerSqr] and defendBonus[enemyKing-passerSqr], and filling those tables with a function that saturates after 3 ranks is not anymore complex than any other function. (You can also incorporate a small penalty for being on the path of the Pawn, etc.)

[Sven]

Advancing the King too far can be a dead end: suppose your Pawn is on e2, the King on f6 and the defending King on d7. Kf7 advances the King, and is still won. But the opponent then moves Kd6, and the only way to keep the win is now to move the King back to f6, and you just wasted two moves. The opponent can then move back to d7, allowing you to advance again, etc.

This should be irrelevant since the PV move e2-e4 leads to an even better evaluation (still won + lower distance to promotion). The main focus should be to find the PV as quickly as possible based on the evaluation.

Sven

[hgm]

Only as long as King advance has a smaller bonus than Pawn advance. And there was no guarantee you would only do 1-ply searches. It could be that this is not possible in practice, but I could not immediately prove that it would never be possible to get more points from aggressive King advance that is not progress, as for the maximum advance of the Pawn you can make without spoiling the win in the same number of moves, which is why I mentioned the 3-rank limitation as a safeguard.

The main point was that there are also positions where advancing the Pawn draws. Then a 1-ply search would not know what to do if you did not pay attention to the King.

[Sven]

Only as long as King advance has a smaller bonus than Pawn advance.

That was a basic assumption I made. In an earlier post I proposed to the OP to apply some factor to the "promotion distance", which implies exactly what you say. I also think that cases where a king move has in fact a lower DTM than advancing the pawn (while both moves win) are not harmful since I would regard winning by advancing the pawn as "making sufficient progress". I'm not even sure whether many such positions exist, or any at all.

The main point was that there are also positions where advancing the Pawn draws. Then a 1-ply search would not know what to do if you did not pay attention to the King.

No, we are only talking about which eval criteria to include for bitbase-won KPK positions to support progress. Moves advancing the pawn but resulting in a draw are out of scope. Bitbase-drawn positions get a draw score and nothing else. Our "positional" KPK evaluation is restricted to won positions only which we have to compare in order to quickly find a satisfying PV, i.e. one that results in winning by actually making progress (I don't think it's necessary to aim at the shortest path to mate, that would be a better task for an EGTB-based engine). Due to iterative deepening it does not matter much whether we do 1-ply or N-ply searches since each new iteration starts with the previous PV.

Only in positions where advancing the pawn draws but more than one king move wins it might become relevant to include king-related properties into the KPK evaluation. But I don't think it is necessary to be too sophisticated in this case since the search will quickly find those king moves which later on lead to a winning pawn advancement as early as possible, and I think it would even be able to do so without any king-specific term at all.

Sven

[hgm]

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.

[Sven]

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

[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.

[Sven]

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".