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

https://www.ezzeriesa.com/index/Writing%20efa7772a3ae64a8193c7ef981ac619fc/Compressing%20chess%20positions%20for%20fun%20and%20profit%20df1fdb5364eb42fdac11eb23b25e9605.html

by kurinikku • 3 years ago

190 194 3 years ago

ezzeriesa.com

justinzollars• 3 years ago

oh fuck. I feel like this is going to become an interview question.

soamv• 3 years ago

A chess position, not a game (still very interesting though!)

calvinmorrison2• 3 years ago

Storing the game would give you the position though

WithinReason• 3 years ago

It took me a moment to see your point: it might take less information to store the entire game using a chess engine by entropy coding than a single position

madacol• 3 years ago

to be more specific a snapshot of the board

OJFord3• 3 years ago

Original title is:

Compressing chess positions for fun and profit

Which unlike that here is correct: you can store a board, the positions, in 26B; not an arbitrary length game!

petters• 3 years ago

Most games could possibly be encoded in less than 26 bytes. There are not that many legal moves each time and if you sort them by probability it may not require many bits to describe which one the players chose.

NelsonMinar• 3 years ago

that may be but it's not what the article is about.

lainga• 3 years ago

A Huffman code ...? The starting board is 0, 1.e4 is 1, etc...

IshKebab• 3 years ago

I doubt it. You could maybe get as low as 1 bit per move, but how many games are only 26 moves? Would be interesting to find out though!

Maybe this paper says. I didn't read it.

https://www.researchgate.net/figure/Entropy-and-distribution...

solardev2• 3 years ago

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

x86x87• 3 years ago

Iy's not meant for humans to read directly. The compact representation helps performance amd storage a lot when it comes to looking at a lot of positions. If you were to store it as a json most of your time would be spent parsing.

Timon32• 3 years ago

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

umanwizard• 3 years ago

Because easy readable code is less important for competitive modern chess engines than maximum speed and memory efficiency.

Scarblac6• 3 years ago

My lazy brain says "just take the FENs, remove the slashes etc that are just for human readability, and compress the result with Gzip or do. Bound to be smaller in practice."

awegio• 3 years ago

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

solardev2• 3 years ago

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?

alexyz12• 3 years ago

You’ll never get to the moon on 4kb Apollo computers like that

personjerry• 3 years ago

While we're at it, just take a screenshot of the board

catapart2• 3 years ago

Mostly for automation. Bots don't need to read and they are very happy to parse data.

People like to use bots to run thousands or millions of simulated games to test how good their bot is at chess and have it ranked.

Other people like to use the bots that were created to play chess as practice toward a certain skill level. Beginners can pick bots that are proven to be beginner level, through thousands or millions of simulated games.

The smaller the data footprint for the games, the faster and more efficiently the bots can play, which reduces cost and time. In a more practical sense, AI/ML algorithms can be more efficient with tiny data sizes for a bunch of complicated reasons.

So, overall, this is "nerd sniping" to develop better chess players, both human and automated. It's not the most extensible presentation, I'll grant you, but I'm sure it's as fun as Regex Golf, or any other data-packing stuff.

P.S. I'm sure the comp-sci dev in you already knew all this; this is just a bill in case anyone read your comment and truly didn't already know all of this.

DesiLurker2• 3 years ago

in C/C++ code you dont really need to do mental gymnastics either. I can imagine writing a struct with some clever unions to decode this all in one shot. the main benefit as others have point out is 1) to store large number (think billions) of such game positions & searching through them. Also if you are developing for cloud deployment you probably want to use minimal storage needed for space & egress b/w reasons. last reason is something that may not be obvious but if you have some algos that can run efficiently on gpus then you probably want to lay the data out such that its easy(ier) to load in SIMD engines. overall not a bad idea.

about3fitty• 3 years ago

Yep, everyone’s happy until the cosmic rays hit

VyseofArcadia• 3 years ago

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.

thriftwy• 3 years ago

You can compress that JSON with a pre-trained dictionary and get a massive discount.

treyd• 3 years ago

Now try building a chess site to store millions of games with hundreds of millions of game states to search over. It's nice that you can very cheaply fit a board into a fixed size column on a database and store the entire game history into around a kilobyte.

You'd write a wrapper to extract our the dense form to something with a nice interface.

astrobe_2• 3 years ago

In the early 90ies, we used to have pocket electronic chess games. I used to have myself one that was about the size of a pocket calculator (it actually was also a pocket calculator), which included a tiny board with tiny, tiny chess pieces. Not a strong opponent and quite slow, but good enough for casual games on the road.

I doubt you could fit that JSON file in its NVRAM. Sometimes I wonder how much sooner we could have had what smartphones offer us today if some technical choices had been made more... wisely.

But that's the endless conundrum Worse is better [1].

[1] https://dreamsongs.com/RiseOfWorseIsBetter.html

kaashif• 3 years ago

90ies

I've only seen 90s (nineties), never 90ies (ninety-ies). I am imagining the second one pronounced differently.

mrb• 3 years ago

It's as long as my comment

samwillis• 3 years ago

When I was building my multiplayer Sudoku app, I had fun experimenting with how small I could pack a sudoku grid into a URL. I came up with a scheme combining bit packing with the knowledge of how the grid works. So as you move through the grid, based on the knowledge of what's been placed where and the remaining digits you have a fewer options.

Was fun, I was playing code golf with myself. Sadly seem to have lost the code and I didn't use it in the end.

It would probably have been possible to go smaller than I got it by combining it with a sudoku solver, so stop packing positions once it's solvable. But life moved on.

jprete• 3 years ago

I think for Sudoku there are a lot fewer legal board configs than there are arrangements of the numbers. There’s probably a way to store the solved state as a single number and then just use 27 bits to specify which numbers are revealed. I don’t know what that single number looks like, though, and you’d have to check that there was only one legal solution to the revealed numbers.

halfcat• 3 years ago

Thank you for the python-inline-source library. Are you still working on Tetra?

Scarblac6• 3 years ago

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

zeagle2• 3 years ago

Finally, a good use case for blockchain technology!

r3trohack3r3• 3 years ago

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.

ThomasCM4• 3 years ago

Surprisingly, storing a game (with all moves) can take less space than encoding a single board. This is because you can effectively encode a move in a single byte (as there are less than 255 moves possible in each position). Applying compression to the resulting binary string will allow you to reduce the space even more.

Check out this great blog post of Lichess for more information: https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-2...

And shameless plug: Using this encoding, I'm storing millions of games on https://www.chessmonitor.com/ There you can link your Chess.com or Lichess account and view all kind of statistics of your games.

seabass-labrax• 3 years ago

That is a beautifully designed website. I don't think I've ever used an OAuth authentication flow as smooth as the one that your site uses to access my Lichess credentials (same as my HN name, btw, in case you want to beat me at a correspondence game).

ChessMonitor is practically a work of art!

gowld• 3 years ago

Are you saying that, to encode a valid position, ignoring the cost to encode both the starting position and the move definitions, you can encode the move sequence using less information than encoding a single position?

omoikane2• 3 years ago

ChessMonitor looks very nice, I like how you can link to a particular opening:

https://www.chessmonitor.com/u/XqaFNTHcR61WpiMfOhEY/games?po...

foota• 3 years ago

Heh, I guess there are board states that are not possible to reach through a valid sequence of moves, but I guess otherwise it's not possible that games are more compressable by definition, since any valid board state could be represented as a sequence of moves.

This does raise the question of the efficiency of reverse engineering a series of minimal moves for some board state.

TylerE3• 3 years ago

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 possible moves, so to fully encode a knight move you need 6+3=9 bits. 8 also works for pawns (and annoying due to e.p. 4 doesn't). Bishops, queens, and rooks would need a 4/5 bit field. Encode castling as starting from the rook as they have 'spare' moves in their bit set, and kings don't. Encode the end state at the begining.

This is going to use 2 bits for the end state, and then either 9, 10, or 11 bits per move.

thechao• 3 years ago

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.

robertlagrant2• 3 years ago

I suspect it would be hard to beat pgn run through a good compression algorithmn.

I once[0] tried to spread this message :)

[0] https://stackoverflow.com/a/1831841/61938

thaumasiotes3• 3 years ago

Bishops, queens, and rooks would need a 4/5 bit field.

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.

esrauch• 3 years ago

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

dang• 3 years ago

Ok, we've positioned the title above. Thanks!

kurinikku6• 3 years ago

Thank you!

tromp3• 3 years ago

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.

DesiLurker2• 3 years ago

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.

bumbledraven• 3 years ago

Amazing work. This should be the top comment on this page.

kurinikku6• 3 years ago

jade-cat2• 3 years ago

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://en.wikipedia.org/wiki/Fifty-move_rule [1] https://en.wikipedia.org/wiki/Threefold_repetition

Scarblac6• 3 years ago

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.

jade-cat2• 3 years ago

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

thdc• 3 years ago

Yeah, it seems like the author is storing more information than just the position but not enough to figure out all of the possible next states of the game.

Another straightforward thing missing is the player's turn; this could determine whether the position is a stalemate or not.

drivers99• 3 years ago

They'd also need to store whose turn it is, so I'm guessing the article is strictly about "positions" and not game state.

notfed• 3 years ago

I don't see how it can be considered a position without whose turn it is.

hinkley4• 3 years ago

I prefer the Ko rule of Go.

You can’t repeat the last position. But repeating a pattern of part of the board every two turns can force progress to resolution. The entire board never repeats, but it also stops the loop earlier.

pfooti• 3 years ago

An interesting cognitive phenomenon: if you ask chess experts and novices to memorize and recall an arbitrary chessboard, the experts are significantly better than the novices _only if_ the board is a legal board that can be arrived at during play. If it is not a legal board, there's no particular difference between novices and experts. Original ref: Chase & Simon 1973, Perception in Chess.

This is usually taken to mean that the brains (or whatever) of experts see structure that can be used for compression that novices don't, but that compression has assumed invariants you cannot break.

Scarblac6• 3 years ago

It's not really about whether it's legal, but whether it looks normal. Very bizarre positions can easily be legal, but they're hard to remember for everyone.

hinkley4• 3 years ago

I’ve heard this corroborated by exhibition players who play ten or fifteen opponents at once. They do better with moderately skilled opponents than random people.

dmurray• 3 years ago

Not a "legal" board, but a typical board. Both this and the original de Groot study picked positions from real games played by strong players. Experts don't do retrograde analysis on the positions, but they do recognise typical patterns that often occur in real play.

tylerhou• 3 years ago

This isn't just for chess -- it's practically any knowledge task that you can build expertise in.

E.g. take programming. Suppose I sat down an experienced programmer and a novice and gave them the same small (~10-20 line) function to reproduce from memory. If the function is a "reasonably written function" I'm willing to bet that the experienced programmer could reproduce the function with just one or two "peeks" -- once you have enough experience, you can better recognize patterns / chunk your knowledge. A novice doesn't have this ability, so it would likely take them many more peeks.

On the other hand, if the function is some random gibberish with little structure, you could imagine that it's probably equally difficult for both the experienced programmer and the novice to reproduce the function from memory.

For chess, one reason why masters can better recall positions is because they know what typical positions look like (e.g. a position typical of the "London" opening). Then, they only need to store a "diff" of the given position and a typical position. ("It's a typical London setup for White, except White also played a3 and b4.") A novice doesn't have this knowledge, so they have to store the whole position.

jiggawatts5• 3 years ago

The opposite of this is non-expert customers demanding detailed documentation for common patterns in industry.

“Can you please provide more content to explain what a load balancer does?”

svnt• 3 years ago

It’s been a minute since I did this seriously so maybe my magic is out of date but I don’t think this is how bits to bytes works:

100 bits / ~12 bytes
18 bits / ~2 bytes

I didn’t want to spend a whole lot of effort tracking the arithmetic after this. Was it actually 28 bytes? 27 because I can squeeze those extras into one shared byte?

HALtheWise2• 3 years ago

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 that case, with 13 bits of savings. The scheme proposed here reclaims some of that overhead by granting special meaning when a piece's location overlaps with the king, but still is capable of representing other illegal positions where non-king pieces occupy the same square.

Unfortunately, decoding a mathematically optimal encoding quickly devolves to making a list of all possible board configurations and indexing into it, so I'd definitely believe that the proposal here is close to the smallest practically useful representation.

Scene_Cast2• 3 years ago

Couldn't you make it practical by assuming all possible positions (64) for the first piece, then 63 for the second, and so on, and encode one piece at a time? (Arithmetic coding piece by piece)

HALtheWise2• 3 years ago

Yes, although

1. You'd definitely want to deduplicate positions of identical pieces for even more savings 2. That only handles the case where no pieces have been captured, and the full arithmetic coding would probably need separate "sections" of the integer range for different cases, and the number of sections is also quite high. 3. There's extra nuanced things you might want to handle in the coding, like that pawns can't be on their own back row. That is significantly harder.

It looks to me like https://github.com/tromp/ChessPositionRanking has resolved these sorts of issues, but I haven't dug into exactly how.

ToValueFunfetti2• 3 years ago

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.

tromp3• 3 years ago

You need the 2-logarithm rather than the natural logarithm. That gives ~ 152.6 bits, or ~ 19.1 bytes.

xpe4• 3 years ago

Recent results improve that estimate, by proving an upper bound of 8.7x10^45, and showing an upper bound 4×10^37 in the absence of promotions. - Wikipedia (link above)

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.

billfruit• 3 years ago

There is also the Forsyth-Edwards Notation which is in text, can be quite brief if there are only few pieces on the board.

timerol7• 3 years ago

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 there are less than 16 bits set in the bitboard, ignore the last items in the list.

  0000 - 0x0 - black pawn 
  0001 - 0x1 - black pawn (can be en-passant'd)
  0010 - 0x2 - black knight
  0011 - 0x3 - black bishop
  0100 - 0x4 - black rook (castling unavailable)
  0101 - 0x5 - black rook (castling available)
  0110 - 0x6 - black king
  0111 - 0x7 - black queen
  1000 - 0x8 - white pawn 
  1001 - 0x9 - white pawn (can be en-passant'd)
  1010 - 0xA - white knight
  1011 - 0xB - white bishop
  1100 - 0xC - white rook (castling unavailable)
  1101 - 0xD - white rook (castling available)
  1110 - 0xE - white king
  1111 - 0xF - white queen

I think that covers all possibilities to store a chess position in 64 + 32 * 4 = 192 bits, or 24 bytes exactly.

The starting position would be represented with a bitboard of 0xFFFF00000000FFFF, with a list of [0xD, 0xA, 0xB, 0xF, 0xE, 0xB, 0xA, 0xD, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x8, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x5, 0x2, 0x3, 0x7, 0x6, 0x3, 0x2, 0x5], using the same position-to-number scheme in the blog post

Edit: 32 pieces, not 16. Thanks to the peanut gallery for catching it quickly

Edit2: To store which player is next: do nothing for white. For black, if there are 32 pieces, flip the bitboard upside down. (To check if it's black's turn, verify that black pawns are "below" white pawns, which is illegal before captures are made.) If there are less than 32 pieces and it's black's turn, invert the bitboard. (To check, count the number of set bits.) This is entirely taken from https://news.ycombinator.com/item?id=37526484

elteto• 3 years ago

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

timerol7• 3 years ago

Convention - use the same bit-to-number scheme in the blog post. Bit 0 is a1, bit 7 is h1, bit 8 is a2, bit 56 is a8, bit 63 is h8.

penteract4• 3 years ago

There are at most 32 pieces on a chessboard (16 of each color), so I think you need 24 bytes.

timerol7• 3 years ago

... right. I thought 16 felt a little small. Thanks for the catch, updated

k1t• 3 years ago

What if there are 32 pieces on the board?

bhelkey• 3 years ago

A nitpic, to castle, the king AND the rook must not have moved from their starting squares.

Using this approach, you would need to store castling available/unavailable for the kings as well.

penteract4• 3 years ago

If the king has moved, you can just mark both rooks as castling unavailable.

ianferrel• 3 years ago

No you don't. If the king moves, you update both rooks to be unavailable for castling.

sufianrhazi2• 3 years ago

Nice! Though there are max 32 pieces on a board, not 16; so this scheme is 64 + 32 * 4 = 192 bits, or 24 bytes.

The bit to indicate whose turn it is isn't accounted for here. But it probably could probably represented by the binary negation of the bitboard -- if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied.

Taking things further, it probably can be compressed even more with (much) more complex logic, as the castling available bit must only be present on the corner positions, and the pawn en-passant capabilities are only available on the middle rows, so those bits are meaningless in other positions.

timerol7• 3 years ago

I like the bitboard inversion idea. (Requires flipping logic as well from https://news.ycombinator.com/item?id=37526484, since 32 is a special case.) Note that the en-passantable pawns and castle-able rooks came from options that were unused in my first pass (linked comment). I could use 0x1 as "castleable rook or en-passantable pawn, determined from where it is" and then store 32 integers with 13 options in 119 bits[1], saving 9 bits. But I'm kinda attached to the simplicity here.

(The 16->32 was edited as you wrote this comment.)

[1] log(13^32)/log(2) = 118.4

penteract4• 3 years ago

if there are 32 or fewer bits set, then it is white's turn; if there are 33 or more bits set, then it is black's turn and you can negate the bitboard prior to determining which squares are occupied.

This doesn't quite work because if there are exactly 32 bits set, inverting it leaves 32 bits set. You could fix this by marking all pawns belonging to the player who's turn it is as capturable via en-passant (if a player has no pawns left, at least 1 piece has been captured, so inverting the bitboard works).

65102• 3 years ago

There is never a pawn at the 8th row, one might "insert" an en-passant row into the board.

tromp3• 3 years ago

A position, as stored in FEN notation, also includes side-to-move.

devit• 3 years ago

There's a simple trick to encode it: if there are less than 32 pieces, invert the bitboard (easily decoded since boards can't have more than 32), while if there are 32 pieces flip the board vertically (easily decoded because white pawns can't be after black pawns with no captures).

skupig2• 3 years ago

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 use for the other king. You can use the extra value for another "my turn" piece that also sets a bit. 190 bits!

xpe4• 3 years ago

It is necessary to store the ability-to-castle state with each rook; attempting to keep it only attached to each king is insufficient.

65102• 3 years ago

My thought was to have additional schemes depending on the length of the byte array. For example, if the position is an empty array it is the beginning position, if it is 1 byte it represents the most common positions.

"" is the beginning position

"0" is E4

"1" is D4

"2" is C4

"3" is E4 E5

"4" is D4 D5

"5" is G3

One could do a multi byte version where the order of popular positions is replaced with a crappy chess computer.

If there is no en-passant, no promoted pawn and castling is allowed you can use representations slightly shorter than 24.

penteract4• 3 years ago

To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns.

It is necessary to find another way to represent en-passant opportunities (swap an en-passantable pawn with the piece in the 1st or last rank as mentioned https://news.ycombinator.com/item?id=37526523 ).

2 rook representations aren't needed (encode a king with castling opportunities as a knight, bishop or rook, and when decoding, if there are no kings of a given color, look at the piece in the king's starting position) so another 4 bits could be saved by making rook, bishop or knight representations shorter.

alexb_5• 3 years ago

To cut 2 bytes off (while making it much less elegant), huffman coding could be used to store pawns in 3 bits - to guarantee a space reduction, this relies on the fact that if there are n promoted pawns, there must have been at least ceil(n/3) captures, freeing up space for the longer representation of promoted pawns.

Can you explain this in more detail? Curious as to how you could save space with this.

timerol7• 3 years ago

A Huffman code like this can also represent knights (or any single other piece) in 3 bits.

  000 - black pawn
  001 - black knight
  0100 - black bishop
  0101 - black rook
  0110 - black king
  0111 - black queen
  100 - white pawn 
  101 - white knight
  1100 - white bishop
  1101 - white rook
  1110 - white king
  1111 - white queen

Going with "a pawn in the first row is actually en-passantable, and should be swapped with the piece in the appropriate position if it exists", and "kings are represented as knights when they can castle in either direction, bishops when they can only castle kingside, and rooks when they can only castle queenside", that gets the initial representation down to 64 + 16 * 3 (pawns) + 6 * 3 (knights and kings) + 10 * 4 = 170 bits, with a worst case of 172 bits (when kings lose some castling rights), if I understand it correctly.

Huffman encoding for 21.5 bytes seems to win the day.

seanhunter• 3 years ago

As the article discusses, there's a bit more than that to store in a position. Specifically you have to store whether or not castling is available for the two sides and also whether any pawns are en passant targets, since both of those moves are available (or not) conditionally in a given position based on previous moves in the game.

timerol7• 3 years ago

There are specific types mentioned to denote rooks that the king is allowed to castle towards, and pawns that can be en passanted

hinkley4• 3 years ago

I don’t think that’s true. Or rather, it’s only true for storing board position not for storing the move history. If you have the entire move history you know that status of each piece.

jenscow• 3 years ago

small shavings:

* If there are less than 32 bits set in the bitboard, the item list is shorter (rather than ignored).

* Probably not worth it, but: When there are 32 bits set on the bitboard, stop processing the bit-board.. however, if you adjusted the ordering of the lines (0,7,1,2,...), it's optimised for the first 1 or 2 positions

* Maybe this is cheating, but if the size of the game data will be known ahead of processing, then you could leave off the last item in the list if it's a king or a rook

* Starting the item list with 2 white kings can be a special case for "starting position", and if the items are listed before the board then only 1 byte is needed :)

antsou• 3 years ago

I believe you can also do it in a slightly different way. For each square on the board:

0 - encodes no piece in the square; at least 32 of them, so 32 bits (4 bytes)

1xxxx - xxxx being your encoding: encodes remaining pieces; at most 32 of them, so max 32 x 5 bits (20 bytes)

kurinikku6• 3 years ago

OP here. I'm not sure how I overlooked this comment earlier, but this is elegant and it works! It's amazing how you need exactly 4 bits for each bit. Thank you for sharing!

bewaretheirs2• 3 years ago

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.

thurn• 3 years ago

It is of course possible to break these rules via promotion, e.g. having two dark square bishops is entirely possible.

bewaretheirs2• 3 years ago

But in those cases you're missing the pawn that was promoted, so the location of the second dark-square bishop would be encoded in a 6-bit pawn slot rather than a 5-bit or base-33 bishop slot.

Dwedit• 3 years ago

The state of an individual chess piece can be stored in 6 bits. 3 bits for the X coordinate, 3 bits for the Y coordinate.

A captured piece can use the same coordinates as the King, which would indicate that it's captured.

For promoted pieces, you can use 3 bits per promoted piece type (Bishop, Rook, Knight, Queen) to indicate how many exist. For the case of 8 promoted pawns, you'd need one more bit to indicate that all pawns have been promoted and to treat a 7 as an 8.

You need 1 bit to indicate who's turn it is. You need 1 bit per player to indicate if castling is still possible, and 1 bit to indicate if the last pawn move was two squares.

What gets tricky is tracking for the draw rules.

There's '50 moves with no pawn or capture', '3 move repetition', '5 move repetition', '75 moves with no capture or pawn move'. 50 or 75 are simple enough to count, but tracking identical boards from a previous state would be hard to do with limited bits.

So then we have:

6 bits for piece coordinates of 32 pieces (192 bits)

13 bits for pawn promotion status for each player (26 bits)

1 bit per player for castling allowed (2 bits)

1 bit for whose turn

1 bit for en-passant possible

7 bits for move counter with no pawn movement or captures

That works out to 29 bytes.

Edit: Article did promotions much better by removing impossible promoted piece counts.

'Castling allowed' flag could be tied to 'both rooks in their original positions'. If the pieces look like they're in their original positions, but a king or rook moved, swap the two rooks so they're not in the original position anymore.

En-passent check by swapping pawn order is neat, but pawn order could instead be used to eliminate the 'promoted' flag per pawn instead.

JoshuaDavid2• 3 years ago

Minor point: the FIDE rules[1] state

Article 9: The Drawn Game
...
9.2 The game is drawn, upon a correct claim by a player having the move, when the same position for at least the third time (not necessarily by a repetition of moves) [happens and a draw is claimed]
9.3 The game is drawn, upon a correct claim by a player having the move, if: ... 9.3.2 the last 50 moves by each player have been completed without the movement of any pawn and without any capture.
...
9.6 If one or both of the following occur(s) then the game is drawn:
9.6.1 the same position has appeared, as in 9.2.2 at least five times.
9.6.2 any series of at least 75 moves have been made by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence.

This means that, in order to store a full chess game-state, you also need to keep track of how many moves since the last pawn move or capture (for the 50 and 75 move rule (9.3.2 and 9.6.2 respectively)) and also what positions have previously occurred (for the 3 / 5 position repeats, (9.2 and 9.6.1 respectively)).

The maximum number of moves from any chess position is 218 according to this post[2], so each move in the history can be uniquely identified by a single byte. You only need to store the moves since the last capture (since you can't repeat an earlier position), and you _definitely_ can't have more than 112 pawn moves without a capture (because there are only 16 pawns and they can only move forward, except in the case of en-passant which requires a different pawn to move forward twice).

But that gives an upper bound of 8400 moves -- this bound is probably much higher than it needs to be though.

----

[1] https://handbook.fide.com/chapter/E012023

[2] https://www.chess.com/forum/view/fun-with-chess/what-chess-p...

Dylan168079• 3 years ago

If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves".

they can only move forward, except in the case of en-passant

En passant still attacks forward, into the space the enemy pawn just moved through.

112 pawn moves without a capture (because there are only 16 pawns and they can only move forward

But pawns can't move through pawns. ~~At most I think you can have 4 of the pawns march all the way forward and get captured, leaving you with with 4 pawns that can move 6 spaces and 8 pawns that can move 7 spaces, for a total of 80 pawn moves without a capture.~~

Okay, if you sacrifice a bunch of other pieces to pawns, then you can get them to pair up without losing any. So that's 8 pawns moving 6 spaces, and 8 pawns moving 7 spaces. 104 pawn moves in a row without a capture.

JoshuaDavid2• 3 years ago

If a pawn moves then you can't repeat a state either, can you? So track the last 75 "moves".

You are correct.

So the board state from 75 moves previously plus 75 bytes to store the last 75 moves is sufficient to store a chess game state.

aimor2• 3 years ago

What about bishops?

The bishops are limited to half the board so only need 5 bits for position. This frees up 4 bits, but you lose the capture state (can't use King's position for capture state). Well, you CAN use the king's position for capture state for two of the bishops at any given time. Then for the other two bishops use a bit to store their capture state. This saves 2 bits overall, bringing the total down to exactly 26 bytes.

Gonna have to think that through for awhile, not sure if it works out.

Update: I see a comment below that does this but uses 21 bits (instead of 22) by storing bishop position and capture state as a base-33 number.

NextHendrix• 3 years ago

It's possible to gain bishops via promotion which may scupper this plan

aimor2• 3 years ago

Trying to strike a balance between raw enumerations of all valid states and practicality:

Rooks and Knights are identical, so their positions fall into [64 choose 2] states + 1 state for when both are captured (only one can occupy the King's location) + 3 states for when both are in the starting position and castling is available for one or the other or both

  2020 states = 11 bits * 2 colors * 2 piece types = 44 bits

Bishops only occupy half the board (32 states) + 1 state to track captures

  33 states ^ (4 unique pieces) = 21 bits

Queens and Kings just store their location

  64 states = 6 bits * 4 pieces = 24 bits

Pawn promotions uses the same method as the article

  9 bits x 2 colors = 18 bits

En passant can be stored by the column + 1 state for none

  9 states = 4 bits

Pawns can be in, uh, [64 choose 8] position states. (It's only 4 billionish)

  [64 choose 8] states = 32 bits * 2 colors = 64 bits

And captured pawns can be 'unpromoted' and placed on an empty spot in the top row since unpromoted pawns will never be there.

And 1 bit for whose turn it is

  1 bit

Total = 176 bits or 22 bytes

Started out thinking about ways to use more of the duplicate pieces, rediscovered the idea of ranking and unranking, started to understand what the person with a limit of 19.2 bytes was doing, tried out just treating position state as [64 choose 32] and only got to 194 bits, then finally worked through this approach.

omoikane2• 3 years ago

This reminds me of how Oscar Toledo disassembled Video Chess, which ran in just 128 bytes of memory:

https://news.ycombinator.com/item?id=36431917

It uses lower 4 bits of 64 bytes to store the board positions (upper 4 bits is used to store other data). 64 nibbles is 32 bytes, not too far off from the 26 bytes here.

frud• 3 years ago

Any scheme that does not make allowance for illegal moves or invalid positions is not suitable for purpose, IMO. In OTB situations players can make mistakes that no one catches. These illegalities become part of the official record of the game.

Dylan168079• 3 years ago

Oh, no encoding of the turns? Then the encoding I came up with after following in the link to Forsyth–Edwards Notation is even better.

Version 1: For each position on the board, store if it has a piece or not. 8 bytes for that. Then for each piece in order, 4 bits can encode color and type. 16 bytes for that. Then you can spend 4 bits on castle ability, and 4 bits to pick the pawn that is able to be captured en passant (If there isn't one, pick a pawn that isn't in position. It's impossible for all the pawns to be in a vulnerable rank and have an enemy pawn in position.) So that's 25 bytes, no sweat.

Version 2: Instead of 4 bits per piece, store color|0 for a pawn, and color|1|type for anything else. Encode castle-eligible rooks and castle-ineligible rooks as separate types. This costs 14 bytes at the start of the game, and if you promote a piece at least one pawn has to die so the cost increases by 1 bit at most, up to 8 times. So 15 bytes, and you can always squeeze the bits for en passant eligibility into the 15th byte, because more promotions means fewer pawns to keep track of. You can even say whose turn it is by encoding "active turn king" and "inactive turn king" as different types. That's 23 bytes for the entire board state.

Either way you can add the turn counters with 2 more bytes.

Edit: Okay, this version beats mine solidly: https://news.ycombinator.com/item?id=37526804 I was thinking wrong about the number of captures versus promotions, and you can get much more clever with encoding en passant. So 22 bytes or less is enough for this sort of method.

timerol7• 3 years ago

Your version 1 is similar to my top level comment. Note that 4 bits is enough to encode color, type, and include special types for en passantable pawn and castleable rook, so you keep a clean 24 bytes. (Compressing the two special types into one special option, decodable based on position, can get just under 23 bytes.)

For version 2, note that 12 promotions can happen, since one capture (white's B pawn taking black's A pawn) can open up the promotion path for 3 pawns (white's B pawn, white's A pawn, and black's B pawn). Two bits per pawn and 5 bits per other piece start at 14 bytes, but can go as high as 17.5 bytes. (Promoting 12 pawns with 0 other captures would be pretty ridiculous as a game, but technically possible...)

jepler2• 3 years ago

Ignoring whose turn, castling & en passant, a static huffman table isn't terrible:

    0 - empty (1*32=32)
    10y - pawn (color) (3*16=48)
    11xxxy - piece (color) (6*16=96)

The initial board takes 176 bits (22 bytes) to describe. In most games, the definition length would decrease. A game position is self-delimiting as it always has exactly 64 entries (no need to store the variable length)

one of the extra 3 non-pawn piece values can be used to encode 'rook (castling unavailable)' without spending extra bits. a scheme for storing en passant without any additional bits is less clear (but doing it with 3 extra bits is, so 22.375 bytes for positions that would regularly be reached in play).

I think it COULD increase in at least one specific circumstances: two promoted pawns (+6 bits total) with only 1 taken pawn (-3 bits). I think the maximum is 12 promoted pawns and 4 taken pawns which would make some hypothetical board take 204 bits (25.5 bytes) in this encoding.

A static arithmetic encoding (rather than a huffman encoding) of the same values should take a hair less space.

jepler2• 3 years ago

static arithmetic encoding appears to store the initial board, "black to move" and 4 rook "can castle" flags and a 1-of-9 "can en passant" value in 22 bytes. "4 pawns taken + 12 pawns promoted to queens", which I still think is the "complex-est" configuration that might actually be reachable in a valid game, fits in 25 bytes. A board with just 2 kings left on it encodes in 10 bytes (en passant and can castle flags are not needed).

Tommah• 3 years ago

For my chess tactics trainer at https://www.checkmatechamp.net/ , I tried a lot of different techniques to compress a small set of positions (about 800). I was not concerned with storing the positions in a fixed size, so I was mainly trying things that would make the entropy of each compressed position smaller. I eventually fit these into a file that is about 14 KB in size when gzipped. Each position takes about 17.5 bytes, excluding the HTTP headers. If you go to the page and scroll through the positions, you'll see that each position loads instantly. That's because all the positions are in that 14 KB file which is loaded initially. I didn't include the castling or en passant info in that file, but I suspect it wouldn't add more than one byte per position on average.

I only considered techniques that would not cause the decoder to become overly complicated. One "non-standard" technique that I used was inverting the color of all the pieces on one side of the board. Specifically, on the lower half of the board, I change all the white pieces to black and vice versa. This greatly lowers the average entropy of a typical position, since for most of the game, each player keeps most of his pieces on his side of the board. It is also easy to handle in the decoder in one line (if row < 4, then piece = -piece).

I have meaning to write a blog post about it, but I haven't gotten around to it yet. If you are interested in hearing more, let me know, and I will move it up my to-do list.

inimino• 3 years ago

If the colors are symmetrical, then it's just "my pieces" and "opponent's pieces". You could encode who has the move by how the board is ordered, and predict it from the king and queen position, then just encode the differences.

jiggawatts5• 3 years ago

People have pointed out that due to rules about no repeats, the full state requires storing previous moves.

I’m fairly convinced that the most efficient encoding would be keeping only the move history and then playing that forward to obtain the board state.

E.g.: there are only 32 distinct pieces so a 5-bit number can select one uniquely. Each piece has a maximum of about 32 positions it can move to. Then the encoding is just 10 bits per ply. Typical games are 40 moves (80 ply) and hence require just 800 bits or 100 bytes for the whole game history.

Then you could get clever with Huffman coding or the like, since some moves are more common than others.

verteu• 3 years ago

I agree with this for a typical-length game. But I'd guess its worst-case is inferior due to some pathologically long games.

jiggawatts5• 3 years ago

Yes, but pathological games are statistically rare. At scale, the average is what matters…

paxys• 3 years ago

As the game goes on the space needed to store the list of moves increases while space needed to store a snapshot of the board decreases. It would be interesting to figure out where on average the strategies meet.

jiggawatts5• 3 years ago

Replying to my own post: it seems each move can be packed into 8 bits in all but a few rare scenarios such as having many promoted pawns as queens on the board.

See: https://www.chessprogramming.org/Encoding_Moves#Per_Piece_an...

teo_zero5• 3 years ago

The problem is that the encoding of a position by the previous moves is not unique. For example, 1.a2-a3,a7-a6; 2.h2-h3 represents the same position as 1.h2-h3,a7-a6; 2.a2-a3... Chess engines need to remember evaluated positions to avoid reevaluating them, and this scheme doesn't work well for that purpose.

ComplexSystems• 3 years ago

You can get this even lower, without the need for the extra promotion bits, if you make a note of a few things:

1. There is still redundancy in that there are multiple pieces of the same type, and if you permute their locations you get another representation of the same state. 2. You don't need to say that some pawn's location is the king if it's en passant. You can just use the back row, which pawns can't get to.

Using this, you can use the permutations of the pawns to store extra information. For instance, all of the pawns will be on the board at squares #a, #b, ... . Since pawns themselves have numerical indices, you could say that the "canonical" representation of the board state has all of the pawn locations sorted in ascending order. Then, different permutations of that can carry information about promotions and which of the "pawns" are really queens, etc.

kurinikku6• 3 years ago

OP here. Thanks for the suggestion! I really like the idea of there being redundancy for pieces of the same type. If I understand correctly, when a knight is in a particular square say it's not relevant whether it's the king-side or queen-side knight. I believe you still need to keep the ordering for the rooks due to castling, but for the knight and bishop you can store 1-bit each in the ordering. With this we end up with 7 bits for each side, thus below 26 bytes overall!

Let me ponder a bit more on the pawn locations. We do need the pawn ordering since the we've encoded the string representing the promotions in sorted order. In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably.

teo_zero5• 3 years ago

In the case of en passant we know exactly where the pawn would be, and while we can use the back row, I haven't quite figured out how to use this to encode reliably.

If a white pawn in x4 (for x between a and h) can be captured en passant, you encode its position as x1. When decoding, if you see a white pawn in rank 1, you know it can't be there, so you place it in x4 and flags it e.p. Black pawns are analogous.

yewenjie• 3 years ago

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.

phkahler• 3 years ago

The author of the post forgot a bit to indicate which sides turn it is. That's another piece of state you don't get by looking at the board.

xg15• 3 years ago

I wonder if you could shave off some more bits by considering the specific movement restrictions of some pieces:

Bishops can only ever occupy squares of their respective colour, so you'd only have to encode ~32 possible positions instead of 64.

Pawns (before promotion) can only move straight forward and diagonally forward, which makes their range of valid positions a sort of upside-down triangle shape, with the "tip" of the triangle at the respective pawn's starting position. (e.g. it's impossible to move the pawn from A2 to H2 - or even to H8 - without a promotion)

Haven't made the exact calculations, but it might be possible to encode both positions with 5 bits each instead of 6 bits.

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

Related Stories