3 ms·
26 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 lega
by pklausler 9mo ago
26 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.
- tromp 9mo ago96 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). [1] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking
- gowld 9mo ago"legal chess positions" is a larger space than pklausler's "observed chess positions". Novel positions reached in future that violated the 96-bit encoding could be encoded using a variable-length additional "patch" suffix.
- pklausler 9mo agoYes, that number just can't be right; thank you for the check.
- eulgro 9mo agoGiven 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.
- wongarsu 9mo agoThey didn't try to encode all legal positions though, only ones that were actually reached in their database of games. It sounds very plausible to me that this allows a lot of simplifying assumptions that cut the state space by about 60 bits
- mlyle 9mo agoI can put it all in, say, 24 bits, if my database is small. 140k games, 120 positions each. log(140000*120)/log(2) ~~ 24.001, and surely there will be some duplication. The encoding is just the index number of the game + move that resulted in that position.
- pklausler 9mo agoThe duplication is the problem if you want to use positions as DB keys.
- bombcar 9mo agoNow 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.
- NitpickLawyer 9mo agoNot what you asked for, sorry, but it reminded me of this gem - https://www.youtube.com/watch?v=C5JVFCouXIU https://www.youtube.com/watch?v=C5JVFCouXIU
- mlyle 9mo agoObviously not possible -- how would pawns pass each other without captures?
- bombcar 9mo agoAh! True, I worked out how you could have OTHER pieces get around a pawn, but pawns themselves can't get past each other.