I compress out "threat positions" in my suicide tablebases (suicide chess has compulsory captures), but I am not sure that I do the same thing. Or actually, I am pretty sure that I don't do the same thing.
What I do is this:
- if the position has one or more captures, play out the captures (resulting in probes into smaller tables). The value stored can be any value (whichever compresses best).
- if the position does not have a capture, try out all "threat" moves that result in a position where the opponent can (and therefore must) capture. If one of the threat moves is winning (i.e. leads to a position in which all the captures by the opponent lose), then any value can be stored (whichever compresses best). If the best threat move draws and the position is a draw, then we can store either a draw or a loss (whichever compresses best).
Finding the values that lead to best compression in my compression scheme is quite likely NP-hard, but I found some heuristics that do quite well.
I only compress out "threat positions" in my 6-piece (suicide) tablebases, as it does slow down accesses (leading to a small search explosion if it needs to be done recursively). It saves about 50%. (Many tables are reduced to zero: all positions that do not have a capture or a winning or drawing threat move are losses.)
One heuristic used in draughts databases is to continue the current run in order to optimize the run-length compression. I think it's NP-hard otherwise, as you noted.
I probably got the idea from Building the Checkers 10-piece Endgame Databases
, but what this paper describes seems a bit different:
Whenever you probe a capture or threatened capture position, you then do a search until you reach a quiet position for which the actual WDL or DTC value is stored in the db.
What is a "threatened capture position"? A position where the side not to move would have a capture?
If that's the case, then this trick seems similar to the removal of in-check positions (which I don't do, but which most likely is done by Shredder and I believe by some versions of Robbobases).
Yes, a threatened capture is one where the side not to move can capture.
Because in 8x8 checkers captures are compulsory, kings only capture short-ranged, and men only capture forward, the search tree is rather small and this tradeoff is good for performance. For 10x10 draughts with long-range king captures and backward-capturing men, this optimization does not work as well because the search trees become too large.
Do I understand correctly that those search trees are full of probes into the same database?
That depends: for capture positions, the side to move captures, and so you get a position with fewer pieces. These are typically stored in separate databases. For threatened captures, you play out all the moves for the side to move. Some of those moves will block the pending capture, and you will then look up the resulting position in the same database. Other moves will keep the capture opportunity for the opponent in tact, or create new captures for either side, which then also have to be resolved, ultimately in other databases.
BTW, this is what causes the search explosion. It's actually very similar to quiescence search: you just resolve all moves (using alpha-beta of course) until you have a quiet position with no captures pending for either side. Then you apply the evaluation function, or in this case, do the table lookup. For endgames with kings on both sides, you also need to have some kind of repetition detection in the qsearch in order to weed out "perpetual checks".