clgd wrote:How does this strike you all as a middle-ground between bitbases and tablebases?
I don't think storing the best move offers any advantage over storing the DTM. In general there are fewer DTMs than there are possible moves.
Basically you try to take advantage of the fact that the tablebase is very sparse, and are looking for a way to compress it without making access unduly slow. A hash table cod be one way of doing that.
I have considered various schemes for that - but it's hard to beat the compression already being used.
It occured to me that with a bitbase you could have an algorithm that predicts whether a given ending is a win, loss or draw and then just store the exceptions in a hash table or bloom filter type of data structure. To make this work well I believe the hit rate of the predictive algorithm has to be pretty high because compressed bitbases are already very compact. Properly constructed bloom filters cannot be compressed because thet already look like random numbers.
For predicting whether a particular position from a simple ending is a win/loss or draw I wonder if some kind of classification algorithm will do it.
You could build a set of characteristics that you think have some predictive power and perhaps apply a naive bayes classifier to them or mabye some kind of decision tree. An exception table could identify the positions that were classified wrongly by this classifier, perhaps a bloom filter or even a simple sorted list.
Surely something like this has already been tried. To be worthwhile this would have to save both time and space and apparently this is not so simple, otherwise it would have been done by now. Since the big tables require disk accesses, you can probably save time even if the algorithm is fairly involved, as long as it does not require disk access. But to not require disk accesses (or too many of them) the representation probably has to be well over an order of magnitude more compact.
It would be fun to try this with the KRP vs KR database. I don't think any other 5 piece database is very important compared to this one.
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.
hgm wrote: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.
hgm wrote: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.
I looked at a rule based approach to this ending a few years ago. I remember that most of the rules had exceptions that were based on tactics. So it seems like most of the rules might work if they were combined with a tiny little tactical search. That's partly why I'm speculating about a hybrid approach where a separate module analyzes the ending with, for instance, a 3 ply search with a win/loss/draw evaluation function.
Whatever might be done - the general principle is to trade off a little domain specific knowledge for space. Even bitbases take an enormous amount of space.
hgm wrote: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
hgm wrote: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
hgm wrote:The longest tactics where a Q loss or trade can be forced is 5 ply, starting with a check along the board edge to.
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
You can't force a Q-trade here, not?
But you have a good point; the rule would deinitely have to accont for stalemate positions with a rabid rook.
hgm wrote:The longest tactics where a Q loss or trade can be forced is 5 ply, starting with a check along the board edge to.
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
You can't force a Q-trade here, not?
But you have a good point; the rule would deinitely have to accont for stalemate positions with a rabid rook.
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.
rjgibert wrote: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.
