I guess everything will depend on how the bits are distributed.chrisw wrote: ↑Thu Jun 24, 2021 10:34 pm I suppose one could view it as a problem of finding the one bits in a (very) sparsely populated bit stream. For (very) simple endings, there'll be quite some periodicity in the stream, you could probably construct the stream using variables like stm and distance to queen and so on. Or, why not reverse the problem, brute force find the variables and the polynomial connecting them backwards off the bit stream. Probably PyTorch or Scipy will do it for you. I jest, alhough something may be possible. Then put that in your evaluation and smoke it.
one could improve the binary search over indices by reserving n bits for repeat count, like 3 bits and then you save up to 7 indices in cases where there are 8 consecutive draw bits sets or something like that
but as hgm said, sometimes even log n is just too slow, I don't know.
EDIT: if the assumption that there are lots of repetitive patterns is true, one might do even better by having and extra lookup table, say for each n bits and simply store a starting bit index for the entire group. assumining uniform slicing, one might save some space while still retaining O(1) lookup, if such slices are sufficiently large, but all this would have to be tried I guess, perhaps there's more to it
also, if I'm not mistaken syzygy only stores the tables for one side and uses 1-ply search for the other, effectively cutting the data in half, but I may be wrong on this