There is a way to represent a book using 1 byte per move. The old spraklen programs used this to conserve space. You basically build a tree where 6 bits represent the move (the Nth move in a sorted legal move list) and 2 bits shape the tree. You can think of the 2 bits as left and right parenthesis. Left parenthesis starts a new child node, right parenthesis closes the current node. So a book with 2 choices for white only looks like this:
(e4)(d4)
And can be expressed with 2 bytes.
Since it's recursive, you can build a sub book inside one:
(e4(e5))(d4)
Easily parsed by a computer of course. One limitation is that it cannot handle a position with over 64 moves but I'm pretty sure that is rare enough that you can build a practical book with it. 64 is not the actual limitation - if there are 70 legal moves you are still ok if the one you want is one of the first 64.
None of this is really interesting for books however unless you are building a program for a highly constrained toy computer with severely limited memory.
But your idea might be interesting in the context of an endgame database. Let's assume a bit base. If you can produce a function that gets the right answer the majority of the time, you would only have to store the exceptions. However a bit base is already very compact and it's difficult to improve on that. There is no regular pattern to the exception list so you have to store each one with many bits. So your function must be almost perfect if you expect substantial savings, perhaps needing to get it right 99% of the time or more. Keep in mind that many endings are mostly wins or draws anyway and are compressed - so you will beat your head against the wall trying to improve on this with heuristics.
I came up with an interesting data structure when building a perfect Rubiks cube solver many years ago. The solver found the shortest solution. It was a very difficult problem back when I did this because computers were slow and did not have much memory. Such an idea might work for an endgame database combined with a search. Here is how it worked for the cube:
1. Build a fixed size hash table.
2. From the solved cube, work backwards.
3. From each position hash the cube.
4. Don't worry about collisions in the hash table.
5. Store the current depth in the hash table entry IF it's the lowest depth that hashes here.
Each entry was only 4 bits.
So given any cube I could do a lookup in the hash table and tell you that the solution is at least N ply away. I shared many positions with a single entry by doing this. During the search this could prune away enormous sub-tree's because the search was iterative and I could stop searching if the remaining depth was less than this value. You pre-build this table with a depth first search until it is completely full and it can be any size, the bigger the better.
Sergei S. Markoff wrote:Current eval functions and shallow searches are good predictors for the deep searches. So, when you're need to store tree (in openings book, EGTB or TT) it's possible to store _only_ moves that are differs from "obvious". Possible it can reduce amount of stored info by many times. Anyone tried this approach?