Feg / De Koning EDGB file format / indexing

[Tuhma]

Feg / De Koning EDGB file format

Let's start with indexing.

Feg uses 64-bit indexing that is divided to two 32-bit integers.

32-bits for white pieces and 32-bits for black pieces.
My opinion is that indexing is relatively simple compared to Nalimov indexing.

Let's call 32-bit part of index reserved for white pieces as a white index and
32-bit part of index reserved for black as a black index.

I will now present few examples because it makes everything very easy.
I found this data using feg -ll command line option.

Here is the first position:

[game KQQQKQQ_M085_001] [annotator hash o02106574 o00072275] [posj]
. . . . Q q . .
. . . . . Q . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . q . . . . .
Q . . . . . . .
. . K . . . . k w....

Here we see picture of position and its index number:
annotator hash o02106574 o00072275
o-means octal number so Feg prints here two octal numbers per piece.
One octal number is 3-bits and 2 octal numbers are 6-bits. Using two octal numbers
it is possible to present all squares of chessboard because 8*8 = 64.
Let's play with these two index numbers:
o02106574 = o02 10 65 74
o00072275 = o00 07 22 75

We made some spacing and now we see
that first part of the index has 4 pieces and second part of index has 3 pieces.
We can conclude that first part is for white and second part is for black.
And here space means end of field for one piece

Then we convert these octal numbers to decimal numbers:
o02106574 = o02 10 65 74 = 02 08 53 60 (white)
o00072275 = o00 07 22 75 = 00 07 18 61 (black)

Then let's use this square numbering for chessboard:

56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
08 09 10 11 12 13 14 15
00 01 02 03 04 05 06 07

And in Feg's picture capital letters means white pieces and lowercase letter means
black pieces.

Here are locations of white pieces using this square numbering:
02, 08, 53, 60
and here are locations of black pieces using this square numbering:
07, 18, 61

-> We see that the these numbers are exactly same as numbers in the index!

Very simple indexing!

Then we have en passant:
Example (e-means target square for en passant):
[game KPKP_M010_001] [annotator hash o00000042 o00003003] [posj]
. . . . . . . .
. . . . . . . .
. . . e . . . .
. . P p . . . .
k . . . . . . .
. . . . . . . .
. . . . . . . .
K . . . . . . . w....

and index:
annotator hash o00000042 o00003003
Let's do the same thing:
o00000042 = o00 00 00 42 = 00 00 00 34
o00003003 = o00 00 30 03 = 00 00 24 03

Here are locations of white pieces using previous square numbering:
00 and 34 (same as in the index)
and black pieces:
24 and 35. Here we find difference, but it is very easy to figure out:
We have en passant situation that needs special coding and we know that there must be
some trick. Also according to the index pawn is in the square 3 that is illegal but
it is in the same column that it is in the picture

-> We conclude that when it is white to move then en passant information is coded to
position of black pawn and vice versa. If pawn is target for en passant then
it is put to first row (illegal position) in the same column where it really locates.
Because feg stores only wins (distance to mate) in tablebase file
it can figure out en passant situation when it finds a win for this kind of illegal position.
It just moves pawn to right row.

I will write more about this topic later and I hope that There are not any mistakes
in this post. I just want to show that because feg file format is quite compact despite
of very simple indexing may be Nalimov indexing is too complicated.

Regards,

Tuhma

[Codeman]

There are two sides to indexing.
On the one hand, the better you index the smaller will be the final file you get (and the space requirements during generation). On the other hand, better indexing also means that it takes more time to load/generate the positions.

When using special index optimization, you should also be looking at how much space they save and how much more complicate they make the system.
One obvious thing the 8-fold-symmetry which reduces the size by a factor 8 is often used.
Very easy to implement and very powerful is the separate index-table for the two kings which may not be located next to each other.
Another possible optimization is the n-like men (reduces a factor n!)
Nalimov as well uses the fact that pieces from stm may not give unblockable checks.

There are many more possibilities but as I said, it is questionable whether they are worth the effort.
e.g. 2 knights from sntm may not give check at once.

Regards Edmund

[Tuhma]

Actually, De Koning EDGB file format use these 8x (pawnless) and 2x (with pawns) symetries in indexing. I also suspect that feg uses mailbox array board representation (12 rows and 10 columns).
I will write more about that later.

Tuhma