mmt wrote: ↑Sat Dec 12, 2020 3:43 am
syzygy wrote: ↑Sat Dec 12, 2020 1:43 am
How are you going to "mark" a position "as having the true value stored" without encoding this in the value you store for the position?
One way could be like I wrote earlier: true value (1 bit, ignoring cursed wins/losses), gap (maybe 7 bits, maybe depends on the endgame), true value, gap... A sort of simplified RLE. I don't know if it's near optimal. I do know that my scheme reduces entropy significantly compared to storing all values (I know that you're not exactly storing all values in your tables), which should result in better compression ratios.
syzygy wrote: ↑Sat Dec 12, 2020 1:43 amAnd for a "marked" position, how are you going to store a choice from W/D/L with just 2 possible values? The true value is one of three values W, D, L.
If the search returns W, then 0=D, 1=L. If the search returns D, then 0=W, 1=L. If the search return L then 0=W, 1=D.
Ok, so you are basically storing two tables. A first table with a value for each position indicating whether a shallow search returns the correct value, and a second table with a value for each position for which the shallow search does not return the correct value.
With the right compression method, I suspect it would be more efficient and simpler to combine these two tables into one.
The simplest way would be three values 0, 1, 2.
0 = use predicted outcome
1 = use most likely outcome among W, D, L different from the predicted outcome
2 = use least likely outcome among W, D, L different from the predicted outcome
where most/least likely is determined according to the frequencies of W, D, L as outcomes for the particular table.
This can probably be improved by conditioning on the predicted outcome. For example, if the predicted outcome is W, then D might be more likely than L even if for the table as a whole L is more likely than D.
syzygy wrote: ↑Sat Dec 12, 2020 1:43 am
Do you mean a fixed but different number of nodes per endgame? That is going to be a lot of tuning for each table.
Not a single fixed number but a few parameters for each endgame for SF invocations that use the iterative deepening scheme I described earlier.
Tuning should be easy: you just take a random sample of let's say 10k positions from the endgame and optimize the parameters (number of nodes searched, cutoff scores for draws and wins/losses for, let's say, 3 iterations) using your favorite method to get the best score based on what you want the tradeoff between the size and speed to be. That's what I did manually to go down from an average of 200 nodes to 90 nodes without any loss of accuracy for 62 large EGTBs.
OK, that is indeed doable.
Using a predictor and encoding only the delta between the predictions and the true values is not a new idea but, as far as I am aware, has never worked (or perhaps: has never been implemented) especially well.
Syzygy tables use the following "predictor":
- if there is a winning capture, it is a win (meaning that the position can be encoded with whatever value compresses best);
- if there is a drawing capture, it is at least a draw (meaning that a draw can be encoded as a loss for that position if that is more space efficient);
- otherwise, the position is like any other position in the table, and the compression algorithm will ensure that more likely outcomes are encoded more space-efficiently.
The (partial) "don't care" aspect of this encoding is used in the first ("Re-Pair"-based) compression phase (one can do much better than statically assigning the same value to all don't cares). This also takes care of illegal positions/index values, which can also be encoded with whatever value compresses best.
One can go further by looking at checking moves. If there is winning checking move, the position is a win, etc. But this is getting a lot more expensive since you would need to probe the same 7-piece table many times (the captures by definition enter smaller tables), potentially leading to a combinatorial explosion. Perhaps it is better to look for forced combinations check-evasion-winning/drawing capture, which avoids having to probe the same 7-piece table multiple times during a probe (this is something I wish I had tried when writing my generator).
I think a regular predictor (e.g. based on SF) cannot fully make use of the definite information (including no information) that can be obtained by a relatively cheap single round of captures (perhaps including checking moves). However, it should be possible to combine the approaches. This does seem tricky, though.
If the approaches are combined, the regular predictor's main task is to do well on "quiet" positions that do not have a winning capture or winning checking move. I doubt that SF is the best possible predictor in terms of time vs quality.
Whether that would work would depend on how accurate it could be made.