KQKP and KRKP endgames

[Daniel Shawul]

Besides that, a bitbase of draws doesn't help compared to a WDL. If your compression is any good it doesn't matter if you use 2bits/pos or 1bits/pos for the bitbases. Anyway there is really no need to not use bitbases. If your goal is to learn rules, then use some data mining techinque not goal specific different from what is being tried here (so traditional), and you might come up with something important in the process. Long time ago I tried a simple Quinlan classifier to learn rules for each bitbase to be used for prediction and help compression. But it didn't help specially after I started using advanced compression algorithms.

[lucasart]

kpk is difficult, required about 15 rules.

That's interesting. If you have those rules somewhere, please post them. I think they belong on the Chess programming wiki page, whicn mentions vaguely that this can be done with deterministic rules, but it takes many rules. Anyway, I see you've chosen the bitbase approach in Stockfish, which is certainly the best performance-wise. I ported SF's code for KPK bitbase into my engine, which is also GPL (of course I mentionned it in the credit section as usual). I hope you don't mind me doing that.

KBNK is surpisingly difficult (around 10 rules)

I'm not sure I follow you here. Unless we're in a trivial case, where the defending king can just capture a piece, it's a win. And to win it, all one needs is to modify the PST in such a way to incentivise pushing the defending king towards a corner of the right color, the search will do the rest. Even GNU Chess 5.07, with such a heuristic and a poor & buggy search, was able to do that. That one is still on my todo list, though.

KBPK, KNPK, KPP are too difficult

The most common case of a drawn KBPK is implemented in Fruit 2.1. It's very simple, and I'm sure almost all other draw cases are only a few good moves away from it, so the search+heuristic should do the trick just fine.

KQKQ is very difficult, likely too difficult

That's rather surprising. My newbie feeling tell me that this is rather trivial: either you can win a Q (by a straightforward fork, that cannot be more than a few plies away) or it's a draw.

[Sven]

I've done some experiments about perfect rule based classifiers.

Kqk, krk, kbk, knk are straightforward.
kpk is difficult, required about 15 rules.
KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK are straightforward.
KBBK is relatively straightforward
KBNK is surpisingly difficult (around 10 rules)
KBPK, KNPK, KPP are too difficult

KQKQ is very difficult, likely too difficult
KQKR is doable, but there are some exceptional perpetual stalemate chases which are very difficult
KQKN, KQKB are straightforward
KQKP is very difficult, but I believe is doable (30 rules)
KRKR, KRKB, KRKN are very (maybe too) difficult
KRKP is very difficult but I believe is doable
KBKP complex, but should be doable
KNKP, KPKP are too difficult

There is not AFAIK complete theory about many of these ending, but if you want to build your own classifiers, simply generate all positions, check their status from tablebases and build your own rules with trial and error.

However I must warn you that the task is huge and ELO gain is going to be minimal.

Let me first express my highest appreciation of your work on that topic! I have tried only a very tiny subset of that and can confirm that it can be really a huge task to write good classifiers for such a wide range of endgames as given in your list.

There is only a minor point I would like to comment on: from the list above which also contains several cases of mating the lone king, may I assume that your classifiers do more than just deciding about WDL (maybe even WD only), by also returning an evaluation that helps to actually play a "good" move, as in KBNK for instance?

As to KBNK specifically, I am surprised as well about the number of rules you mentioned since I think that a rule set like the one below were sufficient for mating the black king, with decreasing priorities:

1. no stalemate (can be skipped since it is usually detected by search)
2. wB and wN not hanging (can be skipped since it is usually detected by search)
3. maximize distance of bK to center
4. minimize distance of wK to bK
5. minimize distance of bK to a corner with same square color as wB

I have successfully applied it in KnockOut, using exactly rules 3-5 in that order.

Sven

[syzygy]

Could it be that Joona is talking about internal node recognisers that cut a whole subtree when a position with known outcome is reached?

I suppose it could indeed be hard to statically determine with 100% certainty whether KQKQ is draw, but I don't see the need for the evaluation to evaluate KQKQ 100% correct. I do see the need for 100% correctness of internal node recognisers.

[Sven]

Could it be that Joona is talking about internal node recognisers that cut a whole subtree when a position with known outcome is reached?

I suppose it could indeed be hard to statically determine with 100% certainty whether KQKQ is draw, but I don't see the need for the evaluation to evaluate KQKQ 100% correct. I do see the need for 100% correctness of internal node recognisers.

Certainly I do not intend to anticipate Joona's reply to your question but at least all those "mating the lone king" cases he included in his list, like KQK or KBNK, are not of that kind, or would you say that KBNK needs an internal node recognizer?

I understood that the original post by Lucas was about recognizing known draws.

Sven

[syzygy]

Could it be that Joona is talking about internal node recognisers that cut a whole subtree when a position with known outcome is reached?

I suppose it could indeed be hard to statically determine with 100% certainty whether KQKQ is draw, but I don't see the need for the evaluation to evaluate KQKQ 100% correct. I do see the need for 100% correctness of internal node recognisers.

Certainly I do not intend to anticipate Joona's reply to your question but at least all those "mating the lone king" cases he included in his list, like KQK or KBNK, are not of that kind, or would you say that KBNK needs an internal node recognizer?

Within a search, it makes sense to not search the subtree further once you reach a position like KQK, KBNK or KQKQ, but then you need to be absolutely sure that the specific KQK and KBNK positions reached really are wins and that the specific KQKQ position reached really is a draw. For KBNK and KQKQ this probably requires quite a bit of code. Joona's reply makes complete sense to me if I assume that this is what he is talking about.

I understood that the original post by Lucas was about recognizing known draws.

The original post by Lucas isn't entirely clear on whether he wants to do the check only in the eval (i.e. in leaf nodes) or also at internal nodes.

I think most of the discussion was on rules to be used in the eval. In the eval, you only need suitable PSTs for solving KQK, KBNK, KRK, and you need nothing special to play KQKQ perfectly. So this can't be what Joona is talking about.

[Uri Blass]

I've done some experiments about perfect rule based classifiers.

Kqk, krk, kbk, knk are straightforward.
kpk is difficult, required about 15 rules.
KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK are straightforward.
KBBK is relatively straightforward
KBNK is surpisingly difficult (around 10 rules)
KBPK, KNPK, KPP are too difficult

KQKQ is very difficult, likely too difficult
KQKR is doable, but there are some exceptional perpetual stalemate chases which are very difficult
KQKN, KQKB are straightforward
KQKP is very difficult, but I believe is doable (30 rules)
KRKR, KRKB, KRKN are very (maybe too) difficult
KRKP is very difficult but I believe is doable
KBKP complex, but should be doable
KNKP, KPKP are too difficult

There is not AFAIK complete theory about many of these ending, but if you want to build your own classifiers, simply generate all positions, check their status from tablebases and build your own rules with trial and error.

However I must warn you that the task is huge and ELO gain is going to be minimal.

Let me first express my highest appreciation of your work on that topic! I have tried only a very tiny subset of that and can confirm that it can be really a huge task to write good classifiers for such a wide range of endgames as given in your list.

There is only a minor point I would like to comment on: from the list above which also contains several cases of mating the lone king, may I assume that your classifiers do more than just deciding about WDL (maybe even WD only), by also returning an evaluation that helps to actually play a "good" move, as in KBNK for instance?

As to KBNK specifically, I am surprised as well about the number of rules you mentioned since I think that a rule set like the one below were sufficient for mating the black king, with decreasing priorities:

1. no stalemate (can be skipped since it is usually detected by search)
2. wB and wN not hanging (can be skipped since it is usually detected by search)
3. maximize distance of bK to center
4. minimize distance of wK to bK
5. minimize distance of bK to a corner with same square color as wB

I have successfully applied it in KnockOut, using exactly rules 3-5 in that order.

Sven

This is a draw and good KBN vs K recognizer should not do the mistake to evaluate it as a win.

I do not see how your rules help here.

[D]n1b5/K7/8/8/8/8/8/7k b - - 1 1

[Uri Blass]

I've done some experiments about perfect rule based classifiers.

Kqk, krk, kbk, knk are straightforward.
kpk is difficult, required about 15 rules.
KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK are straightforward.
KBBK is relatively straightforward
KBNK is surpisingly difficult (around 10 rules)
KBPK, KNPK, KPP are too difficult

KQKQ is very difficult, likely too difficult
KQKR is doable, but there are some exceptional perpetual stalemate chases which are very difficult
KQKN, KQKB are straightforward
KQKP is very difficult, but I believe is doable (30 rules)
KRKR, KRKB, KRKN are very (maybe too) difficult
KRKP is very difficult but I believe is doable
KBKP complex, but should be doable
KNKP, KPKP are too difficult

There is not AFAIK complete theory about many of these ending, but if you want to build your own classifiers, simply generate all positions, check their status from tablebases and build your own rules with trial and error.

However I must warn you that the task is huge and ELO gain is going to be minimal.

KR vs KR seems to be easier than KP vs K intuitively
How many types of winning tactics one side has in KR vs KR?

Note that number of rules means nothing because I can solve it by
only one rule that is simply to search to depth that is big enough.

The interesting question is not the number of rules but the time that you need.

[Sven]

I've done some experiments about perfect rule based classifiers.

Kqk, krk, kbk, knk are straightforward.
kpk is difficult, required about 15 rules.
KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK are straightforward.
KBBK is relatively straightforward
KBNK is surpisingly difficult (around 10 rules)
KBPK, KNPK, KPP are too difficult

KQKQ is very difficult, likely too difficult
KQKR is doable, but there are some exceptional perpetual stalemate chases which are very difficult
KQKN, KQKB are straightforward
KQKP is very difficult, but I believe is doable (30 rules)
KRKR, KRKB, KRKN are very (maybe too) difficult
KRKP is very difficult but I believe is doable
KBKP complex, but should be doable
KNKP, KPKP are too difficult

There is not AFAIK complete theory about many of these ending, but if you want to build your own classifiers, simply generate all positions, check their status from tablebases and build your own rules with trial and error.

However I must warn you that the task is huge and ELO gain is going to be minimal.

Let me first express my highest appreciation of your work on that topic! I have tried only a very tiny subset of that and can confirm that it can be really a huge task to write good classifiers for such a wide range of endgames as given in your list.

There is only a minor point I would like to comment on: from the list above which also contains several cases of mating the lone king, may I assume that your classifiers do more than just deciding about WDL (maybe even WD only), by also returning an evaluation that helps to actually play a "good" move, as in KBNK for instance?

As to KBNK specifically, I am surprised as well about the number of rules you mentioned since I think that a rule set like the one below were sufficient for mating the black king, with decreasing priorities:

1. no stalemate (can be skipped since it is usually detected by search)
2. wB and wN not hanging (can be skipped since it is usually detected by search)
3. maximize distance of bK to center
4. minimize distance of wK to bK
5. minimize distance of bK to a corner with same square color as wB

I have successfully applied it in KnockOut, using exactly rules 3-5 in that order.

Sven

This is a draw and good KBN vs K recognizer should not do the mistake to evaluate it as a win.

I do not see how your rules help here.

[D]n1b5/K7/8/8/8/8/8/7k b - - 1 1

I see we are still talking about different things. I wrote:

2. wB and wN not hanging (can be skipped since it is usually detected by search)

and this was meant in the context of the evaluation function where you usually do not care about tactics that require searching a couple of plies. I think I explicitly mentioned how it was meant in my reply to Joona. Your example is recognized as a draw by searching 3 plies + qsearch, e.g. 1...Nc7 2.Kb8 <any>.

I still think that the original post of Lucas was about detecting known draws but not about evaluation of "mating lone king" positions. I also don't think that an internal node recognizer makes sense for "mating lone king" cases where the vast majority of positions is won for the stronger side with very few exceptions (like your example) which must be found by search. Trying to save nodes by excluding known draws would have almost no success and would only waste time.

Sven

[Sven]

Could it be that Joona is talking about internal node recognisers that cut a whole subtree when a position with known outcome is reached?

I suppose it could indeed be hard to statically determine with 100% certainty whether KQKQ is draw, but I don't see the need for the evaluation to evaluate KQKQ 100% correct. I do see the need for 100% correctness of internal node recognisers.

Certainly I do not intend to anticipate Joona's reply to your question but at least all those "mating the lone king" cases he included in his list, like KQK or KBNK, are not of that kind, or would you say that KBNK needs an internal node recognizer?

Within a search, it makes sense to not search the subtree further once you reach a position like KQK, KBNK or KQKQ, but then you need to be absolutely sure that the specific KQK and KBNK positions reached really are wins and that the specific KQKQ position reached really is a draw. For KBNK and KQKQ this probably requires quite a bit of code. Joona's reply makes complete sense to me if I assume that this is what he is talking about.

As I wrote in my reply to Uri, I think that "mating the lone king" positions like KQK or KBNK should not be handled by an internal node recognizer since most positions are won and the effort to detect rare exceptions does not pay off. Essentially the same applies to using bitbases or tablebases, but the difference is that you use the same (bitbase/tablebase) mechanism also for the "normal" N-men endgames which are not in the exceptional "mating the lone king" group. But without bitbases/tablebases I think that the search should find the exceptional draw cases while the evaluation should guide the search into the right direction (how to mate the king correctly).

I understood that the original post by Lucas was about recognizing known draws.

The original post by Lucas isn't entirely clear on whether he wants to do the check only in the eval (i.e. in leaf nodes) or also at internal nodes.

Agreed.

I think most of the discussion was on rules to be used in the eval.

Not sure about this ...

In the eval, you only need suitable PSTs for solving KQK, KBNK, KRK, and you need nothing special to play KQKQ perfectly. So this can't be what Joona is talking about.

I almost agree, except for the "PST" argument since mating the lone king usually also requires to approach the own king to the enemy's king which is not solvable by PST's alone. Other than that, you are right of course, and that was exactly what I was wondering about, but now let's wait for Joona's explanation

Sven