How to implement KPK ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

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

Re: How to implement KPK ?

Post by Chan Rasjid » Sat Mar 30, 2013 12:18 pm

Evert wrote:
Chan Rasjid wrote: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).
When things don't go as I expected, I usually start with a 'healthy' dose of doubts about my own understanding. But now, what you and Muller said confirms that my understanding of how chess search works here is still sound - an alpha-beta engine with just material evaluation will still not make weird chess moves. So my kpk routine should be very much better.

My implementation of 'win' is exactly as what you said, basically about the pawn promoting successfully. Only thing is that the usual passed pawn codes are more complex.

Lately, strange things is happening with my engine. As in what I posted in the other thread "An Evaluation Mystery", I almost have to doubt that the GCC compiler is failing in a strange manner! I'll just re-install GCC in my Arch Linux system though it is unbelievable it could be in error over such simple lines of codes.

I'll sit back for a while and may try to solve these bugs through a more well rounded and holistic approach - adding 'prayer'.

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 » Sat Mar 30, 2013 12:20 pm

Sven Schüle wrote:
Evert wrote:
Chan Rasjid wrote: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!
Don't believe when you're told "There's no free lunch!" There is Linux.

Sven
Posts: 3573
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: How to implement KPK ?

Post by Sven » Sat Mar 30, 2013 12:42 pm

Chan Rasjid wrote:
Sven Schüle wrote:
Evert wrote:
Chan Rasjid wrote: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
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: How to implement KPK ?

Post by wgarvin » Sat Mar 30, 2013 12:50 pm

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
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: How to implement KPK ?

Post by Chan Rasjid » Sat Mar 30, 2013 1:53 pm

Hello Wylie,

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

Bets 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 » Sat Mar 30, 2013 2:03 pm

Sven Schüle wrote:
Chan Rasjid wrote:
Sven Schüle wrote:
Evert wrote:
Chan Rasjid wrote: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 . :D

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

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

User avatar
Evert
Posts: 2898
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: How to implement KPK ?

Post by Evert » Sat Mar 30, 2013 2:03 pm

Sven Schüle wrote: 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.

User avatar
hgm
Posts: 22206
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: How to implement KPK ?

Post by hgm » Sat Mar 30, 2013 2:26 pm

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
Posts: 3573
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: How to implement KPK ?

Post by Sven » Sat Mar 30, 2013 6:29 pm

Chan Rasjid wrote:
Sven Schüle wrote:
Chan Rasjid wrote:
Sven Schüle wrote:
Evert wrote:
Chan Rasjid wrote: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 . :D

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
Posts: 3573
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: How to implement KPK ?

Post by Sven » Sat Mar 30, 2013 6:38 pm

hgm wrote: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

Post Reply