KQKP and KRKP endgames

[lucasart]

I don't want to use a table base, just to programmatically detect some general cases where such an endgame is a known draw. I google it and couldn't find anything useful. But surely there must be some theory on that, right ?

I think KQKP can be important: typically it raises from a KPKP which becomes a pawn race, one side queens, but that doesn't always guarantee a win. Obviously my stupid eval will return pretty much the material difference, which could lead to blunders (ie. choosing to simplify to obtain an apparently winning KQKP that is in fact a draw, when another choice could have won).

KRKP should be relatively similar, I suppose.

[Mincho Georgiev]

They are quite different according to my humble chess knowledge.
However, there is a general rule of each one of them.

1. KQKP:
/if the king of the stronger side is distant from the pawn and needs temp to get closer/
- pawn on 7th - win can be achieved only if the pawn is on B,G,D,E files.

2. KRKP:
- certain win is achieved if the king of the weaker side is behind it's pawn and the pawn gets cut from it's king by the 4th relative rank /weaker side prospective/.


There are some exceptions and some more rules for king being an obstacle in his pawn's way in KRKP, as well as some for KQKP and lots of good resources like the books of Averbach, Dvoretskii and so on.

[Sven]

I don't want to use a table base, just to programmatically detect some general cases where such an endgame is a known draw. I google it and couldn't find anything useful. But surely there must be some theory on that, right ?

I think KQKP can be important: typically it raises from a KPKP which becomes a pawn race, one side queens, but that doesn't always guarantee a win. Obviously my stupid eval will return pretty much the material difference, which could lead to blunders (ie. choosing to simplify to obtain an apparently winning KQKP that is in fact a draw, when another choice could have won).

KRKP should be relatively similar, I suppose.

KQKP can be solved statically for many cases, even though it is not always "trivial". In general, assuming a white queen and a quiet position with white to move, the position is a known draw, beneath possible other cases, if

a) the pawn is on the 2nd rank, and
b) the pawn is on the a-, c-, f-, or h-file, and
c) the pawn's promotion square is not occupied by a white piece, and
d) the pawn's promotion square can't be safely occupied by a white piece in the next move, and
e) the bK defends the pawn OR we have one of the patterns like Ka1/Pc2, Kc1/Pa2 (not sure about the latter!) where a distance of 2 squares between bK and pawn can be sufficient for a draw, and
f) the wK is "far enough" away from the pawn.

Conditions a)-e) are exact while in f) the term "far enough" depends on the position of all other pieces. There are distinct zones where the wK must be inside to win.

EDIT: Of course the second part of e) is also not "exact" ...

There are also rare exceptions with pawns on the 3rd rank which are drawn.

For KRKP the rules seem to be slightly more complex, and I can't give you any rules here. I don't think it is very similar to KQKP.

Sven

[lucasart]

I don't want to use a table base, just to programmatically detect some general cases where such an endgame is a known draw. I google it and couldn't find anything useful. But surely there must be some theory on that, right ?

I think KQKP can be important: typically it raises from a KPKP which becomes a pawn race, one side queens, but that doesn't always guarantee a win. Obviously my stupid eval will return pretty much the material difference, which could lead to blunders (ie. choosing to simplify to obtain an apparently winning KQKP that is in fact a draw, when another choice could have won).

KRKP should be relatively similar, I suppose.

KQKP can be solved statically for many cases, even though it is not always "trivial". In general, assuming a white queen and a quiet position with white to move, the position is a known draw, beneath possible other cases, if

a) the pawn is on the 2nd rank, and
b) the pawn is on the a-, c-, f-, or h-file, and
c) the pawn's promotion square is not occupied by a white piece, and
d) the pawn's promotion square can't be safely occupied by a white piece in the next move, and
e) the bK defends the pawn OR we have one of the patterns like Ka1/Pc2, Kc1/Pa2 (not sure about the latter!) where a distance of 2 squares between bK and pawn can be sufficient for a draw, and
f) the wK is "far enough" away from the pawn.

Conditions a)-e) are exact while in f) the term "far enough" depends on the position of all other pieces. There are distinct zones where the wK must be inside to win.

EDIT: Of course the second part of e) is also not "exact" ...

There are also rare exceptions with pawns on the 3rd rank which are drawn.

For KRKP the rules seem to be slightly more complex, and I can't give you any rules here. I don't think it is very similar to KQKP.

Sven

Thanks for the link. It appears to be much more complex than I initially envisaged. What I was basically hoping for is:
1/ determine simple rules when it's a known draw, if the pawn is on the 7th rank
2/ any other drawish position should not be more than a few good moves away from 1/, so a bit of search combined with 1/ should more or less do the trick

However, rule 1/ must tolerate no exceptions, even "rare" ones, or else it's a disaster and I'm better off without it. I thought a 7th rank pawn with the king at distance 1 and attacking king at distance >=2 for example was a sufficiant condition, but even that seems to be wrong...

[kbhearn]

You could still do a rough predictor that's not always right and rely on search to extend it. The winning zones are right over 99% of the time. And the pawn on the 6th rank on the queen's move is lost over 99% of the time. Assuming pawn on the 7th with its king nearby and attacking king outside the winning zone is drawn is probably good enough as long as you don't just abort the search, most of the special cases are only a couple ply from becoming a general case, you could even do say a few ply extension upon entering such an ending in order to catch the majority of special cases.

KRvKP is indeed more complicated, sometimes you have to precisely calculate races with bodychecks many plies deep to find the true evaluation of the position. Again though, there are specific formations you could recognise as clearly won which comprise the majority of the cases, and then treat things that don't meet those formations as a smaller advantage than you otherwise would. Combined with an extension upon entering KRvKP, most wins would be able to reach a 'known certain win' within a few ply.

[Sven]

I don't want to use a table base, just to programmatically detect some general cases where such an endgame is a known draw. I google it and couldn't find anything useful. But surely there must be some theory on that, right ?

I think KQKP can be important: typically it raises from a KPKP which becomes a pawn race, one side queens, but that doesn't always guarantee a win. Obviously my stupid eval will return pretty much the material difference, which could lead to blunders (ie. choosing to simplify to obtain an apparently winning KQKP that is in fact a draw, when another choice could have won).

KRKP should be relatively similar, I suppose.

KQKP can be solved statically for many cases, even though it is not always "trivial". In general, assuming a white queen and a quiet position with white to move, the position is a known draw, beneath possible other cases, if

a) the pawn is on the 2nd rank, and
b) the pawn is on the a-, c-, f-, or h-file, and
c) the pawn's promotion square is not occupied by a white piece, and
d) the pawn's promotion square can't be safely occupied by a white piece in the next move, and
e) the bK defends the pawn OR we have one of the patterns like Ka1/Pc2, Kc1/Pa2 (not sure about the latter!) where a distance of 2 squares between bK and pawn can be sufficient for a draw, and
f) the wK is "far enough" away from the pawn.

Conditions a)-e) are exact while in f) the term "far enough" depends on the position of all other pieces. There are distinct zones where the wK must be inside to win.

EDIT: Of course the second part of e) is also not "exact" ...

There are also rare exceptions with pawns on the 3rd rank which are drawn.

For KRKP the rules seem to be slightly more complex, and I can't give you any rules here. I don't think it is very similar to KQKP.

Sven

Thanks for the link. It appears to be much more complex than I initially envisaged. What I was basically hoping for is:
1/ determine simple rules when it's a known draw, if the pawn is on the 7th rank
2/ any other drawish position should not be more than a few good moves away from 1/, so a bit of search combined with 1/ should more or less do the trick

However, rule 1/ must tolerate no exceptions, even "rare" ones, or else it's a disaster and I'm better off without it. I thought a 7th rank pawn with the king at distance 1 and attacking king at distance >=2 for example was a sufficiant condition, but even that seems to be wrong...

"attacking king at distance >= 2" is obviously wrong in many cases but you can try to find a better value instead of "2" for each interesting class of bP-bK positions by writing a program (or adding code to your engine) that enumerates all legal, non-terminal, quiet, white-to-move positions for a given bP-bK position class (restricted to Pa2/c2/a3/c3 based on symmetry and other knowledge), looks up their true values in a tablebase/bitbase, and determines the smallest wK-bP distance for which the position is always a draw for all positions of the same class, and maybe also the largest wK-bP distance for which the position is always won (the latter only if you want to get safe predictions for "always won" positions as well). That should not be too difficult. (Here I assume that the wK-bP distance is the relevant number, which I am not 100% sure about: it might also be the distance of the wK to the promotion square.)

A suitable definition of "quiet" could be: wK not in check and no safe capture of bP possible in one ply. My conditions c) and d) above would have to be considered, too, since occupying the promotion square would make all wK-bP distance calculations obsolete. So you might extend the term "quiet" by "promotion square not occupied by white and can't be safely occupied in one ply".

Maybe someone has already done something similar.

The result would be interesting, even though I am not sure whether the overall effort would really pay off when considering that KQKP is quite a special case.

Sven

[Sven]

Btw for KQKP I just found that there are also rare exceptions where a black king on rank 4 is sufficient for a draw, e.g. if the wQ is unable to block the pawn in two plies like in this example:
[D]8/5Q2/5K2/8/1k6/8/2p5/8 w - - 0 1[/D]
That makes a useful predictor slightly more complex (but still doable) ...

EDIT: fixed the diagram (must be white to move)
EDIT2: I meant "black king on rank 4" of course, not "black pawn"

Sven

[lucasart]

Btw for KQKP I just found that there are also rare exceptions where a black king on rank 4 is sufficient for a draw, e.g. if the wQ is unable to block the pawn in two plies like in this example:
[D]8/5Q2/5K2/8/1k6/8/2p5/8 w - - 0 1[/D]
That makes a useful predictor slightly more complex (but still doable) ...

EDIT: fixed the diagram (must be white to move)
EDIT2: I meant "black king on rank 4" of course, not "black pawn"

Sven

On this position the pawn is only one push away from promotion. It's not on rank 4. So this position doesn't look very exceptional. I fail to understand the subtilty here.

[syzygy]

That makes a useful predictor slightly more complex (but still doable) ...

I don't really see why a predictor that misses some subtleties would not be useful.

Without any specific rules, the eval will use material balance as predictor. That will incorrectly evaluate many draws as wins for K+Q. With specific rules, most of these draws can be caught at the price of evaluating a few wins for K+Q as draw. Overall that should be an improvement. Inaccuracies in the evaluation are inevitable, which is the reason to do a search.

Of course a not completely accurate predictor should not be used to abort the search at an internal tree node.

[michiguel]

That makes a useful predictor slightly more complex (but still doable) ...

I don't really see why a predictor that misses some subtleties would not be useful.

Without any specific rules, the eval will use material balance as predictor. That will incorrectly evaluate many draws as wins for K+Q. With specific rules, most of these draws can be caught at the price of evaluating a few wins for K+Q as draw. Overall that should be an improvement. Inaccuracies in the evaluation are inevitable, which is the reason to do a search.

Of course a not completely accurate predictor should not be used to abort the search at an internal tree node.

Exactly. Inaccurate predictors should not be used in search, but could be used in eval. However, these type of positions are very deceiving. We had a thread about it ~1.5 year ago with Robert Houdart and Richard Vida about it. A very simplistic approach may even be worse than nothing if done carelessly. I have seen it when I was working on this. Search is really tricky to find wrong exceptions, stick them in hash, and the whole thing gets difficult.

If a simplistic case is applied, it should be better to include only basic cases in which you are 100% sure the position is predicted well (draws in this case), and let the other cases be found in search.

I worked hard on this finding all exceptions (validating it with TBs) and coding rules for it. It is not easy. I did not finish the job but I covered most of it in Gaviota. But, the position posted by Sven, Gaviota get it wrong in eval. It finds the draw after one ply though.

Miguel