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

191–200 of 204 posts

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

#191

Post by jepler »

jepler wrote: post #104

Ignoring whose turn, castling & en passant, a static huffman table isn't terrible: 0 - empty (1*32=32) 10y - pawn (color) (3*16=48) 11xxxy - piece (color) (6*16=96) The initial board takes 176 bits (22 bytes) to describe. In most games, the definition length would decrease. A game position is self-delimiting as it always has exactly 64 entries (no need to store the variable length) one of the extra 3 non-pawn piece v…

static arithmetic encoding appears to store the initial board, "black to move" and 4 rook "can castle" flags and a 1-of-9 "can en passant" value in 22 bytes. "4 pawns taken + 12 pawns promoted to queens", which I still think is the "complex-est" configuration that might actually be reachable in a valid game, fits in 25 bytes. A board with just 2 kings left on it encodes in 10 bytes (en passant and can castle flags are not needed).

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

#192

Post by teo_zero »

xpe wrote: post #183
skupig wrote: post #177

Earlier quoted context omitted.

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.

I rhink the concept is: in the initial position you have three kings: in a1, e1 and h1. Once the left rook is moved, it will be encoded as rook and not as a king anymore. Same for the right one. If you move the king, both rooks will be encoded as rooks and not as king anymore.

Decoding is easy: if there's more than one king, one must be in e1: that's the real one, the others are actually rooks.

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

#193

Post by teo_zero »

LorenPechtel wrote: post #141
Scarblac wrote: post #71

Earlier quoted context omitted.

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

Yeah, I was trying to send a chess puzzle to someone on Gameknot.com. White to mate in 1--except there was no black king. (The objective was to mate anyway--find the move that would mate the black king no matter where it was.) Their encoder created the king.

Do you perhaps mean that there was no white king?

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

#194

Post by teo_zero »

kurinikku wrote: post #181
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…

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

If a white pawn in x4 (for x between a and h) can be captured en passant, you encode its position as x1. When decoding, if you see a white pawn in rank 1, you know it can't be there, so you place it in x4 and flags it e.p. Black pawns are analogous.

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

#195

Post by teo_zero »

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…

The problem is that the encoding of a position by the previous moves is not unique. For example, 1.a2-a3,a7-a6; 2.h2-h3 represents the same position as 1.h2-h3,a7-a6; 2.a2-a3... Chess engines need to remember evaluated positions to avoid reevaluating them, and this scheme doesn't work well for that purpose.

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

#196

Post by LorenPechtel »

teo_zero wrote: post #193
LorenPechtel wrote: post #141

Earlier quoted context omitted.

Yeah, I was trying to send a chess puzzle to someone on Gameknot.com. White to mate in 1--except there was no black king. (The objective was to mate anyway--find the move that would mate the black king no matter where it was.) Their encoder created the king.

Do you perhaps mean that there was no white king?

No black king--in other words, you don't know where the black king is since it must exist. The puzzle was to find the move that would mate the king no matter what square it was in.

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

#197

Post by LorenPechtel »

Dylan16807 wrote: post #144
LorenPechtel wrote: post #138

Earlier quoted context omitted.

You can have only one en passant situation on the board at once. This means you can use 3 bits to encode the column for en passant, you check the board to evaluate the legality of the solution and discard if it isn't legal (this means you don't have to use a bit to encode whether it's possible as the encoder is guaranteed to be able to pick a column that it's not possible.)

You can have two pawns in the same column in plausible en passant position after pawns cross over via capture. Of course after a capture you have more bits free, but you need to do something more complex than encoding the column.

I think we are both wrong. En passant only exists for one move, whatever has happened from captures is irrelevant. However, now I realize you can have two possible en passant captures at once--a pawn moves to 4th rank between two opposing pawns on the 4th rank.

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

#198

Post by nextaccountic »

r3trohack3r wrote: post #190
rcxdude wrote: post #178

Earlier quoted context omitted.

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.

git commits themselves are merkle trees (or more like, DAGs) that contain filesystem trees, a set of parent commits, and metadata

each parent commit in turn contains their own parents etc, until you reach an initial commit

the funny thing here is that parent commits don't have references to children, it's children that have references to parents (like the union find data structure) so the relationship here is inverted. that's because git objects are immutable

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

#199

Post by kurinikku »

teo_zero wrote: post #194
kurinikku wrote: post #181

Earlier quoted context omitted.

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…

> 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. If a white pawn in x4 (for x between a and h) can be captured en passant, you encode its position as x1. When decoding, if you see a white pawn in rank 1, you know it can't be there, so you place it in x4 and flags it e.p. Black pawns are analogous.

What I meant to say was "I haven't quite figured out how to use this to encode reliably and get an improvement vs simply using own king's position".

If we can guarantee that the pawn stays in its own file then I see a path for improvement (by having the actual position vs back row usage as a 1-bit toggle), but this is not broadly the case due to movement across files on pawn captures.

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

#200

Post by teo_zero »

kurinikku wrote: post #199
teo_zero wrote: post #194

Earlier quoted context omitted.

> 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. If a white pawn in x4 (for x between a and h) can be captured en passant, you encode its position as x1. When decoding, if you see a white pawn in rank 1, you know it can't be there, so you place it in x4 and flags it e.p. Black pawns are analogous.

What I meant to say was "I haven't quite figured out how to use this to encode reliably and get an improvement vs simply using own king's position". If we can guarantee that the pawn stays in its own file then I see a path for improvement (by having the actual position vs back row usage as a 1-bit toggle), but this is not broadly the case due to movement across files on pawn captures.

My method doesn't require any additional bits for the e.p. and is compatible with all the other techniques listed in TFA.

Using own king's position loses the info of the file. Iff you guarantee that the pawns are listed in order, this is not a problem. But later in TFA a permutation or sorting of pawns is suggested, which would then mess things up.

Please note that a slightly modified version of my method, where a pawn that can be captured e.p. is swapped (not merely moved) with whatever is in its corresponding back rank before any other encoding takes place, is compatible with all the other clever techniques suggested in the comments.

Post reply on HN