user27007: 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.

user9684: The fastest way to search a database is to use the same format as the database.  Searching a tree database with a FEN is slow as a conversion is needed for each move.  Although a shorter position storage would be useful, it's not likely to happen soon.

user10380: 24 bytes is 24 * 8 = 32 * 6 bits, giving us 6 bits for each of the 32 units, with none to spare. 6 bits gives just enough info to specify a square, with none to spare.
Specify, in this order, the positions of wK, wQ, 2 wRs, 2 wBs, 2 wNs, 8 wPs, then likewise for Black. Code that a unit is "off the board" by giving its position as the same as its side's king. However, this encodes only one-box positions: it fails to encode positions where a side has (say) 2 Qs.

user20803: You are on the right track.
With most databases, your most efficient organization would be a single user-defined table with two fields: your 64 (64 x 1) bit "square occupied" field, and your 128 (32 x 4) bit "next piece ID" field. The you instruct the database engine to sort the table and construct an index on the first field.
Don't worry about how to link the two fields or how to scan for the foreign key. Let the database engine do it; they're very good at this.

user25320: If you're just wanting to know whether a position has been occurred before (or keep count of occurrences), use a Zobrist hash. I believe X-piece endgame tables use Zobrist hashing. That boils down a unique representation of a position to a 64-bit integer. Polyglot opening books also use Zobrist hashing, and have standardised Zobrist keys, which might be useful for future compatibility (looking up occurring positions in an openings book)
Scanning through your approach you're not taking into account castling possibilities, en-passant possibilities, nor who is to move. These are important, because a position where the White king can castle is different to one with the exact same piece configuration but White cannot castle.

user27050: 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).

27007: <p>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.</p>
<p>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.</p>
<p>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.</p>
<p>The first table would be int id, and BINARY(8) <code>pieceExist</code></p>
<p>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.</p>
<p>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</p>
<p>The next table would be int id (foreign key from the first table) Binary(16) <code>pieceSpecification</code></p>
<p>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.</p>
<p>You would then find all ids where the <code>pieceSpecification</code> number you constructed has an equivalent value in the table.</p>
<p>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.</p>
<p>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.</p>
<p>Let me know if there are any problems with this or perhaps a better approach I could use.</p>
 9684: <p>The fastest way to search a database is to use the same format as the database.  Searching a tree database with a FEN is slow as a conversion is needed for each move.  Although a shorter position storage would be useful, it's not likely to happen soon.</p>
 10380: <p>24 bytes is 24 * 8 = 32 * 6 bits, giving us 6 bits for each of the 32 units, with none to spare. 6 bits gives just enough info to specify a square, with none to spare.</p>
<p>Specify, in this order, the positions of wK, wQ, 2 wRs, 2 wBs, 2 wNs, 8 wPs, then likewise for Black. Code that a unit is &quot;off the board&quot; by giving its position as the same as its side's king. However, this encodes only one-box positions: it fails to encode positions where a side has (say) 2 Qs.</p>
 20803: <p>You are on the right track.</p>
<p>With most databases, your most efficient organization would be a single user-defined table with two fields: your 64 (64 x 1) bit &quot;square occupied&quot; field, and your 128 (32 x 4) bit &quot;next piece ID&quot; field. The you instruct the database engine to sort the table and construct an index on the first field.</p>
<p>Don't worry about how to link the two fields or how to scan for the foreign key. Let the database engine do it; they're very good at this.</p>
 25320: <p>If you're just wanting to know whether a position has been occurred before (or keep count of occurrences), use a <a href="https://www.chessprogramming.org/Zobrist_Hashing" rel="nofollow noreferrer">Zobrist hash</a>. I believe X-piece endgame tables use Zobrist hashing. That boils down a unique representation of a position to a 64-bit integer. Polyglot opening books also use Zobrist hashing, and have <a href="https://web.archive.org/web/20190605035952/https://hardy.uhasselt.be/Toga/book_format.html" rel="nofollow noreferrer">standardised Zobrist keys</a>, which might be useful for future compatibility (looking up occurring positions in an openings book)</p>
<p>Scanning through your approach you're not taking into account castling possibilities, en-passant possibilities, nor who is to move. These are important, because a position where the White king can castle is different to one with the exact same piece configuration but White cannot castle.</p>
 27050: <p>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.</p>
<p>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.</p>
<p>0 - white pawn<br />
1 - black pawn<br />
2 - white knight<br />
3 - black knight<br />
4 - white bishop<br />
5 - black bishop<br />
6 - white rook that can't be castled with<br />
7 - black rook that can't be castled with<br />
8 - white rook that can be castled with<br />
9 - black rook that can be castled with<br />
A - white queen<br />
B - black queen<br />
C - white king if white has the move<br />
D - black king if black has the move<br />
E - the king that doesn't have the move<br />
F - a pawn that has just advanced two squares</p>
<p>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).</p>
