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

181–190 of 204 posts

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

#181

Post by kurinikku »

ComplexSystems wrote: post #152

You can get this even lower, without the need for the extra promotion bits, if you make a note of a few things: 1. There is still redundancy in that there are multiple pieces of the same type, and if you permute their locations you get another representation of the same state. 2. You don't need to say that some pawn's location is the king if it's en passant. You can just use the back row, which pawns can't get to. Us…

OP here. Thanks for the suggestion! I really like the idea of there being redundancy for pieces of the same type. If I understand correctly, when a knight is in a particular square say it's not relevant whether it's the king-side or queen-side knight. I believe you still need to keep the ordering for the rooks due to castling, but for the knight and bishop you can store 1-bit each in the ordering. With this we end up with 7 bits for each side, thus below 26 bytes overall!

Let me ponder a bit more on the pawn locations. We do need the pawn ordering since the we've encoded the string representing the promotions in sorted order. In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably.

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

#182

Post by kurinikku »

bumbledraven wrote: post #131
tromp wrote: post #11

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.

Amazing work. This should be the top comment on this page.

+1

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

#183

Post by xpe »

skupig wrote: post #177
xpe wrote: post #166

Earlier quoted context omitted.

It is necessary to store the ability-to-castle state with each rook; attempting to keep it only attached to each king is insufficient.

That's not what I wrote, you duplicate the king ID in the position of each castle-able rook.

Seems like I’m not following your specific id mapping.

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

#184

Post by halfcat »

samwillis wrote: post #8

When I was building my multiplayer Sudoku app, I had fun experimenting with how small I could pack a sudoku grid into a URL. I came up with a scheme combining bit packing with the knowledge of how the grid works. So as you move through the grid, based on the knowledge of what's been placed where and the remaining digits you have a fewer options. Was fun, I was playing code golf with myself. Sadly seem to have lost th…

Thank you for the python-inline-source library. Are you still working on Tetra?

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

#185

Post by calvinmorrison »

WithinReason wrote: post #47
calvinmorrison wrote: post #9

Earlier quoted context omitted.

Storing the game would give you the position though

It took me a moment to see your point: it might take less information to store the entire game using a chess engine by entropy coding than a single position

Yeah i guess after a certain number of moves it wouldn't but for the first half it would.

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

#186

Post by antsou »

timerol wrote: post #40

I played with this in the past ( https://news.ycombinator.com/item?id=34461113#34462521 ), but am willing to take another stab at it. Store one 64 bit bitboard - a set bit means that a piece is present at that place. An unset bit means that no piece is after that position. After the bitboard, store a list of 32 4 bit integers, where the order of the pieces in the list corresponds to the order of the bits set. If ther…

I believe you can also do it in a slightly different way. For each square on the board:

0 - encodes no piece in the square; at least 32 of them, so 32 bits (4 bytes)

1xxxx - xxxx being your encoding: encodes remaining pieces; at most 32 of them, so max 32 x 5 bits (20 bytes)

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

#187

Post by zeagle »

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.

It was in jest because blockchain is a solution looking for a problem, but as others have pointed out what you say isn't really the case. I'm glad it generated some discussion. Hashing previous steps for verification isn't blockchain.

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

#188

Post by notfed »

drivers99 wrote: post #39
jade-cat wrote: post #12

There are two more things that should be considered. Both of them unlikely to influence a position, but they can matter - just like the en passant target. The fifty move rule[0] is quite simple, just store a number, fits in five bits. But the threefold repetition rule[1] is quite a pickle - it basically means that to know everything about a position you need to know every position that occurred before it. [0] https:/…

They'd also need to store whose turn it is, so I'm guessing the article is strictly about "positions" and not game state.

I don't see how it can be considered a position without whose turn it is.

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

#189

Post by xg15 »

I wonder if you could shave off some more bits by considering the specific movement restrictions of some pieces:

Bishops can only ever occupy squares of their respective colour, so you'd only have to encode ~32 possible positions instead of 64.

Pawns (before promotion) can only move straight forward and diagonally forward, which makes their range of valid positions a sort of upside-down triangle shape, with the "tip" of the triangle at the respective pawn's starting position. (e.g. it's impossible to move the pawn from A2 to H2 - or even to H8 - without a promotion)

Haven't made the exact calculations, but it might be possible to encode both positions with 5 bits each instead of 6 bits.

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

#190

Post by r3trohack3r »

rcxdude wrote: post #178
r3trohack3r wrote: post #170

Earlier quoted context omitted.

IIUC a blockchain is a structure where each node has a content addressable hash that includes the hash of the previous node in the chain. If you change any historical node, every subsequent hash is updated. This structure is used inside your .git directory, your docker manifest, etc. Blockchains are incredibly useful structures.

That's a Merkle tree. Blockchains are a Merkle tree plus some form of consensus algorithm, often a trustless one. It's the usefulness of the consensus algorithm which is usually called into question by critics (generally because it's often expensive and cannot reference anything outside the system).

IIUC a merkle tree is a data structure where the leaf nodes are the hashes of data. The inner nodes of the tree are hashes of the child hashes up to a root hash.

Merkle trees are helpful for quickly validating the integrity of a chunked file. Both IPFS and BitTorrent use merkle trees to validate files.

I do not understand how git could represent its history using a merkle tree.

Post reply on HN