It also showed a couple of less than optimal design decisions which I'm considering correcting in an all new version.
The first of these decisions was the choice of indexing scheme. I picked the one which may have been the simplest, but for only a modest increase in complexity a significant savings (13+%) in space may be achieved. Back then I did not know about Ken Thompson's scheme (indexing by king squares); had I known, I would have used it instead.
The second decision was to delay the inclusion of en passant captures, thinking that I'd just add it later. That particular "later" never came and that's why I never got correct tablebase files for all the KxPKP classes.
The third bad decision was to force all score values to be mapped into a single byte. With this, it's impossible to handle many of the six man classes. Likewise, forcing the index into a four byte integer precluded generating any six man class.
Bad idea number four was to require the intermediate generation file format be the same as the file result format. This led to even more space inefficiencies.
The last poor design decision was to have flat files for output; a much better idea is to prefix the score data with some metadata which describes the indexing, score ranges, and bit lengths of values.
So now I'm thinking about a re-write. Back in the Old Days I was mostly stuck with a Mac Plus with 4 MB RAM and a slow 20 MB drive; things have certainly changed since then.
The king squares indexing uses a 64x64 look-up table indexed by king squares to select a segment of contiguous score data along with a reflection selector bit vector.
For an endgame without pawns, the primary king is mapped into the a1-d1-d4 triangle using from zero to three different reflections to select one of 564 segments.
For an endgame with at least one pawn, the primary king is mapped into the a1-d1-d8-a8 rectangle using at most one reflection to select one of 1,806 segments.
Within each segment, the score entry of interest is selected using the locations of the non-king men. For N non-pawn men, there are N^64 entries. If pawns are included, then things are a little different as a pawn is restricted to one of 48 (not 64) squares; a pawn on the first rank is considered to actually be on its fourth rank after a double advance with at least one legal en passant reply.
Code: Select all
Triangle map (no pawns): 1 * 60 = 60 3 * 58 = 174 6 * 55 = 330 sum = 564 564 segments man count / score count 3 / 36,096 4 / 2,310,144 5 / 147,849,216 6 / 8,462,349,824 Flank map (has at least one pawn): Permitted: 2 * 60 = 120 12 * 58 = 696 18 * 55 = 990 sum = 1806 1806 segments man count / score count 3 / 115,584 4 / 7,397,376 5 / 473,432,054 6 / 30,299,652,096