Compressing Chess Moves Even Further, To 3.7 Bits Per Move

The size of e4:e5 ...
Save an empty file using notepad and name it bytesize.txt
Look in properties for file size: 0 bytes
Put a move like "e4:e5" in that file and save.
Zip it up (bytesize.zip) : 127 bytes
Look at properties of both files text and zip and compare file sizes.
Text file with e4:e5 is 5 bytes.
Put a FEN code: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 2
Zipped file becomes: 176 bytes for a complete 2 ply move.
And the text file becomes 60 bytes.

I opened a file using hexed.it/
Then I played with the settings and Binary 8-Bits per row. I spaced it out for ease of view. This is the FEN code converted into binary.
0000 0000
0000 1000
0001 0000
0001 1000
0010 0000
0010 1000
0011 0000
0011 1000
This is what I got when I went to the tab in that hexed.it site and selected: Tools> Histogram> Entropy Analysis > Shannon Entropy: 2.8780 bits
(35.97% of maximum)

If I press new file and type a move like : e4e5 and than look in the Histogram, I get 1.5 bits.

www.perplexity.ai/search/What-is-Entropy-HldmE88cRxOGNCHfy5WTKQ

To @JosephChessKing6, in reply to #10.

Let’s consider a simple deterministic game where there are exactly eleven legal moves available in any position—suppose each move is pressing any of eleven buttons. Encoding such games is straightforward: just enumerate the buttons, and use the number of the button pressed as the move’s encoded value. This way any move would cost four bits—which provide sixteen permutations; eleven are used and five others are wasted.

It can be done better if we encode the moves by two at a time. Two moves is 121 possibility to distinguish between, so seven bits would be enough to encode any such move pair. Thus it’s 7 bits per two moves, or 3.5 bits per move—versus previous four. Though if the game has an odd number of moves, one of them would not be possible to pair, and it would take ordinary whole number of bits—four, that is.

It can be compressed further and further. If we group moves by 13 at a time, then it would be eleven-in-thirteenth-power permutations per block, which are covered by 45 bits. That would be 45 bits per 13 moves, or slightly less than 3.462 bits per move, which is even more dense. Though this method cannot do better than binary-logarithm-of-eleven bits per move. But next round of cleverness can break this border.

That is how there can be a fractional number of bits per move. I think that in the article it’s some essentially the same mechanism.

I’m ready to elaborate further if you have subsequent questions or if you didn’t understand any of my explanations.

@Hott said in #12:
> To @JosephChessKing6, in reply to #10.
>
> Let’s consider a simple deterministic game where there are exactly eleven legal moves available in any position—suppose each move is pressing any of eleven buttons. Encoding such games is straightforward: just enumerate the buttons, and use the number of the button pressed as the move’s encoded value. This way any move would cost four bits—which provide sixteen permutations; eleven are used and five others are wasted.
>
> It can be done better if we encode the moves by two at a time. Two moves is 121 possibility to distinguish between, so seven bits would be enough to encode any such move pair. Thus it’s 7 bits per two moves, or 3.5 bits per move—versus previous four. Though if the game has an odd number of moves, one of them would not be possible to pair, and it would take ordinary whole number of bits—four, that is.
>
> It can be compressed further and further. If we group moves by 13 at a time, then it would be eleven-in-thirteenth-power permutations per block, which are covered by 45 bits. That would be 45 bits per 13 moves, or slightly less than 3.462 bits per move, which is even more dense. Though this method cannot do better than binary-logarithm-of-eleven bits per move. But next round of cleverness can break this border.
>
> That is how there can be a fractional number of bits per move. I think that in the article it’s some essentially the same mechanism.
>
> I’m ready to elaborate further if you have subsequent questions or if you didn’t understand any of my explanations.

Ah, thanks! You made it very clear! Now I understand! :) :)

@Ferdosco said in #2:
> Compress your brain into a black hole!

Impossible! this dudes brain is too big to be able to be compressed into a black hole

@kamekura said in #9:
> compression is actually to evaluate the position, use an engine
> like Stockfish, and then store the index of the move.
>
> Computational cost apart, how would that work in practice given that the typical engine output is non-deterministic?

Actually they should be deterministic if using only one thread, correct me if I'm wrong

@mudblooded said in #17:
> Actually they should be deterministic if using only one thread.

I believe I have heard something that implied that calculations with floating-point numbers are also non-deterministic. Or maybe they are consistent between runs on the same machine, but not consistent between different machines (which can also be a problem). I think it was something from the history of TeX: its creator had rewritten it to use only integer arithmetics to ensure perfectly identical behaviour on any system.

Interesting read. I also love the fact, that you did it in Rust :)