News for hackers. Stuff that matters.
Re:Compressing Chess Moves for Fun and Profit by andoando on Friday March 15, 2024 @02:01PM (#39718752)
Im confused, how does probability help here when you need to encode the possibility of all legal moves?
Re:Compressing Chess Moves for Fun and Profit by jprete on Friday March 15, 2024 @02:11PM (#39718874)
Using the probability distribution of moves at any given position, so that more likely moves take less space, will result in saving space on average.

This is the same as Huffman coding, just applied to a different domain.

For that matter, it might also resemble LLM compression of input text, although LLM compression is intentionally lossy and the above schemes are not.

Re:Compressing Chess Moves for Fun and Profit by perihelions on Friday March 15, 2024 @02:07PM (#39718820)
You use variable-length encodings—shorter encodings for more likely moves, longer encodings for ones that happen infrequently.

This is the thing the parent comment was referring to,

https://en.wikipedia.org/wiki/Huffman_coding

Re:Compressing Chess Moves for Fun and Profit by neon5077 on Friday March 15, 2024 @02:27PM (#39719068)
Look up Huffman codes on Wikipedia.

In short, you put the most likely or most common values at the front of the dictionary. Values 0-255 take up one byte, 256-65535 take two bytes, etc. The lower your index, the fewer bits are needed to represent the corresponding state.

Re:Compressing Chess Moves for Fun and Profit by vitus on Friday March 15, 2024 @02:57PM (#39719386)
You're missing an important detail of Huffman codes: they need to be prefix-free so you can actually tell when one value ends and another begins.

A simplified example: suppose you have four letters in your alphabet that you want to represent in binary. You can't just represent these as A=0, B=1, C=10, and D=01, since it's impossible to tell whether "01011" is meant to represent ABABB or DDA or ACBB.

(Hamming codes on the other hand are intended for error correction, where you want maximally distant code words to minimize the chance that bitflips cause decoding errors.)

Re:Compressing Chess Moves for Fun and Profit by neon5077 on Friday March 15, 2024 @04:06PM (#39720123)
I don't really think that's too relevant to the core concept of using fewer bits for the most common codes.

That's really a problem inherent to binary streams in general, not just Huffman encoding.

Re:Compressing Chess Moves for Fun and Profit by vitus on Friday March 15, 2024 @05:21PM (#39720850)
It was a minor point re: this claim:

> Values 0-255 take up one byte, 256-65535 take two bytes

If you wanted to encode more than 256 values, then at best you'd be able to specify values 0-254 taking one byte, e.g. if you used 0xff as a special prefix to represent "use another byte for all other values", but that particular encoding means that you'd only be able to encode another 256 values with a second byte.

Re:Compressing Chess Moves for Fun and Profit by angry_albatross on Friday March 15, 2024 @02:39PM (#39719191)
I think you mean Huffman codes, not Hamming codes.
Re:Compressing Chess Moves for Fun and Profit by neon5077 on Friday March 15, 2024 @04:00PM (#39720045)
Yup.