161–170 of 204 posts
Earlier quoted context omitted.
Finally, a good use case for blockchain technology!
I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
Reading this I realized chess is not fully Markovian (you cannot know everything about the game by just looking at the board at any point), specifically because whether determining if castling and en passant are valid moves depend on the history of the board.
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).
I suspect it would be hard to beat pgn run through a good compression algorithmn. Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets. So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8…
Ignoring board boundaries, a queen has 56 possible moves requiring 6 bits. At any given position on the board, most of those aren't possible because the board is too small, but cramming that into 5 bits will make the encoding much more annoying.
Same thing goes for rooks; ignoring board boundaries there are 28 possible moves, but including the board boundaries there are 14. You can fit that in four bits, but you pick up some context sensitivity.
> 8 also works for pawns (and annoying due to e.p. 4 doesn't)
I don't see the problem? A pawn can move forward two spaces, it can move forward one space, it can capture diagonally to the left, or it can capture diagonally to the right. Those are the only possibilities and they fit into two bits.
En passant enables a pawn to capture a piece that isn't located on the space being captured, and you need to know the state of the board on the previous turn (or, equivalently, what the previous move was) in order to know whether en passant is a legal move... but to encode that it happened, you don't need anything you didn't already have.
Earlier quoted context omitted.
I suspect it would be hard to beat pgn run through a good compression algorithmn. Or similarly essentially a binary version of pgn. Probably the optimalist of optimal is a binary specifying the starting square (6 bits), and then a minimal-width for the specified piece number that indexes against a standard set of move offsets. So, for instance, a knight has (ignoring potential exposed checks, board boundaries, etc, 8…
You only need 5b to encode the piece to move: you know whose turn it is. Also, as the game progresses, you can reindex to reduce the number of bits to define which piece is moving.
If you want to encode the piece (rather than the square), and you're comfortable not counting "whose turn is it?" against the information requirement, you don't need 5 bits. Each player has only 16 pieces, so you can give them all four-bit names.
You won't know what kind of piece they are, though.
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…
You can use duplicate king identifiers to represent castling available, and replace the extra rook identifiers with "black king (my turn)" and "white king (my turn)" to store the turn in the same amount of space. edit: You can then use the inverted/flipped board trick to store one bit of your piece list, down to 191 bits. edit2: You only need one "king (my turn)" ID, which represents the whichever color you didn't us…
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.
You can save 28 bits!... Use log2(4e37) = 124.9 bits for games without piece promotions. Then switch to log2(8.7e45) = 152.6 bits for games with them.
Earlier quoted context omitted.
I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
Nearly every company, what is your source for that? I've never even heard of this before.
Earlier quoted context omitted.
I can't tell if this is in jest or not but blockchains are prolific in software. Nearly every company uses them to prove the authenticity of deployments in production at one or more layers.
No, no they do not.
This structure is used inside your .git directory, your docker manifest, etc.
Blockchains are incredibly useful structures.