I wish these articles acknowledged that densely packed structures like that have significant overhead in terms of the instructions which must be generated to parse them. If that shit gets inlined all over the place, how much bigger is the binary now? Absolute minimalism is rarely the right choice, the size of .text matters too.
How to store a chess position in 26 bytes (2022)
31–40 of 108 posts
Re: How to store a chess position in 26 bytes (2022)
#3226 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.
Now I'm wondering if it is a "legal" chess position to get the pieces to swap sides ... a solver to find how to do it would be amusing.
Re: How to store a chess position in 26 bytes (2022)
#33I don't understand the castling part of this - you can move a rook from its starting square and back and castling isn't available - it says that you can determine whether castling is available from the location of the pieces?
If the rook has the king's position, it's never moved. As soon as it moves, it can have any position except the king's.
i think i just misunderstood the writing, it does explicitly say 4bits for castling. the prose around is just describing what castling is - i thought it was implying that you could determine whether castling is possible from the position of the pieces.
Re: How to store a chess position in 26 bytes (2022)
#34Lichess uses a scheme which is probably more efficient on average, described on revoof's blog[0]. Basically, it's a variable length scheme where the first 64 bits encode square occupancies, followed by piece codes (including castling, side to move, and ep with some trickery), followed by half-move clocks if necessary.
0: https://lichess.org/@/revoof/blog/adapting-nnue-pytorchs-bin...
Re: How to store a chess position in 26 bytes (2022)
#3526 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 i…
Yes, that number just can't be right; thank you for the check.
Re: How to store a chess position in 26 bytes (2022)
#36Why not do it simpler? :
Create an array with 16 elements, one element per piece, black + white.
Every array element is 7 bits wide, 1 bit for captured or not,
and 6 bits for the square number the piece is on (8 x 8).
Then you need 16 * 7 = 112 bits = 14 bytes.
(And the captured-bit can even be compressed further as a 65th square,
but that makes it more calculation intensive to extract a position)
Re: How to store a chess position in 26 bytes (2022)
#37Very 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.
If they cared about that, then it wouldn't have been written in python. This is an exercise of the author showing how clever they are.
Re: How to store a chess position in 26 bytes (2022)
#38Why not do it simpler? : Create an array with 16 elements, one element per piece, black + white. Every array element is 7 bits wide, 1 bit for captured or not, and 6 bits for the square number the piece is on (8 x 8). Then you need 16 * 7 = 112 bits = 14 bytes. (And the captured-bit can even be compressed further as a 65th square, but that makes it more calculation intensive to extract a position)
+ 3 bits for piece type?
Re: How to store a chess position in 26 bytes (2022)
#39Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position. The problem here is that drawing can become an option or a requirement based on information that this representation doesn't capture. First the simpler version of this problem. After 50 full moves without a capture or pawn move, a draw MAY be claimed. After 75 moves, a draw MUST be claimed. T…
Both examples you have provided are not exactly pertaining to chess POSITION, but rather technicalities to put an upper bound on the time a game may take. Yes, there are rules like 75-move rules, or three-fold repetition, but they have no material bearing on the pieces. On the other hand, FEN does capture information like whether you're eligible for castling, which does make a difference in terms of chess position.
Re: How to store a chess position in 26 bytes (2022)
#40Earlier quoted context omitted.
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.
Not when you include transpositions, where you arrive at the same position from a different move order, in which case saving board states instead of moves could be very valuable.
There are transposition tables for that though. They don't store the board state actually. For Stockfish, transposition table entries are 10 bytes each, 16 bits of which are the low bits(or high? Can't remember) of a zobrist hash of the board state. The other 48 bits of the hash are used for addressing into the hash table, but aren't stored in it. The rest of the entry will be stuff like the best move found during the previous search(16 bits), the depth of that search(8 bits), evaluation(2 different ones at 16 bits each), and various bits of data like node type and age of the entry(for deciding which entry to replace, because this table is always full). Collisions can occasionally happen, but saving a full board state to eliminate them would cost far too much, since no matter how big you make the table, it'll never be big enough to cache all the board states a search visits.
In Stockfish, there will only be one full-fledged board state in memory per search thread. So the size of the board state is pretty much irrelevant to performance. What's important is reducing the overhead of generating possible moves, applying those moves to the board state, and hashing the board state, which is what magic bitboards are for.