syzygy wrote:Don wrote:That is an interesting proposal to only specify if the position is a draw. It would of course lead to really frugal use of memory.
But see also my
reply:
syzygy wrote:That is possible, but I don't think it would reduce their size by much. E.g. with KQvKR the positions where black K or R can immediately capture the white Q are already stored as "don't care". The few positions where black can mate or take the white Q in more than 1 ply don't take up much space, and the space that it takes up seems to be worthwhile since the evaluation will usually not catch these situations. Leaving it out would either result in erroneous results or force the engine to search a few more ply at each node where it could otherwise immediately return a result.
For tables that really have only two values such as KPvK or KBNvK, there would be no difference at all.
It is true that knowing it is a draw allows you to stop searching without a possibility of erroneous results. In the case of KQvKR draws are few, so instead of draw/non-draw it would be better to store win-for-Q/not-win-for-Q and leave the rest to the engine. Not such a bad idea, but I believe the gain is still quite minimal with proper compression. (And for those tables where the gain would be substantial because of winning chances for both sides, the extra information seems to be quite welcome.)
Yes, I can see that you cannot really cheat that much because of information theory - very little actual information removed when you do that for most databases.
At MIT we built a rubiks cube solver and we basically worked it from both ends and could find the perfect minimal solution for any cube presented. For positions close to the solved cube, which would correspond to simple endings in chess, I came up with an interesting technique - but I'm not sure it could be applied here - but it was a major gain in performance. Here is a brief outline of how it worked:
Using retrograde analysis I built a HASH table which contained 4 bit records. But each entry did not represent a specific position, it represented ALL the positions that hashed to this entry up to some depth. In the entry we stored the minimum depth of solution of any cube which hashed to this location. The search process itself was iterative so in the tree we could use this table to prune nodes. For example if we had 3 ply left to search and the entry value was 4, we knew that it was not possible to solve the cube from this position given the remaining depth.
The hashing function for the cube however was partial - we just hashed one face of the cube if I remember this correctly (this was 15 years ago give or take) and this had a positive effect on the idea although even a complete hash of the cube worked too. I think the partial hashing allowed a kind of implicit classifying of positions that made the table more effective. (We did other cool stuff too with this such as building a complete table for the 2x2 cube and treating the 3x3 cube as a superset of the 2x2 cube to get lower bounds too.)
Anyway, I have often considered doing some of my own research on more innovative approaches to chess endings such as some type of entry sharing scheme like this and hueristic assist. But good compress like is done now is hard to beat. The heuristic assist idea is to build a domain specific function that tries to solve the position heuristically but imperfectly with a much smaller "correction table" - such as a bloom filter. One problem with this is that the heuristic function must be correct a very high percentage of the time before the break even point. A table of exceptions requires many bits per exception and a good endgame bitbase requires less than 1 bit per position (but covers all positions.) So there is some break even point and due to the slow heuristic function one would want to see a pretty major gain in compression.
I have observed in some endings that just a few really simple rules will cover 99% or more of all positions, IF you can cover shallow tactics. KRPvsKR is dominated by many positions where a rook is captured due to a simple tactic, such as a skewer or fork.
A related idea is to simply build a specialized search for each ending as part of the database system. It's basically the same thing but a properly constructed very shallow deterministic search may get well over 99% of these right and you might be able to cover the rest with a small correction table. The interesting part of this would be to construct the evaluation function of such a search and that would likely need to be done in some automated way such as by simulated annealing. However I think there are some ending so profound it would be difficult constructing an accurate evaluation function that would be workable. Queen vs Rook comes to mind. Of course an automated learning system may find rules that no human would consider and turn this ending into a relatively simple one, who knows?
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
