Hello, my name is Richard. I am new to this forum and I am glad I joined
I want to do a custom database of games played by engines.
I am wondering how to store efficently these games and what would be the fastest way to find the games which match a given FEN.
I had the idea to store both the PGNs and a data file that contains 2 columns, first column being the unique hashes of positions and the second column being the paths (or an ID with which we can find the path of the PGN file)
to the PGNs that match the hash.
This way, it takes time to precompute but is fast at runtime to find a position.
Is my idea good or is there something simpler/better?
A compact way for storage is binary, using 1 byte per move. You just assign each number in the range 0-255 to a combination of a piece, and a move for a piece of that type. E.g. Pawns would each have 4 move codes, Kings and Knights 8, Rooks and Bishops 14 and Queens 28.
From a list of moves encoded this way you can easily reconstruct games by keeping a board array that contains piece numbers, and a piece list that for each piece numbet contains the square that piece is located. The move is used as index in two tables, to get the corresponding piece number and board step.
I you are looking for an exact position you could keep track of hash key for the position (e.g. Zobrist hashing) that you update incrementally on every move, and compare that to the key of the sought position. Only when there is a match you would have to do a full comparison of the positions. If you also want to be able to search for partial positions (e.g. when the presence of extra pieces should not spoil the match) then there seems to be no alternative to comparing the board itself for a piece-type match on every square.
You mean 1 byte per move because of the 6 choices for the Q,K,R,B,N,P (6 pieces so 3 bits) and the maximum amount of moves per piece is the Queen in the middle of the board (27 moves = 5 bits), so we can stock everything on 3+5 bits = 1 byte right?
You cannot use separate bits for type and move, as you would then need to reserve 27 moves for each Pawn in the code space as well. You cannot just indicate piece type, like you suggest, but would have to indicate which piece of that type you mean.
But this can all be achieved by using 0-3 for the moves of Pawn number 1 (the Pawn that started in the a-file), 0 = straight ahead, 1 = capture left, 2= capture right, 3 = double push. And then 4-7 for Pawn number 2, etc, until 28-31 for Pawn number 8. Then you use 32-39 for the 8 King moves, 40-47 for Knight 1, 48-55 for Knight 2, etc. A Rook can do with 14 moves if you imagine that the board wraps around in toroidal fashion: 1 to 7 steps 'upward', or 1 to 7 steps to the right. Same counting for Bishops, along the left and right forward diagonal. You will need two more codes for the castlings.
You even have enough codes to assign 12 to each Pawn, in order to account for under promotion: that would require 8x12 + 3x8 + 4x14 + 1x28 + 2 = 206 codes. So it still leaves enough codes for a super-numerary Queen.
To really allow for all possible cases you could ever encounter (e.g. like having 9 Knights) you can define one of the byte codes (say 255) as an 'escape', to be followed by two bytes specifying the origin and destination square. This will never occur in practice, so you don't care that this is not optimally compact.
Another advantage by saving it my way is that it is colour agnostic so it will be even more space efficient and will also be able to recognise positions that actually has not been played by the other side.
If you want a failsafe simple way of storing a chess move in a byte is to use an existing correct legal move generator and save the index. To retrieve the move later you can generate all the legal moves from the position with the same generator and pick the move stored at the stored index position.
