How to implement KPK ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
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: 2900
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: 22572
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
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: 3651
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

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: 3651
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

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

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

Re: How to implement KPK ?

Post by hgm » Sat Mar 30, 2013 8:13 pm

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
Posts: 3651
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: How to implement KPK ?

Post by Sven » Sat Mar 30, 2013 8:58 pm

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

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

Re: How to implement KPK ?

Post by hgm » Sat Mar 30, 2013 10:58 pm

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
Posts: 3651
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: How to implement KPK ?

Post by Sven » Sat Mar 30, 2013 11:51 pm

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

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

Re: How to implement KPK ?

Post by hgm » Sun Mar 31, 2013 7:35 am

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.

Post Reply