Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-19T06:26:51.540Z
Answers.LastActivityDate: 2021-03-19T06:26:51.540Z
Answers.UserDisplayName: Anonymous
Answers.Body: <p>Recently, <a href="https://lichess.org/@/revoof/blog/adapting-nnue-pytorchs-binary-position-format-for-lichess/cpeeAMeY" rel="nofollow noreferrer">a Lichess blog post by developer revoof</a> described the binary format used by nnue-pytorch. It strikes a good balance between space optimization and fast to manipulate at the byte level.</p>
  <p>In summary, the variable-length format is similar to Anonymous's answer:</p>
  <ul>
  <li>64 bits (8 bytes) piece occupancy bitboard</li>
  <li>4 bits (half byte) per piece
  <ul>
  <li>16 possible pieces: 6 white pieces, 6 black pieces, white rook that can castle, black rook that can castle, black king storing it's black's move, and a pawn that has just moved two squares and can be captured en passant</li>
  </ul>
  </li>
  <li>(Optional extra data like half-move clock and ply in ULEB128 format, usually one byte each)</li>
  </ul>
  <p>Without the extra data, this is 8 + (32 max pieces)*(0.5 byte per piece) = 24 bytes max (openings will have the most pieces, and endgames the least). The average is 18.7 bytes.</p>
  <p><a href="https://i.sstatic.net/DqfeJL4E.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DqfeJL4E.png" alt="board format" /></a></p>
  <p>*Something weird about the diagram is the bitboard goes from rank 8 to rank 1 like FEN, but the piece list goes from rank 1 to rank 8. I don't know if there's a reason for this.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-23T18:54:09.460Z
Answers.LastActivityDate: 2024-08-29T15:00:52.250Z
Answers.LastEditDate: 2024-08-29T15:00:52.250Z
Answers.UserDisplayName: qwr
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T06:03:19.603Z
Answers.Text: This was the approach I wanted however there seems to be no 128 bit field that is possible. At the movement my 128 bit field is just 2 64 bit columns. Also though I said I  only wish to search how often a position has existed I realize some of the extra FEN info may be needed for that, i.e if castling is available. Because a identical looking position can be reached but maybe one side can't castle because of a king move
Answers.UserDisplayName: Marc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T15:32:56.107Z
Answers.Text: Nothing wrong with two 64-bit fields to store 128 bits, (Note that in many endgames the second of these will be zero.) - This results in three 64-bit unsigned integers.
Answers.UserDisplayName: A. I. Breveleri
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T16:58:29.207Z
Answers.Text: Yes, even with this problem the storage space saved per position is worth it, but perhaps I will explore some methods to condense bits if there are few pieces on the board
Answers.UserDisplayName: Marc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T00:57:37.397Z
Answers.LastActivityDate: 2021-03-17T00:57:37.397Z
Answers.UserDisplayName: A. I. Breveleri
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T00:04:54.780Z
Answers.Text: we can use 5 bits for bishop.
Answers.UserDisplayName: TigerTV.ru
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T06:05:08.563Z
Answers.Text: @TigerTV.ru Good point. And promoted Q so long as it's on rank 1 or 8. But this scheme isn't the best anyway -- Huffmann encoding of FEN can do better. I'd have deleted this answer except that for some reason SE didn't allow me, even when my answer's vote-count was 0.
Answers.UserDisplayName: Rosie F
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-16T11:33:20.123Z
Answers.LastActivityDate: 2021-03-16T11:33:20.123Z
Answers.UserDisplayName: Rosie F
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T21:27:57.580Z
Answers.Text: The castling conundrum is something I considered and mentioned in my comments to this and you are right, it is necessary to a position and would add a potentially 4 more bits I believe.
  Zorbist hash is something that came up in my research so I will look further into it now that you mentioned it, thank you for your comment
Answers.UserDisplayName: Marc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-03T15:03:04.717Z
Answers.Text: my implementation is also useful for now nnot future opening analysis. I just save the possible next moves and the SAN origin to the opening entry. Then I can climb in whatever direction I like, no need to store a million hashes while stripping the whole game away from it
Answers.UserDisplayName: Artiphishle
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-04T15:35:10.543Z
Answers.Text: I thought tablebases were exact, so could not use Zobrist hashing due to collisions?
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T19:59:38.670Z
Answers.LastActivityDate: 2021-03-17T19:59:38.670Z
Answers.UserDisplayName: MikeD
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-16T15:23:20.807Z
Answers.LastActivityDate: 2021-03-16T15:23:20.807Z
Answers.UserDisplayName: Mike Jones
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-15T20:45:39.060Z
Comments.Text: It seems this theory was explored nearly 20 years ago [link](https://groups.google.com/g/rec.games.chess.computer/c/wVyS3tftZAA)
  However I would like a modern take on this
Comments.UserDisplayName: Marc
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T00:31:40.333Z
Comments.Text: "for every square where a piece exists you create a ***4*** bit number which would specify color and type of piece" for a maximum of 128 bits.
Comments.UserDisplayName: A. I. Breveleri
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T01:13:47.420Z
Comments.Text: This scheme might make the DB more space-efficient, but it shouldn't significantly affect retrieval times compared to doing an exact string match query on a FEN string. Exact string match should be fast and constant time given a fixed maximum search key length.
Comments.UserDisplayName: bjb568
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T05:55:10.140Z
Comments.Text: @bjb568 I tested this with two tables of size 2 million
  The first table is ID, board structure, piece1, piece2 with a multi column index on the ladder 3. 
  The second table is ID, varchar 64
  The first table is 58% the size
  and searches are 1.8x faster
Comments.UserDisplayName: Marc
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T06:06:15.897Z
Comments.Text: By ladder 3 I mean, board structure (my 64 bit representation of the boat and if a piece exists on a square), piece1 and piece2 (which specifies what piece exists on each square where a piece exists)
Comments.UserDisplayName: Marc
Tags: <programming>
Title: Storing chess position in 24 Bytes
ThreadText: # Storing chess position in 24 Bytes
  
  (Asked by: username_0 on 2021-03-15)
  
  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.
  
  **Tags:** programming
  
  > **Comments:**
  > **username_0**: It seems this theory was explored nearly 20 years ago [link](https://groups.google.com/g/rec.games.chess.computer/c/wVyS3tftZAA) However I would like a modern take on this  
  > **username_1**: "for every square where a piece exists you create a ***4*** bit number which would specify color and type of piece" for a maximum of 128 bits.  
  > **username_2**: This scheme might make the DB more space-efficient, but it shouldn't significantly affect retrieval times compared to doing an exact string match query on a FEN string. Exact string match should be fast and constant time given a fixed maximum search key length.  
  > **username_0**: @username_2 I tested this with two tables of size 2 million The first table is ID, board structure, piece1, piece2 with a multi column index on the ladder 3.  The second table is ID, varchar 64 The first table is 58% the size and searches are 1.8x faster  
  > **username_0**: By ladder 3 I mean, board structure (my 64 bit representation of the boat and if a piece exists on a square), piece1 and piece2 (which specifies what piece exists on each square where a piece exists)  
  
  ---
  
  ## 6 answers
  
  ### Answer by username_3 on 2021-03-19. Score: 6
  
  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).
  
  
  ---
  
  ### Answer by username_4 on 2024-04-23. Score: 3
  
  Recently, [a Lichess blog post by developer revoof](https://lichess.org/@/revoof/blog/adapting-nnue-pytorchs-binary-position-format-for-lichess/cpeeAMeY) described the binary format used by nnue-pytorch. It strikes a good balance between space optimization and fast to manipulate at the byte level.
  
  In summary, the variable-length format is similar to username_3's answer:
  
  * 64 bits (8 bytes) piece occupancy bitboard
  * 4 bits (half byte) per piece
    + 16 possible pieces: 6 white pieces, 6 black pieces, white rook that can castle, black rook that can castle, black king storing it's black's move, and a pawn that has just moved two squares and can be captured en passant
  * (Optional extra data like half-move clock and ply in ULEB128 format, usually one byte each)
  
  Without the extra data, this is 8 + (32 max pieces)\*(0.5 byte per piece) = 24 bytes max (openings will have the most pieces, and endgames the least). The average is 18.7 bytes.
  
  [![board format](https://i.sstatic.net/DqfeJL4E.png)](https://i.sstatic.net/DqfeJL4E.png)
  
  \*Something weird about the diagram is the bitboard goes from rank 8 to rank 1 like FEN, but the piece list goes from rank 1 to rank 8. I don't know if there's a reason for this.
  
  
  ---
  
  ### Answer by username_1 on 2021-03-17. Score: 2
  
  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.
  
  > **Comments:**
  > **username_0**: This was the approach I wanted however there seems to be no 128 bit field that is possible. At the movement my 128 bit field is just 2 64 bit columns. Also though I said I  only wish to search how often a position has existed I realize some of the extra FEN info may be needed for that, i.e if castling is available. Because a identical looking position can be reached but maybe one side can't castle because of a king move  
  > **username_1**: Nothing wrong with two 64-bit fields to store 128 bits, (Note that in many endgames the second of these will be zero.) - This results in three 64-bit unsigned integers.  
  > **username_0**: Yes, even with this problem the storage space saved per position is worth it, but perhaps I will explore some methods to condense bits if there are few pieces on the board  
  
  ---
  
  ### Answer by username_5 on 2021-03-16. Score: 2
  
  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.
  
  > **Comments:**
  > **username_6**: we can use 5 bits for bishop.  
  > **username_5**: @username_6 Good point. And promoted Q so long as it's on rank 1 or 8. But this scheme isn't the best anyway -- Huffmann encoding of FEN can do better. I'd have deleted this answer except that for some reason SE didn't allow me, even when my answer's vote-count was 0.  
  
  ---
  
  ### Answer by username_7 on 2021-03-17. Score: 2
  
  If you're just wanting to know whether a position has been occurred before (or keep count of occurrences), use a [Zobrist hash](https://www.chessprogramming.org/Zobrist_Hashing). 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](https://web.archive.org/web/20190605035952/https://hardy.uhasselt.be/Toga/book_format.html), 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.
  
  > **Comments:**
  > **username_0**: The castling conundrum is something I considered and mentioned in my comments to this and you are right, it is necessary to a position and would add a potentially 4 more bits I believe. Zorbist hash is something that came up in my research so I will look further into it now that you mentioned it, thank you for your comment  
  > **username_8**: my implementation is also useful for now nnot future opening analysis. I just save the possible next moves and the SAN origin to the opening entry. Then I can climb in whatever direction I like, no need to store a million hashes while stripping the whole game away from it  
  > **username_4**: I thought tablebases were exact, so could not use Zobrist hashing due to collisions?  
  
  ---
  
  ### Answer by username_9 on 2021-03-16. Score: 1
  
  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.
  
  
  ---
  
  