How to implement KPK ?

[Chan Rasjid]

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!

[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

[wgarvin]

In case you haven't read it already, read how Heinz et al. handled this in Darkthought 15 years ago.

They had bitbases for W/D or W/L/D and then the interior node recognizers would make a heuristic score to help drive it towards the win when in a won position (or try to delay a loss etc).

An important thing they discovered was that the had to make the heuristic scoring range for each recognized ending compatible with the normal evaluation scores. If the heuristic was too high or low, odd play would result (such as the engine trying to avoid promoting, etc).

[edit: in one of Heinz's papers somewhere, they list all of the heuristic scoring functions they used for all 3- and 4-man endings. "Knowledgable Encoding and Querying of Endgame Databases", it can be found with Google]

[Chan Rasjid]

Hello Wylie,

Thanks for the links. I'll see whether it is bugs or some failure in my understanding.

Bets Regards,
Rasjid.

[Chan Rasjid]

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!

Rasjid.

[Evert]

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

Maybe. I wasn't being specific: you need a way to evaluate progress from one position where the bitbase says it is won to another; in general that includes things like putting your king in the right place (and even if you know the position is losing, you may want to put your king where it has the best fighting chances). But you're right that you don't need it to avoid giving away the win.

[hgm]

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.

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