Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to store a chess position in 26 bytes using bit-level magic (2022)

ezzeriesa.com

Post reply on HN
Print view View original

121–130 of 204 posts

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#121

Post by kpozin »

hinkley wrote: post #111
seanhunter wrote: post #100

Earlier quoted context omitted.

As the article discusses, there's a bit more than that to store in a position. Specifically you have to store whether or not castling is available for the two sides and also whether any pawns are en passant targets, since both of those moves are available (or not) conditionally in a given position based on previous moves in the game.

I don’t think that’s true. Or rather, it’s only true for storing board position not for storing the move history. If you have the entire move history you know that status of each piece.

If you have the entire move history, then you probably don't need to store partial board positions.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#122

Post by [deleted] »

timerol wrote: post #112
penteract wrote: post #97

Earlier quoted context omitted.

To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns. It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pa…

A Huffman code like this can also represent knights (or any single other piece) in 3 bits. 000 - black pawn 001 - black knight 0100 - black bishop 0101 - black rook 0110 - black king 0111 - black queen 100 - white pawn 101 - white knight 1100 - white bishop 1101 - white rook 1110 - white king 1111 - white queen Going with "a pawn in the first row is actually en-passantable, and should be swapped with the piece in the…

[deleted]

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#123

Post by alexb_ »

Dylan16807 wrote: post #120
alexb_ wrote: post #117

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…

For what piece to replace the unmoved king with, you can actually use both white AND black pieces, since the starting rank can decode what color the king is:

- White Knight on E1 and no king: Replace with white king that can castle both ways, E4 pawn can be taken En Passant

- White Bishop on E1 and no king: Replace with white king that can castle kingside, E4 pawn can be taken En Passant

- White Rook on E1 and no king: Replace with white king that can castle queenside, E4 pawn can be taken En Passant

- Black Knight on E1 and no king: Replace with white king that can castle both ways, E4 pawn cannot be taken En Passant

- Black Bishop on E1 and no king: Replace with white king that can castle kingside, E4 pawn cannot be taken En Passant

- Black Rook on E1 and no king: Replace with white king that can castle queenside, E4 pawn cannot be taken En Passant

It's the same for E8, just put a black king and not a white king. Sorry if this is repetitive, I could have probably just explained it and let you figure it out, but I put the cases down here for clarity. This should also be combined with the Knight huffman encoding that was talked about here https://news.ycombinator.com/item?id=37527350

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#124

Post by Dylan16807 »

JoshuaDavid wrote: post #78

Minor point: the FIDE rules[1] state > Article 9: The Drawn Game > ... > 9.2 The game is drawn, upon a correct claim by a player having the move, when the same position for at least the third time (not necessarily by a repetition of moves) [happens and a draw is claimed] > 9.3 The game is drawn, upon a correct claim by a player having the move, if: ... 9.3.2 the last 50 moves by each player have been completed withou…

If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves".

> they can only move forward, except in the case of en-passant

En passant still attacks forward, into the space the enemy pawn just moved through.

> 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward

But pawns can't move through pawns. ~~At most I think you can have 4 of the pawns march all the way forward and get captured, leaving you with with 4 pawns that can move 6 spaces and 8 pawns that can move 7 spaces, for a total of 80 pawn moves without a capture.~~

Okay, if you sacrifice a bunch of other pieces to pawns, then you can get them to pair up without losing any. So that's 8 pawns moving 6 spaces, and 8 pawns moving 7 spaces. 104 pawn moves in a row without a capture.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#125

Post by thriftwy »

VyseofArcadia wrote: post #56
solardev wrote: post #5

Meanwhile the non-comp-sci dev in me is like, "why not just store every position in a simple JSON so everyone can read it and everything can parse it". Yeah, it might be half a kB, but you don't have to run through mental gymnastics just to render the pieces...

I feel like we have an interesting tragedy of the commons situation of software engineering. On the one hand, storing positions on JSON is quick to implement, easy to understand, easy to read, easy to hack on, and junior engineers and the people who have to deal with your code later will be able to pick it up and run with it easily. On the other hand, when just about everyone is making this same ease-of-use/performan…

You can compress that JSON with a pre-trained dictionary and get a massive discount.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#126

Post by tylerhou »

pfooti wrote: post #15

An interesting cognitive phenomenon: if you ask chess experts and novices to memorize and recall an arbitrary chessboard, the experts are significantly better than the novices _only if_ the board is a legal board that can be arrived at during play. If it is not a legal board, there's no particular difference between novices and experts. Original ref: Chase & Simon 1973, Perception in Chess. This is usually taken to m…

This isn't just for chess -- it's practically any knowledge task that you can build expertise in.

E.g. take programming. Suppose I sat down an experienced programmer and a novice and gave them the same small (~10-20 line) function to reproduce from memory. If the function is a "reasonably written function" I'm willing to bet that the experienced programmer could reproduce the function with just one or two "peeks" -- once you have enough experience, you can better recognize patterns / chunk your knowledge. A novice doesn't have this ability, so it would likely take them many more peeks.

On the other hand, if the function is some random gibberish with little structure, you could imagine that it's probably equally difficult for both the experienced programmer and the novice to reproduce the function from memory.

For chess, one reason why masters can better recall positions is because they know what typical positions look like (e.g. a position typical of the "London" opening). Then, they only need to store a "diff" of the given position and a typical position. ("It's a typical London setup for White, except White also played a3 and b4.") A novice doesn't have this knowledge, so they have to store the whole position.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#127

Post by robertlagrant »

seabass-labrax wrote: post #105
ThomasCM wrote: post #48

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 created an account just to see that flow, and it did not disappoint! How's it this fast?

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#128

Post by episteme »

r3trohack3r wrote: post #49
zeagle wrote: post #30

Earlier quoted context omitted.

Finally, a good use case for blockchain technology!

I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.

Nearly every company, what is your source for that? I've never even heard of this before.

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#129

Post by robertlagrant »

TylerE wrote: post #50
Scarblac wrote: post #10

Storing a chess position in 26 bytes. Storing a game is also interesting. The number of legal moves varies depending on the position. You could try to define a variable length encoding by giving more likely moves a shorter encoding, but the ordering would need to be deterministic so it could be decoded (running Stockfish for a second isn't).

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

Re: How to store a chess position in 26 bytes using bit-level magic (2022)

#130

Post by bjourne »

Scarblac wrote: post #71
jade-cat wrote: post #58

Earlier quoted context omitted.

Fair enough. Still up to 50 board states that can influence the current one (the 50 move rule is coming to help here) FEN doesn't store previous states, but EPD can. It just goes to show how meanings and requirements change depending on context, which is super interesting in and of itself :P

Also, database software gets so clever with storing games that they often can't save games that have illegal moves in them. But there are plenty real games from real tournaments that had illegal moves in them that nobody noticed...

That's a very good point. Similar issues affect file systems that has to store files with invalid filenames and parsers that have to gracefully handle invalid parse trees.
Post reply on HN