How to store a chess position in 26 bytes (2022)
ezzeriesa.notion.site
How to store a chess position in 26 bytes (2022)
1–10 of 108 posts
Re: How to store a chess position in 26 bytes (2022)
#226 bytes is 208 bits, about twice what you really need for a minimal encoding that has enough context (en passant, castling) to generate an accurate set of legal moves. I wrote a chess database tool back in the 90's (CDB) that used 96-bit encodings (if memory serves) to index all the positions reached in a collection of games so that one could see the moves made from any position, their frequencies, and their game outcomes. Good fun.
Re: How to store a chess position in 26 bytes (2022)
#3Previously discussed (2022):
Re: How to store a chess position in 26 bytes (2022)
#4Very clever, but that's the problem, clever is never the correct solution.
With a few bytes more more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't.
Re: How to store a chess position in 26 bytes (2022)
#5This is fun. Of course this problem is also a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers. Hitting the calculator 26 bytes works out to chess being no more than 4.113761393×10⁶² possible states. I'll start my GPU solving that right now!
[edit] This made me look for articles estimating this and I found this one [1] which confirms the above is in the right ballpark. Actual study (according to the article) says 4.822 x10^44 is their upper bounds
[1] https://chess-grandmaster.com/how-many-possible-chess-positi...
Re: How to store a chess position in 26 bytes (2022)
#6Very clever, but that's the problem, clever is never the correct solution. With a few bytes more more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't.
If you are writing a chess engine you'll want to store hundreds of millions of positions while you search for the best move and at that scale a byte is important because it gets multiplied by an enormous factor.
Re: How to store a chess position in 26 bytes (2022)
#726 bytes is 208 bits, about twice what you really need for a minimal encoding that has enough context (en passant, castling) to generate an accurate set of legal moves. I wrote a chess database tool back in the 90's (CDB) that used 96-bit encodings (if memory serves) to index all the positions reached in a collection of games so that one could see the moves made from any position, their frequencies, and their game ou…
96 bits is not nearly enough, as there are ~4.8 * 10^44 > 2^148 legal chess positions (with side to move/castling/ep info) [1].
Chess Position Ranking provides a 153 bit encoding but it's very slow to decode.
If the encoding only needs to work for the set of positions occurring in some database, then there's almost no limit to the number of coding optimizations one can make (until the encoding just becomes an index in the set of all unique db positions).
Re: How to store a chess position in 26 bytes (2022)
#8Very clever, but that's the problem, clever is never the correct solution. With a few bytes more more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't.
If you are writing a chess engine you'll want to store hundreds of millions of positions while you search for the best move and at that scale a byte is important because it gets multiplied by an enormous factor.
But that is a totally different problem which requires far fewer bytes to represent. For that problem you are just considering of the valid pieces which made a move and what board that came from. Storing a single move is far cheaper than an entire board state.
Re: How to store a chess position in 26 bytes (2022)
#926 bytes is 208 bits, about twice what you really need for a minimal encoding that has enough context (en passant, castling) to generate an accurate set of legal moves. I wrote a chess database tool back in the 90's (CDB) that used 96-bit encodings (if memory serves) to index all the positions reached in a collection of games so that one could see the moves made from any position, their frequencies, and their game ou…
Given the current upper bound on legal chess positions is 7.7e45 ≈ 152.4 bits, you either have found a better upper bound or your memory doesn't serve.
Re: How to store a chess position in 26 bytes (2022)
#10Very clever, but that's the problem, clever is never the correct solution. With a few bytes more more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't.
This is pretty standard ( or at least used to be 20 years ago ) in high performance chess programming, see