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

171–180 of 204 posts

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

#171

Post by Dylan16807 »

JoshuaDavid wrote: post #155
Dylan16807 wrote: post #124

Earlier quoted context omitted.

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…

> If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves". You are correct. So the board state from 75 moves previously plus 75 bytes to store the last 75 moves is sufficient to store a chess game state.

150 bytes because "moves" is defined in a very bad way here.

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

#172

Post by TylerE »

thaumasiotes wrote: post #164
TylerE wrote: post #50

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…

> Bishops, queens, and rooks would need a 4/5 bit field. Ignoring board boundaries, a queen has 56 possible moves requiring 6 bits. At any given position on the board, most of those aren't possible because the board is too small, but cramming that into 5 bits will make the encoding much more annoying. Same thing goes for rooks; ignoring board boundaries there are 28 possible moves, but including the board boundaries…

Hours forgetting pawns capturing en passant.

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

#173

Post by thaumasiotes »

TylerE wrote: post #172
thaumasiotes wrote: post #164

Earlier quoted context omitted.

> Bishops, queens, and rooks would need a 4/5 bit field. Ignoring board boundaries, a queen has 56 possible moves requiring 6 bits. At any given position on the board, most of those aren't possible because the board is too small, but cramming that into 5 bits will make the encoding much more annoying. Same thing goes for rooks; ignoring board boundaries there are 28 possible moves, but including the board boundaries…

Hours forgetting pawns capturing en passant.

What?

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

#174

Post by [deleted] »

r3trohack3r wrote: post #170
flangola7 wrote: post #161

Earlier quoted context omitted.

No, no they do not.

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.

[deleted]

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

#175

Post by JambalayaJim »

r3trohack3r wrote: post #170
flangola7 wrote: post #161

Earlier quoted context omitted.

No, no they do not.

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.

In context blockchain is referring to a distributed set of hash structures + a consensus algorithm

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

#176

Post by foota »

ThomasCM wrote: post #48
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).

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…

Heh, I guess there are board states that are not possible to reach through a valid sequence of moves, but I guess otherwise it's not possible that games are more compressable by definition, since any valid board state could be represented as a sequence of moves.

This does raise the question of the efficiency of reverse engineering a series of minimal moves for some board state.

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

#177

Post by skupig »

xpe wrote: post #166
skupig wrote: post #95

Earlier quoted context omitted.

You can use duplicate king identifiers to represent castling available, and replace the extra rook identifiers with "black king (my turn)" and "white king (my turn)" to store the turn in the same amount of space. edit: You can then use the inverted/flipped board trick to store one bit of your piece list, down to 191 bits. edit2: You only need one "king (my turn)" ID, which represents the whichever color you didn't us…

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.

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

#178

Post by rcxdude »

r3trohack3r wrote: post #170
flangola7 wrote: post #161

Earlier quoted context omitted.

No, no they do not.

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).

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

#179

Post by inimino »

Tommah wrote: post #133

For my chess tactics trainer at https://www.checkmatechamp.net/ , I tried a lot of different techniques to compress a small set of positions (about 800). I was not concerned with storing the positions in a fixed size, so I was mainly trying things that would make the entropy of each compressed position smaller. I eventually fit these into a file that is about 14 KB in size when gzipped. Each position takes about 17.5…

If the colors are symmetrical, then it's just "my pieces" and "opponent's pieces". You could encode who has the move by how the board is ordered, and predict it from the king and queen position, then just encode the differences.

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

#180

Post by jiggawatts »

jiggawatts wrote: post #148

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 encodin…

Replying 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_an...

Post reply on HN