Storing chess position in 24 Bytes I want a fast way to search how many times a certain position has appeared in a database of hundreds of thousands of games. I researched the best way to store positions in a database but all of the solutions were quite large and were stored as strings.
I thought of a different way and I was wondering if this would work or if there are some corner cases I did not consider.
Remember, the point of this storage would be to quickly search if a position had ever been reached before and not used to reconstruct entire games.
The first table would be int id, and BINARY(8) pieceExist
Starting from the top left of the board and reading to the right a1 would be set in a 64 bit number if any piece exists in that square and a 0 otherwise.
I would search this table first and retrieve a list of ids where pieces were in the same position as the board I am looking at
The next table would be int id (foreign key from the first table) Binary(16) pieceSpecification
This table specifies what piece is in each position, for every square where a piece exists you create a 4 bit number which would specify color and type of piece, which would has only 12 unique combinations. You would not need to store any information on where this piece is placed on the board as that is specified in the 64 bit number in the other table.
You would then find all ids where the pieceSpecification number you constructed has an equivalent value in the table.
You could probably off the database do a joint on the two sets of ids to see how many times your position has appeared in the database.
I reckon this approach has many benefits. Space in the database is minimized and searches would hypothetically be able to be completed in a matter of milliseconds.
Let me know if there are any problems with this or perhaps a better approach I could use.
You can use the first 64 bits to encode which squares are occupied, and then encode what's in the occupied squares one by one, using four bits per square for up to 32 occupied squares.
The four bits allow sixteen possible piece types. There are only twelve types of pieces, but this lets us get in some additional necessary information. Here's an example encoding scheme.
0 - white pawn
1 - black pawn
2 - white knight
3 - black knight
4 - white bishop
5 - black bishop
6 - white rook that can't be castled with
7 - black rook that can't be castled with
8 - white rook that can be castled with
9 - black rook that can be castled with
A - white queen
B - black queen
C - white king if white has the move
D - black king if black has the move
E - the king that doesn't have the move
F - a pawn that has just advanced two squares
This should be enough to specify the position (piece locations, player to move, castling rights and en passant, but not fifty-move counter or move number).