4 ms·
> Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits). But each position can only
by jstanley 10mo ago
> Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits).
But each position can only be used once, so you really only have 64*63*62*61*...*33 possibilities = 64!/32! = ~2^53, so you could encode this with less than 7 bytes, and then use the basic 12-byte encoding for captures, castling, en-passant, and promotions, and you are below 19 bytes in total. (Did I miscalculate this?)
Also pawns can never be on the 1st or 8th rank so you can subtract those possibilities from each of the numbers that represents a pawn.
You also don't care about the order of bishops, rooks, knights, and especially pawns - so you should be able to do even better.
- tromp 10mo agoMultiplying 32 numbers each over 5 bits long obviously results in more than 160 bits. 64!/32! > 2^178.3
- jstanley 10mo agoOops! Thanks, the issue was with DuckDuckGo's calculator which I mistakenly trusted: https://duckduckgo.com/?q=log(64!%2F32!%2C+2)&t=ffab&ia=calculator https://duckduckgo.com/?q=log(64!%2F32!%2C+2)&t=ffab&ia=calc... It misinterprets "log(64!/32!, 2)" as "log(((64!) / (32!)) .2, 10)" which seems absurd, why would you use the comma as both an argument separator and a decimal place?? (Why was I using DuckDuckGo as a calculator? I do in fact keep a Casio scientific calculator on my desk, but I recently bought a new one (a Casio fx-991cw) so that I wouldn't have to keep moving the first one between home and work, but the new one doesn't have an obvious factorial function and I gave up looking - it is much worse than my fx-991es in many other ways as well despite looking superficially newer and better, so I can not recommend the fx-991cw).
- deleted 10mo ago[deleted]
- bonzini 10mo ago(Former) pawns can be on the 1st or 8th rank if they've been promoted. You can place an unpromoted pawn on the 1st or 8th rank to encode en passant, too. Also castling can be encoded as extra squares available to the rooks only ("queen side never moved" and "king side never moved"), and that is almost free. But without a good encoding for promotions, I doubt you can beat the encoding of the article.