Endgame bitbase / tablebase compromise?

[rjgibert]

White will be forced to allow a skewer check to avoid repeating, IOW the longest variation ends with the capture of the Q with a draw.

Prefer a loss over a rep-draw???

Black cannot force a capture of the queen here. Wanting too dodge a rep-draw even when the alternative is an unsufficient-material draw is no forcing at all.

The most one could say is that black can force a draw here. Which is true in any draw position. But does not mean that shallow tactics is involved. Usually it ends in a rep-draw or 50-move draw, and you don't want to search to a depth where you can see that. Such non-tactical draws will have to be recognized by the rules, or listed as exceptions.

White eventualy plays Kc6 to avoid a rep and after Rh6 Kc5 Rxb6 is a 3-man table base draw, yes?

[rjgibert]

A good starting point would be to program in the rules from Averbukh's book "Rook Endings". He give a very systematic treatment of KRPKR, very suitable for algorithmic implementation.

The problem is alway the tactical positions. Humans filter these automatically. E.g. KQKR is always won, provided there is no skewer that loses you your Queen. (The longest tactics where a Q loss or trade can be forced is 5 ply, starting with a check along the board edge to.) So the rules are easy to formulate, and there would be zero exceptions, leading to infinite compression.

Easy? You are probably right about that, but your assertion about the longest non-win by K + Q is off by a factor of 4 even when you prune off 2-fold reps in the following:
[D] k5K1/8/1Q6/8/8/8/8/7r b - - 0 1

[D] k7/8/1Q6/6K1/8/8/8/7r b - - 0 1

This is a bit trickier, but seems to work too.

BTW, Rybka 2.2 deals with this last position very poorly. It keeps wanting to play Rh7 instead of checking.

[hgm]

White eventualy plays Kc6 to avoid a rep and after Rh6 Kc5 Rxb6 is a 3-man table base draw, yes?

Why would white do that? What exactly is acheived by it?

[wgarvin]

A good starting point would be to program in the rules from Averbukh's book "Rook Endings". He give a very systematic treatment of KRPKR, very suitable for algorithmic implementation.

The problem is alway the tactical positions. Humans filter these automatically. E.g. KQKR is always won, provided there is no skewer that loses you your Queen. (The longest tactics where a Q loss or trade can be forced is 5 ply, starting with a check along the board edge to.) So the rules are easy to formulate, and there would be zero exceptions, leading to infinite compression.

Of course this is also an end-game where bitbases are of zero help, as no engine would be stupid enough to bungle away its Queen.

Another idea I had is to use a search based method. Essentially none of these endings have much "Kolmogorov Complexity" (the answer can be expressed by very simple programs) so it's only a matter of trying to find the right tradeoff between time and space. A search is a knowledge amplifier so an evaluation based on simple rules combined with a shallow search could express the knowledge contained in the bitbase in an extremely compact way if you are willing to trade off some CPU time. But with a search you have some control over how to do this trade-off.

I don't like the idea of having to search to confirm stuff from the bitbases. The whole point of bitbases in memory (from my point of view) is to allow cutoffs with exact win/loss/draw info at any interior node in the search tree. It might be okay to omit a small fraction of the positions which are difficult to classify correctly using just rule-based stuff.

What I would like to see, is to start with a complete bitbase, and then try to reduce it into one or more table-lookup-based things that predict the results of the bitbase with high (but maybe not perfect) accuracy, but using a much smaller index space. Maybe by dropping one piece from the index, or combine the squares of two pieces together into an index and then map it onto a much smaller index, or something like that. Maybe combined with some simple rule-based things. This treatment would probably be different for each ending, so coming up with compact and mostly-accurate representations of all of the 5-piece endings sounds like quite a lot of work. Maybe you'd make 2 to 4 separate predictors for each ending and combine their results. One problem is that the slower it gets, the less useful it is.

[Don]

A good starting point would be to program in the rules from Averbukh's book "Rook Endings". He give a very systematic treatment of KRPKR, very suitable for algorithmic implementation.

The problem is alway the tactical positions. Humans filter these automatically. E.g. KQKR is always won, provided there is no skewer that loses you your Queen. (The longest tactics where a Q loss or trade can be forced is 5 ply, starting with a check along the board edge to.) So the rules are easy to formulate, and there would be zero exceptions, leading to infinite compression.

Of course this is also an end-game where bitbases are of zero help, as no engine would be stupid enough to bungle away its Queen.

Another idea I had is to use a search based method. Essentially none of these endings have much "Kolmogorov Complexity" (the answer can be expressed by very simple programs) so it's only a matter of trying to find the right tradeoff between time and space. A search is a knowledge amplifier so an evaluation based on simple rules combined with a shallow search could express the knowledge contained in the bitbase in an extremely compact way if you are willing to trade off some CPU time. But with a search you have some control over how to do this trade-off.

I don't like the idea of having to search to confirm stuff from the bitbases. The whole point of bitbases in memory (from my point of view) is to allow cutoffs with exact win/loss/draw info at any interior node in the search tree. It might be okay to omit a small fraction of the positions which are difficult to classify correctly using just rule-based stuff.

What I would like to see, is to start with a complete bitbase, and then try to reduce it into one or more table-lookup-based things that predict the results of the bitbase with high (but maybe not perfect) accuracy, but using a much smaller index space. Maybe by dropping one piece from the index, or combine the squares of two pieces together into an index and then map it onto a much smaller index, or something like that. Maybe combined with some simple rule-based things. This treatment would probably be different for each ending, so coming up with compact and mostly-accurate representations of all of the 5-piece endings sounds like quite a lot of work. Maybe you'd make 2 to 4 separate predictors for each ending and combine their results. One problem is that the slower it gets, the less useful it is.

I'm looking at this more abstractly than you are. You have a function called oracle() which returns whether it is a win/loss or draw. That function could do what you suggest, it could do what I suggest or anything it wants that is guaranteed to always return the correct result.

If that function has a search routine inside of it, it is independent from the real search in the program - it is just an implementation detail. In fact I could in theory code this up and send you a library that just works and you would never know that it had a small search component.

So I don't care how it works as long as it's far more space efficient than using an actual bitbase and as long as it's faster than a regular database. The only chance it has of being faster (given that we expect to trade CPU work for table size) of course is if it can avoid the disk accesses issues that can slow down a program using the big databases.

[rjgibert]

White eventualy plays Kc6 to avoid a rep and after Rh6 Kc5 Rxb6 is a 3-man table base draw, yes?

Why would white do that? What exactly is acheived by it?

It's the longest draw. It's how far an engine has to look to determine whether the position is a draw. You know and I know it is a draw, but the engine doesn't know until it actually tries it. When everything else draws, it is finally left no choice.

I think you might be led astray by the behavior of many chess engines that might try Kc6 or Kd6 early on with a relatively shallow search and then later avoid these moves, because it is a hash cutoff. This behavior can give the PV the flavor of a random walk in such positions. But we're not talking about an ordinary chess engine here.

This isn't that big a deal to me. I'm not interested in tilting at windmills. I prefer to move on.