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 (2022)

ezzeriesa.notion.site

Post reply on HN
Print view View original

101–108 of 108 posts

Re: How to store a chess position in 26 bytes (2022)

#101

Post by jonsoft »

tromp wrote: post #97
jonsoft wrote: post #95

Earlier quoted context omitted.

Each pawn that wants to be promoted either takes: (a) another 'special' piece (knight/rook/bishop/queen), in which case it has already bought enough bit budget to later be promoted; or (b) another pawn, in which case this temporarily saves 1 bit (as the other pawn becomes a space), but then later we need 2 extra bits for the promotion, so we pay 1 bit extra per pawn in total In the case of (b) there are now fewer paw…

Among 4 pawns like white and black a&b pawns, you only need 1 pawn capture to allow the other 3 pawns to promote.

Great point.

So for each 4 pawn cluster, 1 pawn takes another pawn, and the net result is +1 bit once the captor promotes. The remaining 2 pawns in the cluster each need 2 extra bits when promoted => 2 x 2 = 4 bits. So 5 bits per 4-pawn cluster, of which there are 4.

So maximum representation would be 162 + (5 * 4) = 182 bits?

Re: How to store a chess position in 26 bytes (2022)

#102

Post by datsci_est_2015 »

arnsholt wrote: post #34

Lichess uses a scheme which is probably more efficient on average, described on revoof's blog[0]. Basically, it's a variable length scheme where the first 64 bits encode square occupancies, followed by piece codes (including castling, side to move, and ep with some trickery), followed by half-move clocks if necessary. 0: https://lichess.org/@/revoof/blog/adapting-nnue-pytorchs-bin...

It’s mathematically dissatisfying, but often the most optimal storage (or algorithm) solutions involve clever heuristics that are dynamically applied.

Some systems just have to be observed in order for solutions to be optimally designed around how they actually behave, rather than how they theoretically behave.

Re: How to store a chess position in 26 bytes (2022)

#103

Post by kazinator »

kazinator wrote: post #77

I would do it like this. There are 32 pieces, any of which may be missing. So let's use four bytes (32 bits) as a mask of what pieces are present. Then, coordinates can be given for each piece that is present. The board is 8x8, so coordinates can be encoded as pairs of 3 bits, e.g. A3 is 000:011. The worst case is that we need 32 of these pairs, which requires 24 bytes. That brings us to a worst case of 28. How can w…

Right we need some additional state for ampassan and whether counseling is available and such, not just the raw position.

However, am I mistaken? The article appears to be neglecting to record one bit of information: whose turn is it for this board position, black or white? If you're going to care about whether castling is available and other such game state, that is not complete without knowing whose turn it is for that position.

Re: How to store a chess position in 26 bytes (2022)

#104

Post by [deleted] »

jonsoft wrote: post #101
tromp wrote: post #97

Earlier quoted context omitted.

Among 4 pawns like white and black a&b pawns, you only need 1 pawn capture to allow the other 3 pawns to promote.

Great point. So for each 4 pawn cluster, 1 pawn takes another pawn, and the net result is +1 bit once the captor promotes. The remaining 2 pawns in the cluster each need 2 extra bits when promoted => 2 x 2 = 4 bits. So 5 bits per 4-pawn cluster, of which there are 4. So maximum representation would be 162 + (5 * 4) = 182 bits?

[deleted]

Re: How to store a chess position in 26 bytes (2022)

#105

Post by jonsoft »

gus_massa wrote: post #100
tromp wrote: post #97

Earlier quoted context omitted.

Among 4 pawns like white and black a&b pawns, you only need 1 pawn capture to allow the other 3 pawns to promote.

Yep, that increase the total in 3*3-4=5 bits, and you can repeat it 4 times, so the maximum is at least 162+4*5=182. I'm trying to prove that is the worst case, but there are just too many cases. I guess I'll try to use a program o brute force it or just forget about it.

Actually, given this, we believe that 4 pawns must have been captured to reach 182 bits. So at least 4 pieces no longer need colors. If we store the color mask at the end, I think we can make it variable length, and truncate when no further pieces need colors assigned.

So then we need maximum 182 - 4 = 178 bits

EDIT: Equivalently, we could suffix each non-empty piece in the sequence with an associated color bit

Re: How to store a chess position in 26 bytes (2022)

#106

Post by kazinator »

kazinator wrote: post #103
kazinator wrote: post #77

I would do it like this. There are 32 pieces, any of which may be missing. So let's use four bytes (32 bits) as a mask of what pieces are present. Then, coordinates can be given for each piece that is present. The board is 8x8, so coordinates can be encoded as pairs of 3 bits, e.g. A3 is 000:011. The worst case is that we need 32 of these pairs, which requires 24 bytes. That brings us to a worst case of 28. How can w…

Right we need some additional state for ampassan and whether counseling is available and such, not just the raw position. However, am I mistaken? The article appears to be neglecting to record one bit of information: whose turn is it for this board position, black or white? If you're going to care about whether castling is available and other such game state, that is not complete without knowing whose turn it is for…

* en passant

Re: How to store a chess position in 26 bytes (2022)

#108

Post by fallingfrog »

wedog6 wrote: post #85
Dylan16807 wrote: post #70

Earlier quoted context omitted.

You have a good starting point, but using 6+1 bits is a bad way to encode 65 possibilities. If you use base 65, you'll see that 65^32 possibilities only require one more bit to store than 64^32. And four promotion possibilities wouldn't be 4 bits, it would be 2. But even better is 5^16 squeezing into 38 bits. Combining those cuts your strategy down to 192.7+37.2+4+6 bits which is 30 bytes. The main savings the articl…

Heuristic: (65/64)^64 is extremely close to e. This comes from a classic formula for e as the limit of (1+1/n)^n. Therefore (65/64)^32 is roughly sqrt(e). Since 1 < e < 4, 1 < sqrt(e) < 2. So 65^32 < 2 * 64^32.

Thats a lovely observation! Very clever.
Post reply on HN