131–140 of 204 posts
How to store a legal chess position in log_2(8726713169886222032347729969256422370854716254) ~ 152.6 bits ~ 19.1 bytes using rankings: https://github.com/tromp/ChessPositionRanking But the major point of this project is to allow for random sampling of positions with a decent likelihood of getting a legal one, which allows for accurate estimation of the number of legal positions.
Earlier quoted context omitted.
I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. I like the "no kings" idea for castleable kings - though I think with smaller pawn sizes, that gives another opportunity for compression: - king that can't castle: king - king that can castle queenside: any other piece in king's position, no king of that color on board - king that can castle kingside: black pawn o…
> I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. You could do it that way, but the particular comment was suggesting two entirely separate ways to save bits, one for pawns and one for rooks. Specifically, the suggestion in that post is to use 1st/8th rank to show en passant, and to show castling by replacing an unmoved king with a different piece. But there's…
I only considered techniques that would not cause the decoder to become overly complicated. One "non-standard" technique that I used was inverting the color of all the pieces on one side of the board. Specifically, on the lower half of the board, I change all the white pieces to black and vice versa. This greatly lowers the average entropy of a typical position, since for most of the game, each player keeps most of his pieces on his side of the board. It is also easy to handle in the decoder in one line (if row I have meaning to write a blog post about it, but I haven't gotten around to it yet. If you are interested in hearing more, let me know, and I will move it up my to-do list.
Earlier quoted context omitted.
It's not really about whether it's legal, but whether it looks normal . Very bizarre positions can easily be legal, but they're hard to remember for everyone.
I’ve heard this corroborated by exhibition players who play ten or fifteen opponents at once. They do better with moderately skilled opponents than random people.
Earlier quoted context omitted.
> I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. You could do it that way, but the particular comment was suggesting two entirely separate ways to save bits, one for pawns and one for rooks. Specifically, the suggestion in that post is to use 1st/8th rank to show en passant, and to show castling by replacing an unmoved king with a different piece. But there's…
I'm actually realizing - you can simply have a case where if a white/black pawn is on the 4th/5th rank, have the next bit be a flag for en passant. This makes all en passant rules stored in 8 bits at max. Since only 1 pawn can be in a status of "en passantable" at a time, we can make it stop assigning a flag bit for future pawns if the answer is ever "yes".
If you're going to explicitly store it, at least squeeze down to 4 bits to pick a specific pawn (and picking one visibly not at risk if no pawn is at risk).
But using clever piece rearrangements is a lot better than spending flag bits.
Earlier quoted context omitted.
Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more. Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAA…
Are you saying that, to encode a valid position, ignoring the cost to encode both the starting position and the move definitions, you can encode the move sequence using less information than encoding a single position?
Earlier quoted context omitted.
Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more. Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAA…
That is a beautifully designed website. I don't think I've ever used an OAuth authentication flow as smooth as the one that your site uses to access my Lichess credentials (same as my HN name, btw, in case you want to beat me at a correspondence game). ChessMonitor is practically a work of art!
I guess OAuth is relatively fast as I don't have a middleman (like Auth0) in there. It's just Passport.js.
Earlier quoted context omitted.
> I see - so you can use the bits you saved by not having separate rook pieces to denote En Passant pawns. You could do it that way, but the particular comment was suggesting two entirely separate ways to save bits, one for pawns and one for rooks. Specifically, the suggestion in that post is to use 1st/8th rank to show en passant, and to show castling by replacing an unmoved king with a different piece. But there's…
I'm actually realizing - you can simply have a case where if a white/black pawn is on the 4th/5th rank, have the next bit be a flag for en passant. This makes all en passant rules stored in 8 bits at max. Since only 1 pawn can be in a status of "en passantable" at a time, we can make it stop assigning a flag bit for future pawns if the answer is ever "yes".
Earlier quoted context omitted.
Nice! Though there are max 32 pieces on a board, not 16; so this scheme is 64 + 32 * 4 = 192 bits, or 24 bytes. The bit to indicate whose turn it is isn't accounted for here. But it probably could probably represented by the binary negation of the bitboard -- if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to d…
> if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied. This doesn't quite work because if there are exactly 32 bits set, inverting it leaves 32 bits set. You could fix this by marking all pawns belonging to the player who's turn it is as capturable via en-passant (if a play…
Earlier quoted context omitted.
I suspect it would be hard to beat pgn run through a good compression algorithmn. Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets. So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8…
> I suspect it would be hard to beat pgn run through a good compression algorithmn. I once[0] tried to spread this message :) [0] https://stackoverflow.com/a/1831841/61938
I suspect the winner would be something like an LZMA derivative with a fixed dictionary. I doubt not using an adaptive encoder would be a big loss as PGN (exlcuding the metadata) is quite far from random bytes.