4 ms·
People have pointed out that due to rules about no repeats, the full state requires storing previous moves. I’m fairly convinced that the most efficient encodi
by jiggawatts 3y ago
People have pointed out that due to rules about no repeats, the full state requires storing previous moves.
I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state.
E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encoding is just 10 bits per ply. Typical games are 40 moves (80 ply) and hence require just 800 bits or 100 bytes for the whole game history.
Then you could get clever with Huffman coding or the like, since some moves are more common than others.
- paxys 3y agoAs the game goes on the space needed to store the list of moves increases while space needed to store a snapshot of the board decreases. It would be interesting to figure out where on average the strategies meet.
- teo_zero 3y agoThe problem is that the encoding of a position by the previous moves is not unique. For example, 1.a2-a3,a7-a6; 2.h2-h3 represents the same position as 1.h2-h3,a7-a6; 2.a2-a3... Chess engines need to remember evaluated positions to avoid reevaluating them, and this scheme doesn't work well for that purpose.
- verteu 3y agoI agree with this for a typical-length game. But I'd guess its worst-case is inferior due to some pathologically long games.
- jiggawatts 3y agoYes, but pathological games are statistically rare. At scale, the average is what matters…
- jiggawatts 3y agoReplying to my own post: it seems each move can be packed into 8 bits in all but a few rare scenarios such as having many promoted pawns as queens on the board. See: https://www.chessprogramming.org/Encoding_Moves#Per_Piece_and_Square https://www.chessprogramming.org/Encoding_Moves#Per_Piece_an...