KQKP and KRKP endgames

[syzygy]

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.

Agreed.

[zamar]

It seems that there is a lot of confusion about the meaning of my post.

My post was about rules as bitbase replacement. How difficult it's to classify position as WIN/DRAW/LOSS without doing any search.

Because accessing compressed bitbases can be relatively costly operation, I wanted to test how easy it would be to replace most of the bitbases with static rules.

The answer was that this is in most cases much more difficult than what I assumed originally.

[Tord Romstad]

Anyway there is really no need to not use bitbases.

There is a very good reason to avoid them whenever possible: They are still too big, even with compression. Programmers keep forgetting that chess programs these days are almost always run on mobile phones and other handheld devices with limited memory.

An obvious point I'm not sure has been mentioned elsewhere in the thread (I haven't read all the messages) is that even an imperfect rule-based internal node recognizer for basic endgames can be useful, if it's aware of its own shortcomings. Instead of returning one of the three values W, L or D, such a recognizer would return W, L, D or "don't know". In case of a "don't know", the program would keep searching, and hopefully reach a position with a known result a ply or two deeper.

I think such imperfect internal node recognizers would usually be easier to program and require fewer rules, and as long as the number of "don't know" positions is reasonably low, they will be almost as good as perfect recognizers in practice.

[michiguel]

Some positions predicted as a win, when there they are draw, could generate bad scenarios.

But this is exactly the situation you get with a KQKP-specific rule that only predicts correct draws. When this rule does not give an answer, you fall back on the regular eval which surely will predict a win for K+Q.

I philosophically agreed with your first post, but what I am trying to say is that you have to be very careful and conservative. Both offer risks (draws and win predictions) and benefits. But the win predictions are more problematic I think.

In a way, this is similar to have incomplete TBs. Here, we may have neighbor positions with predictions and some without. The search will pick and choose what path will benefit the most the side to move. The fact that this endgame have gazillion ways to repeat make the whole thing complicated. The way I have done it was to carefully cover all the "neighbor" and children position holes and the respective derivatives. For instance (I think), Sven's position was not covered in my analysis, but I believe I may have covered with rules all the possible derivatives. So, search has no chance to screw this.

This is like saying, I can have perfect information about KRPKR, but if you do not have good eval about KQKR (a derivative) problems arise. This was the typical problem saw with incomplete TBs. In this discussion, we may end up with a similar conceptual problem.

Miguel

[Daniel Shawul]

Anyway there is really no need to not use bitbases.

There is a very good reason to avoid them whenever possible: They are still too big, even with compression. Programmers keep forgetting that chess programs these days are almost always run on mobile phones and other handheld devices with limited memory.

Well four men take about 4 mb (?) and five men are about 220 mb. That certainly fits into many hand held devices. Actually I was surprized to find out that scorpio bitbases have been compiled and used on tablets long before I knew about it. My phone has an 16gb sd card with 1 gb ram so it can fit in there too.

An obvious point I'm not sure has been mentioned elsewhere in the thread (I haven't read all the messages) is that even an imperfect rule-based internal node recognizer for basic endgames can be useful, if it's aware of its own shortcomings. Instead of returning one of the three values W, L or D, such a recognizer would return W, L, D or "don't know". In case of a "don't know", the program would keep searching, and hopefully reach a position with a known result a ply or two deeper.

I think such imperfect internal node recognizers would usually be easier to program and require fewer rules, and as long as the number of "don't know" positions is reasonably low, they will be almost as good as perfect recognizers in practice.

For bitbases illegal moves ( "don't knows" ) are actually assigned to either to whichever makes them compress well W,D,L. I am sure I have tried many rules including those mentioned here to predict scores for compression. It doesn't have to be perfect to be used for this purpose. The problem is most of the size of bitbases comes from those with many exceptions such as KQKP.b. So you can think of the bitbase storing those cases where a recongnizer would say a "Don't know". Internal node recognizers can help but those case where they do, the corresponding bitbases are also too small so you might as well use them instead. It is not so much interesting to do manual classification as is done here, others have tried data mining techniques to do automatic learning of rules to compress well in case of bitbases or to be used as recognizers.

[bob]

In the given case of KQKP, why do you believe that it is better to accept some false draw predictions in exceptional cases, instead of restricting draw detection by 100% to those cases where exact knowledge is present? I am not saying that accepting some false draw predictions would cause severe trouble, but do you believe it improves playing strength compared to only predicting perfectly known cases?

It depends on the rules you can choose from. For example, if rule 1 detects 80% of the KQKP draws with 100% accuracy, and rule 2 detects 99% of the KQKP draws, but with 1% false positives, then rule 2 might be preferable. (A good question here is: 1% of what? 1% of the number of won KQKP positions is huge. 1% of the number of drawn KQKP positions is probably acceptable.)

In case you don't then I would always go the "only perfect knowledge" way if it does not hurt otherwise.

Without specific KQKP rules (and without tablebases), you fall back to the very imperfect knowledge encoded by the regular eval function.

My point is that when not using a specific (im)perfect predictor, you still use a (generic) imperfect predictor. Why is it unacceptable to incorrectly detect some draws if it is acceptable (and in any case inevitable) to incorrectly detect wins?

Some positions predicted as a win, when there they are draw, could generate bad scenarios. The search find a way to repeat positions with checks of all colors and get at the tip the (wrongly predicted) "won" position. Next ply in the iterative deepening search will be the same, except that the path is extended one ply. It takes forever to see the draw. This may look like a rare case, but the search will find it, and it will make sure it will find it at the tip.

Since the Q has the power to determine what to find, it is riskier to have "predicted wins" that are wrong. It is safer to determine what is a draw (the winning side won't try to find that).

Miguel

I completely agree here. The search is EXTREMELY adaptive and can force those incorrect results to a point in the tree where they will be embarrassing. It has happened to me many times in the past. The horizon effect is still alive and well, and these deep searches simply make it more difficult to spot. That's sort of related to Berliner's observations on discontinuity in the evaluation. On either side of the discontinuity point, you get significantly different evaluations. An example from years ago was simply turning king safety off when material drops below X. If your king is exposed, you might give up a piece for a pawn to get over that threshold and lose the negative king safety. If it works, then you probably could have done the same thing in another way, and preserved the knight, and not lost a simple endgame as opposed to trying to solve a very unclear tactical position.

We had a few bugs in the early Edwards tablebases. Steven can probably kick in with the specifics, but I found 'em, and I found them OTB in games on ICC. And they were very subtle and represented just a few "broken" positions, but the search can manipulate where it probes to find such scores, so that they become quite embarrassing... Believe me... Got several T-shirts from such problems...

I have had the best success with eval terms that are 100% accurate, even if they don't cover 100% of the positions. But if they think they apply to a position, the answer they give is correct, always. Otherwise the term disables itself. And those still leave holes, since for the cases where the eval term is not used, you are still subject to a "general rule failure". But that is not as bad as a specific rule that gives bad answers, at least in the cases I have had to debug over the years...

[bob]

Anyway there is really no need to not use bitbases.

There is a very good reason to avoid them whenever possible: They are still too big, even with compression. Programmers keep forgetting that chess programs these days are almost always run on mobile phones and other handheld devices with limited memory.

An obvious point I'm not sure has been mentioned elsewhere in the thread (I haven't read all the messages) is that even an imperfect rule-based internal node recognizer for basic endgames can be useful, if it's aware of its own shortcomings. Instead of returning one of the three values W, L or D, such a recognizer would return W, L, D or "don't know". In case of a "don't know", the program would keep searching, and hopefully reach a position with a known result a ply or two deeper.

I think such imperfect internal node recognizers would usually be easier to program and require fewer rules, and as long as the number of "don't know" positions is reasonably low, they will be almost as good as perfect recognizers in practice.

I've never had much luck with the "don't know" approach, and trying to extend just those, but I do believe that your suggestion is the right general direction. You either give an answer you are certain about, or you don't give an answer and let the general-case evaluation do whatever it can do...

And I am specifically talking about a term that produces a large score, such as the classic square of the pawn/king (unstoppable passed pawn) rule that returns a pretty large score if the pawn can't be caught... If it screws up, you will see it more frequently than you might expect...

I've debugged quite a few search instability issues (not to mention the outright bogus move choices of course) that end up in such a case, where the term says "I apply and here's the large bonus" but it was simply wrong.

The search keeps finding ways to prove it wrong, but it also keeps finding ways to shuffle the wood so that the term continues to be applied incorrectly.

[bob]

Some positions predicted as a win, when there they are draw, could generate bad scenarios.

But this is exactly the situation you get with a KQKP-specific rule that only predicts correct draws. When this rule does not give an answer, you fall back on the regular eval which surely will predict a win for K+Q.

I philosophically agreed with your first post, but what I am trying to say is that you have to be very careful and conservative. Both offer risks (draws and win predictions) and benefits. But the win predictions are more problematic I think.

In a way, this is similar to have incomplete TBs. Here, we may have neighbor positions with predictions and some without. The search will pick and choose what path will benefit the most the side to move. The fact that this endgame have gazillion ways to repeat make the whole thing complicated. The way I have done it was to carefully cover all the "neighbor" and children position holes and the respective derivatives. For instance (I think), Sven's position was not covered in my analysis, but I believe I may have covered with rules all the possible derivatives. So, search has no chance to screw this.

This is like saying, I can have perfect information about KRPKR, but if you do not have good eval about KQKR (a derivative) problems arise. This was the typical problem saw with incomplete TBs. In this discussion, we may end up with a similar conceptual problem.

Miguel

I don't think it is a "win issue" as much as an "I apply" or "I don't apply" issue. If the rule thinks it applies, it ought to be right, because sometimes a draw score is still a large score change (say you are a queen up in QK vs PK). I typically get burned when a rule decides "I apply" but makes a mistake in reporting win/lose/draw values. When I make an error and don't apply such a rule when it really would give the right answer, I don't see the silly things showing up in the search, even though I obviously can see a move that the general-purpose eval doesn't get correct.

[tpetzke]

KRKR is in fact one of the easier ones. This one I implemented as DRAW unless one of the "exception rules" applies. For KRKR I required 11 exception rules and the recognizer spots about 75% of the Draws. Compared with other endgame types this is a very good ratio.

Code: Select all

Incorrect Draws : 0
Spotted   Draws : 11.547.632
Missed    Draws : 3.590.432
Spotted   Wins/Loss  : 6.423.392

The exception patterns are required to spot "Non Draw" positions like this which are not so trivial to detect

[D]8/8/8/2r5/3R4/8/8/K2k4 b - - 0 1

Thomas...