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

51–60 of 204 posts

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

#51

Post by esrauch »

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

That suggestion seems very reminiscent of the notion that optimally compressing wikipedia is the same problem as what generative LLMs are doing, by virtue of predicting the next letter/word/segment with high precision lets you compress it extremely well.

I think for chess you could get most of the benefit with a relatively naive engine; chessbase has a weak engine built in where you can hit space bar and it does a move which is incredibly useful since there's just one obvious move for a lot of positions anyway; if the move was especially tricky/nonobvious than it's also not what you would want when hitting spacebar to just predictably proceed anyway).

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

#52

Post by DesiLurker »

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.

I consider any reduction past the cache-line size (32B) to have diminishing returns as far as processing is concerned. unless of course if you can fit 2 of these in one.

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

#53

Post by elteto »

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…

Maybe a silly question, how do you know which side of the board is white vs black?

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

#54

Post by somenameforme »

solardev wrote: post #23
awegio wrote: post #17

Earlier quoted context omitted.

You need a compact encoding for chess engines that explore billions of states as fast as possible to plan the best move.

Well, this is arguably a kind of compression, right? So you'd be trading CPU time for fewer bytes? Is that a desirable tradeoff at chess engine scales?

It's not compression in the normal sense of the word. Most parsing is directly to data. So e.g. you know the square of some piece is the next 5 bits. In languages that allow it you can cast directly from the next bit offset to an e.g. byte. This is going to dramatically faster than parsing much more loosely structured JSON. As database sizes increase you also get worse performance there, so it's a double hit. So with these sort of representations you get orders of magnitude faster and smaller. Sometimes there really is a free lunch!

Also I'd add the sizes involved here are kind of insane. I wrote a database system that was using a substantially better compression that averaged out to ~19 bytes per position IIRC. And I was still getting on the order of 15 gigabytes of data per million games. Ideally you want to support at least 10 million games for a modern chess database, and 150 gigabytes is already getting kind of insane - especially considering you probably want it on an SSD. But if that was JSON, you'd be looking at terrabytes of data, which is just completely unacceptable.

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

#55

Post by Timon3 »

catapart wrote: post #32
Timon3 wrote: post #19

Earlier quoted context omitted.

This is illustrated very well in Sebastian Lague's video "Coding Adventure: Making a Better Chess Bot" ( https://www.youtube.com/watch?v=_vqlIPDR2TU ).

Awesome video and, I'll admit, the timing makes me curious to know if that video maybe inspired some devs to either pick up this kind of encoding work, or maybe just to finish up some encoding work that they had already started. Most likely unrelated, I know! Just a wondering in passing.

It's definitely possible! Even more so considering Sebastian also started a Coding Challenge for Tiny Chess Bots: https://www.youtube.com/watch?v=iScy18pVR58

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

#56

Post by VyseofArcadia »

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/performance tradeoff, software bloat happens. Our computers are so much faster and beefier, but we never actually seem to be able to enjoy the benefits of that, in part because software engineers keep optimizing for quick and easy.

Maybe we shouldn't dogmatically reach for the easy no-nonsense solution every time, and instead consider whether maybe a little nonsense might, over time, save people a lot of time.

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

#57

Post by croes »

cylon13 wrote: post #28
solardev wrote: post #23

Earlier quoted context omitted.

Well, this is arguably a kind of compression, right? So you'd be trading CPU time for fewer bytes? Is that a desirable tradeoff at chess engine scales?

Is your assertion that it takes more time for a CPU to read values out of a 30 byte struct and do a couple shifts and branches than to parse a JSON representation?

It's not just reading, you need to process the data to get castling availability, en passant target etc.

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

#58

Post by jade-cat »

Scarblac wrote: post #24
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:/…

Not all previous positions, only the ones with the same pieces, pawn positions, castling rights and en passant rights. But the standard, FEN, doesn't store that either. It's used more in the context of a full game than with individual positions.

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

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

#59

Post by bewaretheirs »

Bishops move on the diagonal and so can only stay on squares of their original color; you could thus encode the positions of the 4 bishops with 5 bits each instead of 6 each, saving a total of 4 bits, but this would preclude the use of the "store our/their king's location" hack to encode things. But you can encode bishop positions as a 4-digit base-33 number (digits 0..31 indicate the square, digit 32 is captured), which can be stored in binary as a 21-bit number. Net savings ~3 bits.

The "no two pieces on the same square" constraint could similarly be used more aggressively.

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

#60

Post by ToValueFunfetti »

HALtheWise wrote: post #31

For what it's worth, this definitely isn't the theoretical limit for compressing a chess board position, which I would probably resort to calculating mathematically. In particular, (simplifying to boards with no pieces captured) this scheme uses 24 bytes for representing piece positions, but the constraint that no two pieces are in the same square means you should actually need only log2(64!/32!) = 22.3 bytes for tha…

The upper bound on the number of legal chess positions given in https://en.wikipedia.org/wiki/Shannon_number is 8.7 * 10^45, which gives a lower bound of ln(8.7 * 10^45) = ~106 bits or 14 bytes.
Post reply on HN