Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position. The problem here is that drawing can become an option or a requirement based on information that this representation doesn't capture.
First the simpler version of this problem. After 50 full moves without a capture or pawn move, a draw MAY be claimed. After 75 moves, a draw MUST be claimed. This requires a count to be kept that may require up to 7 more bits.
The bigger problem is draw by repetition. If a position repeats exactly (same castling and en passant options) for a third time, then a draw MAY be claimed. If it repeats exactly for a fifth time, then a draw MUST be claimed. (Usually it is claimed on the third time, but you don't have to.) Applying this rule correctly requires not just knowing the current position, but what positions have occurred previously, and how often. Back to the last pawn move, capture, or change in potential castling status. This may require (per the first rule) knowing what up to 75 different past positions were.
The best way to store this history is almost certainly not as a list of positions, but as a history of moves. But, even if done efficiently, we will need more bytes for that history than we needed for the position.
> Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position.
It does not fully capture the history needed for determining future claims of draw by repetition. But by definition, the position fully captures the position.
The notion of position used by the FEN notation [1] includes the board diagram, side to move, castling rights, en-passant options, as well as the number of halfmoves since the last capture or pawn advance, and the total number of moves.
The last one or last two are often ignored in everyday notions of position.
Both examples you have provided are not exactly pertaining to chess POSITION, but rather technicalities to put an upper bound on the time a game may take. Yes, there are rules like 75-move rules, or three-fold repetition, but they have no material bearing on the pieces. On the other hand, FEN does capture information like whether you're eligible for castling, which does make a difference in terms of chess position.
Lichess uses a scheme which is probably more efficient on average, described on revoof's blog[0]. Basically, it's a variable length scheme where the first 64 bits encode square occupancies, followed by piece codes (including castling, side to move, and ep with some trickery), followed by half-move clocks if necessary.
It’s mathematically dissatisfying, but often the most optimal storage (or algorithm) solutions involve clever heuristics that are dynamically applied.
Some systems just have to be observed in order for solutions to be optimally designed around how they actually behave, rather than how they theoretically behave.
It also can encode chess960 positions. With the article's encoding, uncastled rooks can only be decoded if their starting position is known, which it isn't in chess960.
26 bytes is 208 bits, about twice what you really need for a minimal encoding that has enough context (en passant, castling) to generate an accurate set of legal moves. I wrote a chess database tool back in the 90's (CDB) that used 96-bit encodings (if memory serves) to index all the positions reached in a collection of games so that one could see the moves made from any position, their frequencies, and their game outcomes. Good fun.
96 bits is not nearly enough, as there are ~4.8 * 10^44 > 2^148 legal chess positions (with side to move/castling/ep info) [1].
Chess Position Ranking provides a 153 bit encoding but it's very slow to decode.
If the encoding only needs to work for the set of positions occurring in some database, then there's almost no limit to the number of coding optimizations one can make (until the encoding just becomes an index in the set of all unique db positions).
"legal chess positions" is a larger space than pklausler's "observed chess positions". Novel positions reached in future that violated the 96-bit encoding could be encoded using a variable-length additional "patch" suffix.
Given the current upper bound on legal chess positions is 7.7e45 ≈ 152.4 bits, you either have found a better upper bound or your memory doesn't serve.
They didn't try to encode all legal positions though, only ones that were actually reached in their database of games. It sounds very plausible to me that this allows a lot of simplifying assumptions that cut the state space by about 60 bits
I can put it all in, say, 24 bits, if my database is small. 140k games, 120 positions each. log(140000*120)/log(2) ~~ 24.001, and surely there will be some duplication.
The encoding is just the index number of the game + move that resulted in that position.
I remember asking myself this question years ago, and came to 162 bits. I was just a kid back then so the logic is probably wrong but I do wonder how simple the encoding could be under those constraints...
Edit: Here are the Notes
0 Empty
10 Pawn
1100 Knight
1101 Rook
1110 Bishop
1111 Queen
32 + 32 + 472
2 times 6 bits: position of the kings
30 bits: color mask
120 + 2*6 + 30 = 162 bits
We can store the rest using the methods from the blog post and add 18 bits for promotion, giving 180 bits.
I'm sure this isn't the most efficient way, and I think I had other methods and considered things like the bishops being able to occupy 32 squares, though special casing doesn't make sense because of promotions.
Technically if you got 8 bishops/queens/knights/rooks
You would occupy another 16 bits, giving 196 bits
I think the upper limit can be reduced at the cost of increasing the lower limit
EDIT2: I think I made the assumption at the time that to promote one piece you needed to capture at least one enemy pawn, giving the space for the two bits, which means the upper bound is actually 180 bits
Would love to see other people try in the comment section
I thought the same but realized you can retrospectively 'insert' the king positions into the position sequence, shifting the remaining sequence one square along for each king, so no more bits required though the data structure is unwieldy!
Each pawn that wants to be promoted either takes:
(a) another 'special' piece (knight/rook/bishop/queen), in which case it has already bought enough bit budget to later be promoted; or
(b) another pawn, in which case this temporarily saves 1 bit (as the other pawn becomes a space), but then later we need 2 extra bits for the promotion, so we pay 1 bit extra per pawn in total
In the case of (b) there are now fewer pawns that can be promoted, and so worst case, we have to pay a budget of 1 bit per each of 8 promoted pawns.
So I think maximum required bits is only 162 + 8 = 170?
Yep, that increase the total in 3*3-4=5 bits, and you can repeat it 4 times, so the maximum is at least 162+4*5=182.
I'm trying to prove that is the worst case, but there are just too many cases. I guess I'll try to use a program o brute force it or just forget about it.
Actually, given this, we believe that 4 pawns must have been captured to reach 182 bits. So at least 4 pieces no longer need colors. If we store the color mask at the end, I think we can make it variable length, and truncate when no further pieces need colors assigned.
So then we need maximum 182 - 4 = 178 bits
EDIT: Equivalently, we could suffix each non-empty piece in the sequence with an associated color bit
So for each 4 pawn cluster, 1 pawn takes another pawn, and the net result is +1 bit once the captor promotes. The remaining 2 pawns in the cluster each need 2 extra bits when promoted => 2 x 2 = 4 bits. So 5 bits per 4-pawn cluster, of which there are 4.
So maximum representation would be 162 + (5 * 4) = 182 bits?
This nerd-sniped me. I think we should separate "chess board" and "chess game state" as two different problems. For "chess board", we don't consider any castling, en-passant or similar. We might store a bit for "who goes next". This is useful for chess puzzles where state shenanigans are rare (I think).
But if we store castling state, I think we are already trying to store the whole game state, and this is representable only by full history because of move repeating rules.
So, I think storing board state as a sequence of moves is more interesting. I would estimate that a number of possible actions on average is closer to 8 than to 16, so it would give as 3 bits for half-move and 6 bits for full move. 24-move game could be represented with 18 bytes, which is considerably lower than 26 bytes!
You can get close to average bit per move, if you reuse "spare" places for the next move. So, for instance, first move have 20 possibilities, which is representable by 5 bits, but you can reuse "spare" 32-20=12 possibilities as a bit for the next move.
This is a representation assuming you use only "move validator" thing that returns a list of possible moves. I think that if you use a chess engine that would output you a probability distribution of possible moves, you can compress noticeably better on average, but decoding would be slow.
This is fun. Of course this problem is also a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers. Hitting the calculator 26 bytes works out to chess being no more than 4.113761393×10⁶² possible states. I'll start my GPU solving that right now!
[edit]
This made me look for articles estimating this and I found this one [1] which confirms the above is in the right ballpark. Actual study (according to the article) says 4.822 x10^44 is their upper bounds
> a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers
That and therefore doesn’t follow. As a counterexample, consider a NIM (https://en.wikipedia.org/wiki/Nim) game starting with a googolplex number of piles of size 1. That has way more board states than chess or go, but is easily solved, as the game is trivial.
When constraining an entire game being that close as an initial dart throw is pretty good I think. It is also good to use as a check on the plausibility of the author's algorithm. If they had found an encoding that was well below the current estimates for total board states then it likely would have indicated a major flaw (or a major breakthrough worthy of several papers and broader recognition!) At least that is what I meant by 'in the right ballpark'.
> 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.
(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.
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).
I have a lot more to optimize before I'm crunching down the positions but I just made a chess platform[0] with the intention of tracking your play style over many games (integrated with chess.com only for now) because the other ones I've used (including chess.com somehow) only really analyze a game at a time. It was a lot of fun to build and it's been really useful for me to identify some weaknesses and have a 'coach' to talk through them with and replay positions. I'd love feedback from any chess players! (email is in my bio)
I don't understand the castling part of this - you can move a rook from its starting square and back and castling isn't available - it says that you can determine whether castling is available from the location of the pieces?
i think i just misunderstood the writing, it does explicitly say 4bits for castling. the prose around is just describing what castling is - i thought it was implying that you could determine whether castling is possible from the position of the pieces.
He starts out by using 4 bits for castling rights.
Then he introduces the other method (signify that castling is allowed by saying the rook on that side is on the same square as the king) and with that method he doesn't need any extra bits for castling rights.
Edit: it would be better on average to keep the castling bits, and omit the positions of kings and rooks if castling is possible. But that's variable length and it's simply 4 extra bits in the worst case.
Why not do it simpler? :
Create an array with 16 elements, one element per piece, black + white.
Every array element is 7 bits wide, 1 bit for captured or not,
and 6 bits for the square number the piece is on (8 x 8).
Then you need 16 * 7 = 112 bits = 14 bytes.
(And the captured-bit can even be compressed further as a 65th square,
but that makes it more calculation intensive to extract a position)
You only need the piece type for pawns (that can be upgraded), and a bit on the king to track if castling is possible; otherwise a single bit for on-board/captured is sufficient, since the types of the other pieces are implicit in the array index. (You can shave single bits in a few places -- if the state represents a game in progress the king-captured bit isn't needed; natural bishops only need 5 bits for position on board, etc. This doesn't really add up though.)
On the other hand, there are 32 pieces (max) on a chess board, not 16, so grandparent is off by a factor of more than two.
You can only castle if neither the king nor the rook have been moved (and none of the three squares the king uses may be under attack, and all the squares between the rook and the king must be empty).
Since you could move either rook somewhere and then back to their starting squares, you have to track their eligibility separately. If the king moves, both rooks lose eligibility.
I wish these articles acknowledged that densely packed structures like that have significant overhead in terms of the instructions which must be generated to parse them. If that shit gets inlined all over the place, how much bigger is the binary now? Absolute minimalism is rarely the right choice, the size of .text matters too.
That would probably warrant a followup article. I did find myself wondering where the tipping point is between using a slightly less efficient storage method vs. computational overhead.
For example, you technically don't need to track castling availability. If you're storing the entire match as a set of positions, you can deduct that by replaying the previous positions. A quick search seems to indicate that an average chess match runs for about 40 moves, so replaying all previous positions isn't that bad, on average.
If you need to store millions of chess matches, being able to store them in ~1kb each might be more important, compared the overhead of unpacking each state. If you need to query for certain positions across all those matches, maybe less "compression" is desired.
I always enjoy articles about how people store data and how they think of capturing states, but I also like to know the context and how that data is use or queried.
There's a logic error from assuming that because the rook is in its original position that the rook has not moved. Also I'm not sure if en passant is available if the pawn has moved from its home file, even if it subsequently moved back - so you can't assume either of these just by looking at the piece's position.
I think that you need one extra bit, that can contextually encode "rook has moved" or "en passant available".
At the start of the game, qRook - king - kRook all store the location e1.
If the king moves (say we're playing the Bongcloud), qR and kR get set back to their original squares, a1 and h1. Now if the King slides back, castling is off the board.
You could decide if the en passant location is plausible from the position and color of the pawn on ranks 3 & 6, since it's only available of a pawn has moved two squares, so must be on rank 3 or 6, and it hasn't been promoted(another way it could reach those ranks)
If the rook has not ever moved yet, it gets the king's positional value. As both pieces can't overlap, assume the king's positional value is correct and the rook is at starting position.
Then, as soon as the rook is moved, it gets its actual positional value. If it moves back later, the positional value will be that of the rook's starting position (guaranteed different from the king's current positional value as the two pieces can't overlap).
It would be if castle is available, not simply if the rook has never moved.
Likewise, the position of a pawn can be assigned the king’s position if it has made the double move. You know it’s actually in the legal file and in which rank it sits after the move.
I would do it like this. There are 32 pieces, any of which may be missing. So let's use four bytes (32 bits) as a mask of what pieces are present. Then, coordinates can be given for each piece that is present. The board is 8x8, so coordinates can be encoded as pairs of 3 bits, e.g. A3 is 000:011. The worst case is that we need 32 of these pairs, which requires 24 bytes. That brings us to a worst case of 28.
How can we eliminate two bytes?
We can more cleverly encode the mask so that two bytes are used to express the all-pieces-present, and certain other cases. A fully decoded mask is only used for boards that have too few pieces to break over 26 bytes.
For instance suppose we have a two-bit header encoding several cases:
00 - no piece are missing (32 six-bit coordinates follow)
01 - one piece is missing, followed by 5 bit ID of that piece
10 - two pieces are missing, followed by two 5 bit IDs of the two pieces
11 - three or more pieces missing, full mask follows.
In case 11, we need a 32 bit mask, followed by as many as 29 coordinate pairs.
Right we need some additional state for ampassan and whether counseling is available and such, not just the raw position.
However, am I mistaken? The article appears to be neglecting to record one bit of information: whose turn is it for this board position, black or white? If you're going to care about whether castling is available and other such game state, that is not complete without knowing whose turn it is for that position.
I know of two distinct methods of encoding any legal chess position into 24 bytes worst case. In both cases, you get the full position, plus who to move, plus full information on future castling and en-passant possibilities. This is the FEN state of the board, minus the two counts. It's more than the information you get from a published chess diagram in a book or magazine. Although in a book or magazine inevitably "who to move" is represented somehow, castling and en-passant possibilities are not usually.
Method 1: Lichess method; 64 bit header, 1 bit per square indicating occupied squares, then (up to) 32 4 bit codes for the 32 occupied squares. So 24 bytes worst case!
Method 2: My own method a list of 2 bit codes, one of the 4 codes indicates empty square, the other three codes are prefixes for a second 2 bit code. Three prefixes applied to one of 4 code values gives a total of 12 possibilities corresponding to any possible chess piece. Worst case 32x2 bits plus 32x4 bits = 24 bytes.
In each case there is sufficient entropy to create tricks to add the supplementary information (who to move etc.), similar tricks are in the original article.
I mention my own method from my Tarrasch Chess GUI https://github.com/billforsternz/tarrasch-chess-gui only for completeness. If I had known about method 1 I would have used that, it is simpler and better and there is much more entropy available making the tricks easier.
I would urge commentators to keep clear the difference between compressing a chess position (this challenge), a chess move and a chess game. A chess move needs far less bits of course. A complete chess game is always encoded as a list of moves, not positions, for this reason.
Edit: I should have mentioned that the chief advantage of method 1 over method 2 is average bits required. An empty board is 64x1 bits = 8 bytes for method 1 and 64x2 bits = 16 bytes for method 2.
Edit 2: I am going to describe my tricks, just because they are fun. Two kings the same colour means Black to move. Two White kings means the first king is white, two black kings means the first king is black. Otherwise White to move. A friendly pawn on the first rank means an enpassant vulnerable pawn. Swap it with the 4th rank square to get the actual contents of both squares. A hostile pawn on the first rank is an unmoved rook or king, establishing all castling rights. The castling and en-passant tricks can be combined in a pleasant and harmonious way.
Did you reach 30 by taking a number from the blog and adding to it? The first real size estimate in the post includes promoting to any piece, storing an entire 3 bits per pawn for all 16 pawns. This later gets optimized to 9 bits per side.
Sorry I was in the car and read the headline and tried to see how I would do it as an exercise. I actually think I undercounted because for the king and rooks you have to store whether they have been moved yet, and for the pawns whether they just jumped two spaces (so you know if en passant is a valid move).
So I wasn't saying the article is wrong, just engaging in a bit of intellectual exercise.
My count was: there are 16 pawns, each could be in one of 64 places or not on the board, so 6+1 bits per pawn for that, and each could be promoted to a knight a bishop a rook or a queen, so 4+1 bits per pawn for that, and one of them might have just moved two spaces, so 3+1 bits for that. And the other 16 pieces don't change their nature so we only need to know where they are, so 6+1 bits for each of those, plus 3 bits for each of the rooks and the king to tell if they have already been moved. That's.. 40 bytes actually. Im really curious how they got it in 26.
Update: I see! They used illegal positions to store all the special statuses. Very clever!
You have a good starting point, but using 6+1 bits is a bad way to encode 65 possibilities. If you use base 65, you'll see that 65^32 possibilities only require one more bit to store than 64^32.
And four promotion possibilities wouldn't be 4 bits, it would be 2. But even better is 5^16 squeezing into 38 bits.
Combining those cuts your strategy down to 192.7+37.2+4+6 bits which is 30 bytes.
The main savings the article has is being smarter about how to store promotions. And then it uses some tricks by swapping pieces to encode extra bits.
(But it turns out that storing which tiles are occupied, then listing each piece in order, works better than encoding locations.)
Yes, I made a few mistakes and I did realize I didn't need the whole extra bit to store 65 possible locations- I just was being a bit lazy. Ba dum tiss.
Hmm as a bit field followed by piece order- that would be 8 bytes followed by a variable number of pieces, perhaps you could do a sort of compression where 0c means pawn and 1xxxc is any other piece. (c stands for a color bit). So thats another 14 bytes. Thats 22 bytes!
The xxx by the way is one of 8 things: k, k not moved, r, r not moved, n, b, q, en passant pawn
From the previous HN discussion, 00c for pawn and xxxc for other pieces is probably the optimal way to encode pieces into whole bits. Because you can sacrifice 1 pawn to enable 3 promotions, so you need to handle up to 28 non-pawns. With 2/5 you start at 14 bytes but can need up to 17.5. With 3/4 you start at 14 bytes and never need more than 14.
With 6 xxx states instead of 8, you can merge "king not moved", "rook not moved", and "en passant pawn" into a single state since those can never overlap. (Though if you're encoding one pawn the long way that means you need 14.125 bytes, oh well.)
"The 'bit-level magic' here is misleading. They're using integer representations and calling them bits. A true bit-level approach would encode positions as pure binary streams. For example, their promotion string '00000034' is 8 bytes (64 bits), not the claimed 9 bits. Has anyone implemented this with actual bitwise operations instead of integer packing?
TLDR: You stupi...lovely folks, need learn what a bit is. What is a byte, and why integers are NOT BITS.
And no one called this post out from years ago? Crazy.
Someone ask, and I will show you how to do it in 24 BYTES IN BINARY ENCODING FOR REAL - no fake "integers are bits". And can we use compression techniques? We can get this to 10-12 bytes maybe.
So it beats the fake "26 bytes" and my version is actually real binary bits.
You're proving my point. Yes, 495 possibilities CAN be stored in 9 bits. But the article shows STRING '00000034' (64 bits) as an example, not the actual 9-bit binary encoding. That's exactly the problem - claiming bit-level compression while showing byte-level examples.
And if you look at article, nothing is binary encoded, they are all integer representations all the way down.
Please someone show me a BIT implementation of this - THESE ARE BITS 0 1 0 1 1 0 - It's called BINARY. There are no 9, or 5, or 3 or 4.....That isn't how logic gates work.
A 3 / INT is 8 BITS...1 BYTE.
HINT: I'm right.
And you never answered my question:
"Has anyone implemented this with actual bitwise operations instead of integer packing?"
Still waiting to see these "9-bit" "bytes"."00000034".
Again, show me. There is no such thing as a 9-bit byte, that isn't how CPUs or computation work. ITS 8 BITS 1 BYTE, that is transistor / gate design architecture.
Yes 9 bits is 2 bytes. The article confusingly says 18 bits = ~2 bytes. It is the "about 2 bytes" that is confusing. They probably mean that an extra bit won't matter too much since we are bit packing the games in a contiguous stream.
BUT
In the article they don't mean that 00000034 is a bit or a byte. It is one of the possibilities and there are 495 of them and if you index each possibly in a 2 byte integer, you can decode it back to that string and get a representation of the promotions that happened in any game.
You understand me, this is most important. And thank you for explaining this exercise - but to be honest, if the article says "How to store a chess position in 26 bytes"
And you actually cannot store this in 26 bytes based on your implementation, and then you show integer bits and bytes that aren't even binary...eh.
And to be honest, like how about we store the chess position in 1 bit.
I will execute some chess position program in 1 bit, ON / 1. How about that for ultra compression? Lets just pretend those other random bits and bytes don't exist I mean (...but they do...) - it's stored somewhere else, but "HOW TO STORE A CHESS POSITION IN 1 BIT" - but ok, fine I will play "pretend" |How to store a chess position in 26 bytes (2022)|
I'd especially hammer the point in this case, because clever hacks are very much on topic for Hacker News. They are, in fact, what gave birth to the word hacker and the idea of hacking in the first place. Not only that but it was precisely the clever hacks with no particular utility that were prized most highly!
If you are writing a chess engine you'll want to store hundreds of millions of positions while you search for the best move and at that scale a byte is important because it gets multiplied by an enormous factor.
But that is a totally different problem which requires far fewer bytes to represent. For that problem you are just considering of the valid pieces which made a move and what board that came from. Storing a single move is far cheaper than an entire board state.
Not when you include transpositions, where you arrive at the same position from a different move order, in which case saving board states instead of moves could be very valuable.
There are transposition tables for that though. They don't store the board state actually. For Stockfish, transposition table entries are 10 bytes each, 16 bits of which are the low bits(or high? Can't remember) of a zobrist hash of the board state. The other 48 bits of the hash are used for addressing into the hash table, but aren't stored in it. The rest of the entry will be stuff like the best move found during the previous search(16 bits), the depth of that search(8 bits), evaluation(2 different ones at 16 bits each), and various bits of data like node type and age of the entry(for deciding which entry to replace, because this table is always full). Collisions can occasionally happen, but saving a full board state to eliminate them would cost far too much, since no matter how big you make the table, it'll never be big enough to cache all the board states a search visits.
In Stockfish, there will only be one full-fledged board state in memory per search thread. So the size of the board state is pretty much irrelevant to performance. What's important is reducing the overhead of generating possible moves, applying those moves to the board state, and hashing the board state, which is what magic bitboards are for.
Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position. The problem here is that drawing can become an option or a requirement based on information that this representation doesn't capture.
First the simpler version of this problem. After 50 full moves without a capture or pawn move, a draw MAY be claimed. After 75 moves, a draw MUST be claimed. This requires a count to be kept that may require up to 7 more bits.
The bigger problem is draw by repetition. If a position repeats exactly (same castling and en passant options) for a third time, then a draw MAY be claimed. If it repeats exactly for a fifth time, then a draw MUST be claimed. (Usually it is claimed on the third time, but you don't have to.) Applying this rule correctly requires not just knowing the current position, but what positions have occurred previously, and how often. Back to the last pawn move, capture, or change in potential castling status. This may require (per the first rule) knowing what up to 75 different past positions were.
The best way to store this history is almost certainly not as a list of positions, but as a history of moves. But, even if done efficiently, we will need more bytes for that history than we needed for the position.
> Either we have to say that the position does not dictate the possible moves, or that this does not fully capture the position.
It does not fully capture the history needed for determining future claims of draw by repetition. But by definition, the position fully captures the position.
The notion of position used by the FEN notation [1] includes the board diagram, side to move, castling rights, en-passant options, as well as the number of halfmoves since the last capture or pawn advance, and the total number of moves. The last one or last two are often ignored in everyday notions of position.
[1] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...
The question is, are we storing the state of a chess game, or the state of a chess board?
If a game, you might also include timers or other state as well, including full position history.
You may even need envelope encryption for the currently unrevealed post-adjournment move.
Problem need to include the year in the encoding then
> third time, then a draw MAY be claimed. If it repeats exactly for a fifth time, then a draw MUST be claimed
Wow I don't know any online or offline platform which draws on five fold repetition. Didn't know that was a thing at all!
Both examples you have provided are not exactly pertaining to chess POSITION, but rather technicalities to put an upper bound on the time a game may take. Yes, there are rules like 75-move rules, or three-fold repetition, but they have no material bearing on the pieces. On the other hand, FEN does capture information like whether you're eligible for castling, which does make a difference in terms of chess position.
Lichess uses a scheme which is probably more efficient on average, described on revoof's blog[0]. Basically, it's a variable length scheme where the first 64 bits encode square occupancies, followed by piece codes (including castling, side to move, and ep with some trickery), followed by half-move clocks if necessary.
0: https://lichess.org/@/revoof/blog/adapting-nnue-pytorchs-bin...
It’s mathematically dissatisfying, but often the most optimal storage (or algorithm) solutions involve clever heuristics that are dynamically applied.
Some systems just have to be observed in order for solutions to be optimally designed around how they actually behave, rather than how they theoretically behave.
It also can encode chess960 positions. With the article's encoding, uncastled rooks can only be decoded if their starting position is known, which it isn't in chess960.
26 bytes is 208 bits, about twice what you really need for a minimal encoding that has enough context (en passant, castling) to generate an accurate set of legal moves. I wrote a chess database tool back in the 90's (CDB) that used 96-bit encodings (if memory serves) to index all the positions reached in a collection of games so that one could see the moves made from any position, their frequencies, and their game outcomes. Good fun.
96 bits is not nearly enough, as there are ~4.8 * 10^44 > 2^148 legal chess positions (with side to move/castling/ep info) [1].
Chess Position Ranking provides a 153 bit encoding but it's very slow to decode.
If the encoding only needs to work for the set of positions occurring in some database, then there's almost no limit to the number of coding optimizations one can make (until the encoding just becomes an index in the set of all unique db positions).
[1] https://github.com/tromp/ChessPositionRanking
Yes, that number just can't be right; thank you for the check.
"legal chess positions" is a larger space than pklausler's "observed chess positions". Novel positions reached in future that violated the 96-bit encoding could be encoded using a variable-length additional "patch" suffix.
Given the current upper bound on legal chess positions is 7.7e45 ≈ 152.4 bits, you either have found a better upper bound or your memory doesn't serve.
They didn't try to encode all legal positions though, only ones that were actually reached in their database of games. It sounds very plausible to me that this allows a lot of simplifying assumptions that cut the state space by about 60 bits
I can put it all in, say, 24 bits, if my database is small. 140k games, 120 positions each. log(140000*120)/log(2) ~~ 24.001, and surely there will be some duplication.
The encoding is just the index number of the game + move that resulted in that position.
The duplication is the problem if you want to use positions as DB keys.
Now I'm wondering if it is a "legal" chess position to get the pieces to swap sides ... a solver to find how to do it would be amusing.
Obviously not possible -- how would pawns pass each other without captures?
Ah! True, I worked out how you could have OTHER pieces get around a pawn, but pawns themselves can't get past each other.
Not what you asked for, sorry, but it reminded me of this gem - https://www.youtube.com/watch?v=C5JVFCouXIU
I remember asking myself this question years ago, and came to 162 bits. I was just a kid back then so the logic is probably wrong but I do wonder how simple the encoding could be under those constraints...
Edit: Here are the Notes
0 Empty
10 Pawn
1100 Knight
1101 Rook
1110 Bishop
1111 Queen
32 + 32 + 472
2 times 6 bits: position of the kings
30 bits: color mask
120 + 2*6 + 30 = 162 bits
We can store the rest using the methods from the blog post and add 18 bits for promotion, giving 180 bits.
I'm sure this isn't the most efficient way, and I think I had other methods and considered things like the bishops being able to occupy 32 squares, though special casing doesn't make sense because of promotions.
Technically if you got 8 bishops/queens/knights/rooks You would occupy another 16 bits, giving 196 bits
I think the upper limit can be reduced at the cost of increasing the lower limit
EDIT2: I think I made the assumption at the time that to promote one piece you needed to capture at least one enemy pawn, giving the space for the two bits, which means the upper bound is actually 180 bits
Would love to see other people try in the comment section
Considering at least half of all squares are empty, further compression is in order for the empty space.
Also if you're encoding the king as a position instead of a byte sequence you would have to encode their space as empty, that's an extra 2 bits
I thought the same but realized you can retrospectively 'insert' the king positions into the position sequence, shifting the remaining sequence one square along for each king, so no more bits required though the data structure is unwieldy!
Only half of the squares are empty, you can almost make a chechboard pattern with the pieces. I don't expect an easy small worst case.
Each pawn that wants to be promoted either takes: (a) another 'special' piece (knight/rook/bishop/queen), in which case it has already bought enough bit budget to later be promoted; or (b) another pawn, in which case this temporarily saves 1 bit (as the other pawn becomes a space), but then later we need 2 extra bits for the promotion, so we pay 1 bit extra per pawn in total
In the case of (b) there are now fewer pawns that can be promoted, and so worst case, we have to pay a budget of 1 bit per each of 8 promoted pawns.
So I think maximum required bits is only 162 + 8 = 170?
Among 4 pawns like white and black a&b pawns, you only need 1 pawn capture to allow the other 3 pawns to promote.
Yep, that increase the total in 3*3-4=5 bits, and you can repeat it 4 times, so the maximum is at least 162+4*5=182.
I'm trying to prove that is the worst case, but there are just too many cases. I guess I'll try to use a program o brute force it or just forget about it.
Actually, given this, we believe that 4 pawns must have been captured to reach 182 bits. So at least 4 pieces no longer need colors. If we store the color mask at the end, I think we can make it variable length, and truncate when no further pieces need colors assigned.
So then we need maximum 182 - 4 = 178 bits
EDIT: Equivalently, we could suffix each non-empty piece in the sequence with an associated color bit
Great point.
So for each 4 pawn cluster, 1 pawn takes another pawn, and the net result is +1 bit once the captor promotes. The remaining 2 pawns in the cluster each need 2 extra bits when promoted => 2 x 2 = 4 bits. So 5 bits per 4-pawn cluster, of which there are 4.
So maximum representation would be 162 + (5 * 4) = 182 bits?
To extend this to entire game histories, here's the Lichess blog post, "Compressing Chess Moves Even Further, To 3.7 Bits Per Move": https://lichess.org/@/marcusbuffett/blog/compressing-chess-m...
This nerd-sniped me. I think we should separate "chess board" and "chess game state" as two different problems. For "chess board", we don't consider any castling, en-passant or similar. We might store a bit for "who goes next". This is useful for chess puzzles where state shenanigans are rare (I think).
But if we store castling state, I think we are already trying to store the whole game state, and this is representable only by full history because of move repeating rules.
So, I think storing board state as a sequence of moves is more interesting. I would estimate that a number of possible actions on average is closer to 8 than to 16, so it would give as 3 bits for half-move and 6 bits for full move. 24-move game could be represented with 18 bytes, which is considerably lower than 26 bytes!
You can get close to average bit per move, if you reuse "spare" places for the next move. So, for instance, first move have 20 possibilities, which is representable by 5 bits, but you can reuse "spare" 32-20=12 possibilities as a bit for the next move.
This is a representation assuming you use only "move validator" thing that returns a list of possible moves. I think that if you use a chess engine that would output you a probability distribution of possible moves, you can compress noticeably better on average, but decoding would be slow.
Previously discussed (2022):
https://news.ycombinator.com/item?id=37525348
This is fun. Of course this problem is also a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers. Hitting the calculator 26 bytes works out to chess being no more than 4.113761393×10⁶² possible states. I'll start my GPU solving that right now!
[edit] This made me look for articles estimating this and I found this one [1] which confirms the above is in the right ballpark. Actual study (according to the article) says 4.822 x10^44 is their upper bounds
[1] https://chess-grandmaster.com/how-many-possible-chess-positi...
> a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers
That and therefore doesn’t follow. As a counterexample, consider a NIM (https://en.wikipedia.org/wiki/Nim) game starting with a googolplex number of piles of size 1. That has way more board states than chess or go, but is easily solved, as the game is trivial.
Wondering if there's a typo or I misunderstand something, but isn't one of these 10^18 bigger than the other? That would be a pretty big ballpark.
When constraining an entire game being that close as an initial dart throw is pretty good I think. It is also good to use as a check on the plausibility of the author's algorithm. If they had found an encoding that was well below the current estimates for total board states then it likely would have indicated a major flaw (or a major breakthrough worthy of several papers and broader recognition!) At least that is what I meant by 'in the right ballpark'.
> 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.
(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.
Multiplying 32 numbers each over 5 bits long obviously results in more than 160 bits. 64!/32! > 2^178.3
Oops! Thanks, the issue was with DuckDuckGo's calculator which I mistakenly trusted:
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).
I have a lot more to optimize before I'm crunching down the positions but I just made a chess platform[0] with the intention of tracking your play style over many games (integrated with chess.com only for now) because the other ones I've used (including chess.com somehow) only really analyze a game at a time. It was a lot of fun to build and it's been really useful for me to identify some weaknesses and have a 'coach' to talk through them with and replay positions. I'd love feedback from any chess players! (email is in my bio)
[0] https://chessfiend.com
I don't understand the castling part of this - you can move a rook from its starting square and back and castling isn't available - it says that you can determine whether castling is available from the location of the pieces?
If the rook has the king's position, it's never moved. As soon as it moves, it can have any position except the king's.
i think i just misunderstood the writing, it does explicitly say 4bits for castling. the prose around is just describing what castling is - i thought it was implying that you could determine whether castling is possible from the position of the pieces.
He starts out by using 4 bits for castling rights.
Then he introduces the other method (signify that castling is allowed by saying the rook on that side is on the same square as the king) and with that method he doesn't need any extra bits for castling rights.
Edit: it would be better on average to keep the castling bits, and omit the positions of kings and rooks if castling is possible. But that's variable length and it's simply 4 extra bits in the worst case.
It starts off with 4 bits for castling, then optimizes it into a piece swap that takes 0 bits (though the piece swap as written might be flawed).
Why not do it simpler? : Create an array with 16 elements, one element per piece, black + white. Every array element is 7 bits wide, 1 bit for captured or not, and 6 bits for the square number the piece is on (8 x 8). Then you need 16 * 7 = 112 bits = 14 bytes. (And the captured-bit can even be compressed further as a 65th square, but that makes it more calculation intensive to extract a position)
Each side has 16 pieces, so you need 32 elements.
Ah how silly of me, that woud make it 28 bytes. (I had the nagging feeling I was missing something :-) And promotions are also not covered by this...
+ 3 bits for piece type?
You only need the piece type for pawns (that can be upgraded), and a bit on the king to track if castling is possible; otherwise a single bit for on-board/captured is sufficient, since the types of the other pieces are implicit in the array index. (You can shave single bits in a few places -- if the state represents a game in progress the king-captured bit isn't needed; natural bishops only need 5 bits for position on board, etc. This doesn't really add up though.)
On the other hand, there are 32 pieces (max) on a chess board, not 16, so grandparent is off by a factor of more than two.
Two bits on the king for castling, queenside and kingside.
Why not just one bit "castled"?
You can only castle if neither the king nor the rook have been moved (and none of the three squares the king uses may be under attack, and all the squares between the rook and the king must be empty).
Since you could move either rook somewhere and then back to their starting squares, you have to track their eligibility separately. If the king moves, both rooks lose eligibility.
I wish these articles acknowledged that densely packed structures like that have significant overhead in terms of the instructions which must be generated to parse them. If that shit gets inlined all over the place, how much bigger is the binary now? Absolute minimalism is rarely the right choice, the size of .text matters too.
That would probably warrant a followup article. I did find myself wondering where the tipping point is between using a slightly less efficient storage method vs. computational overhead.
For example, you technically don't need to track castling availability. If you're storing the entire match as a set of positions, you can deduct that by replaying the previous positions. A quick search seems to indicate that an average chess match runs for about 40 moves, so replaying all previous positions isn't that bad, on average.
If you need to store millions of chess matches, being able to store them in ~1kb each might be more important, compared the overhead of unpacking each state. If you need to query for certain positions across all those matches, maybe less "compression" is desired.
I always enjoy articles about how people store data and how they think of capturing states, but I also like to know the context and how that data is use or queried.
The king can't be captured, so the capture bit for the kings can be used for something else.
Bishops only need 5 bits instead of 6 (they can't move to a square of different color), shaving 2 bits and thus reaching exactly 26 bytes.
BTW 495 can be computed as a binomial coefficient C(8+5-1,5-1), the number of combinations of 8 elements chosen with repetitions from 5 elements.
Should be able to shave 4 bits, cause there's four bishops?
Doh of course. But the 26 bytes + 2 bits irritated me so I didn't think about it.
I think didn't mention the bit for whose move it is? Luckily, he has a few spare bits.
There's a logic error from assuming that because the rook is in its original position that the rook has not moved. Also I'm not sure if en passant is available if the pawn has moved from its home file, even if it subsequently moved back - so you can't assume either of these just by looking at the piece's position.
I think that you need one extra bit, that can contextually encode "rook has moved" or "en passant available".
At the start of the game, qRook - king - kRook all store the location e1.
If the king moves (say we're playing the Bongcloud), qR and kR get set back to their original squares, a1 and h1. Now if the King slides back, castling is off the board.
You could decide if the en passant location is plausible from the position and color of the pawn on ranks 3 & 6, since it's only available of a pawn has moved two squares, so must be on rank 3 or 6, and it hasn't been promoted(another way it could reach those ranks)
If the rook has the king's position, it's never moved. As soon as it moves, it can have any position except the king's.
To make this work, the rook can only have the king's position, if neither the king nor that rook have moved.
How do you differentiate between "never moved" and "moved but moved back"?
If the rook has not ever moved yet, it gets the king's positional value. As both pieces can't overlap, assume the king's positional value is correct and the rook is at starting position.
Then, as soon as the rook is moved, it gets its actual positional value. If it moves back later, the positional value will be that of the rook's starting position (guaranteed different from the king's current positional value as the two pieces can't overlap).
It would be if castle is available, not simply if the rook has never moved.
Likewise, the position of a pawn can be assigned the king’s position if it has made the double move. You know it’s actually in the legal file and in which rank it sits after the move.
I would do it like this. There are 32 pieces, any of which may be missing. So let's use four bytes (32 bits) as a mask of what pieces are present. Then, coordinates can be given for each piece that is present. The board is 8x8, so coordinates can be encoded as pairs of 3 bits, e.g. A3 is 000:011. The worst case is that we need 32 of these pairs, which requires 24 bytes. That brings us to a worst case of 28.
How can we eliminate two bytes?
We can more cleverly encode the mask so that two bytes are used to express the all-pieces-present, and certain other cases. A fully decoded mask is only used for boards that have too few pieces to break over 26 bytes.
For instance suppose we have a two-bit header encoding several cases:
00 - no piece are missing (32 six-bit coordinates follow)
01 - one piece is missing, followed by 5 bit ID of that piece
10 - two pieces are missing, followed by two 5 bit IDs of the two pieces
11 - three or more pieces missing, full mask follows.
In case 11, we need a 32 bit mask, followed by as many as 29 coordinate pairs.
So 2 + 32 + 6 * 29 = 208 bits.
And hey look, by dumb luck, 208 / 8 = 26.
I will check the article later.
Right we need some additional state for ampassan and whether counseling is available and such, not just the raw position.
However, am I mistaken? The article appears to be neglecting to record one bit of information: whose turn is it for this board position, black or white? If you're going to care about whether castling is available and other such game state, that is not complete without knowing whose turn it is for that position.
* en passant
what's wrong with scrolling on that blog? arrow keys don't work
notion
?
I know of two distinct methods of encoding any legal chess position into 24 bytes worst case. In both cases, you get the full position, plus who to move, plus full information on future castling and en-passant possibilities. This is the FEN state of the board, minus the two counts. It's more than the information you get from a published chess diagram in a book or magazine. Although in a book or magazine inevitably "who to move" is represented somehow, castling and en-passant possibilities are not usually.
Method 1: Lichess method; 64 bit header, 1 bit per square indicating occupied squares, then (up to) 32 4 bit codes for the 32 occupied squares. So 24 bytes worst case!
Method 2: My own method a list of 2 bit codes, one of the 4 codes indicates empty square, the other three codes are prefixes for a second 2 bit code. Three prefixes applied to one of 4 code values gives a total of 12 possibilities corresponding to any possible chess piece. Worst case 32x2 bits plus 32x4 bits = 24 bytes.
In each case there is sufficient entropy to create tricks to add the supplementary information (who to move etc.), similar tricks are in the original article.
I mention my own method from my Tarrasch Chess GUI https://github.com/billforsternz/tarrasch-chess-gui only for completeness. If I had known about method 1 I would have used that, it is simpler and better and there is much more entropy available making the tricks easier.
I would urge commentators to keep clear the difference between compressing a chess position (this challenge), a chess move and a chess game. A chess move needs far less bits of course. A complete chess game is always encoded as a list of moves, not positions, for this reason.
Edit: I should have mentioned that the chief advantage of method 1 over method 2 is average bits required. An empty board is 64x1 bits = 8 bytes for method 1 and 64x2 bits = 16 bytes for method 2.
Edit 2: I am going to describe my tricks, just because they are fun. Two kings the same colour means Black to move. Two White kings means the first king is white, two black kings means the first king is black. Otherwise White to move. A friendly pawn on the first rank means an enpassant vulnerable pawn. Swap it with the 4th rank square to get the actual contents of both squares. A hostile pawn on the first rank is an unmoved rook or king, establishing all castling rights. The castling and en-passant tricks can be combined in a pleasant and harmonious way.
In my head I count 30 bytes, since all 16 pawns can be underpromoted to a bishop rook or knight.
Did you reach 30 by taking a number from the blog and adding to it? The first real size estimate in the post includes promoting to any piece, storing an entire 3 bits per pawn for all 16 pawns. This later gets optimized to 9 bits per side.
Sorry I was in the car and read the headline and tried to see how I would do it as an exercise. I actually think I undercounted because for the king and rooks you have to store whether they have been moved yet, and for the pawns whether they just jumped two spaces (so you know if en passant is a valid move).
So I wasn't saying the article is wrong, just engaging in a bit of intellectual exercise.
My count was: there are 16 pawns, each could be in one of 64 places or not on the board, so 6+1 bits per pawn for that, and each could be promoted to a knight a bishop a rook or a queen, so 4+1 bits per pawn for that, and one of them might have just moved two spaces, so 3+1 bits for that. And the other 16 pieces don't change their nature so we only need to know where they are, so 6+1 bits for each of those, plus 3 bits for each of the rooks and the king to tell if they have already been moved. That's.. 40 bytes actually. Im really curious how they got it in 26.
Update: I see! They used illegal positions to store all the special statuses. Very clever!
You have a good starting point, but using 6+1 bits is a bad way to encode 65 possibilities. If you use base 65, you'll see that 65^32 possibilities only require one more bit to store than 64^32.
And four promotion possibilities wouldn't be 4 bits, it would be 2. But even better is 5^16 squeezing into 38 bits.
Combining those cuts your strategy down to 192.7+37.2+4+6 bits which is 30 bytes.
The main savings the article has is being smarter about how to store promotions. And then it uses some tricks by swapping pieces to encode extra bits.
(But it turns out that storing which tiles are occupied, then listing each piece in order, works better than encoding locations.)
Heuristic: (65/64)^64 is extremely close to e. This comes from a classic formula for e as the limit of (1+1/n)^n.
Therefore (65/64)^32 is roughly sqrt(e). Since 1 < e < 4, 1 < sqrt(e) < 2. So 65^32 < 2 * 64^32.
Yes, I made a few mistakes and I did realize I didn't need the whole extra bit to store 65 possible locations- I just was being a bit lazy. Ba dum tiss.
Hmm as a bit field followed by piece order- that would be 8 bytes followed by a variable number of pieces, perhaps you could do a sort of compression where 0c means pawn and 1xxxc is any other piece. (c stands for a color bit). So thats another 14 bytes. Thats 22 bytes!
The xxx by the way is one of 8 things: k, k not moved, r, r not moved, n, b, q, en passant pawn
From the previous HN discussion, 00c for pawn and xxxc for other pieces is probably the optimal way to encode pieces into whole bits. Because you can sacrifice 1 pawn to enable 3 promotions, so you need to handle up to 28 non-pawns. With 2/5 you start at 14 bytes but can need up to 17.5. With 3/4 you start at 14 bytes and never need more than 14.
With 6 xxx states instead of 8, you can merge "king not moved", "rook not moved", and "en passant pawn" into a single state since those can never overlap. (Though if you're encoding one pawn the long way that means you need 14.125 bytes, oh well.)
"The 'bit-level magic' here is misleading. They're using integer representations and calling them bits. A true bit-level approach would encode positions as pure binary streams. For example, their promotion string '00000034' is 8 bytes (64 bits), not the claimed 9 bits. Has anyone implemented this with actual bitwise operations instead of integer packing?
TLDR: You stupi...lovely folks, need learn what a bit is. What is a byte, and why integers are NOT BITS.
And no one called this post out from years ago? Crazy.
Someone ask, and I will show you how to do it in 24 BYTES IN BINARY ENCODING FOR REAL - no fake "integers are bits". And can we use compression techniques? We can get this to 10-12 bytes maybe.
So it beats the fake "26 bytes" and my version is actually real binary bits.
Ask.
Your mental model is wrong. Read the post again, slowly, and it will probably make more sense to you. Here are the relevant bits
> This gives us the string `00000034` to uniquely represent this specific set of promotions, without information loss.
> How many possible strings are there? Generating this by brute force, we end up with 495 distinct strings
> This can be stored in 9 bits for each side
Hint: 2^9 is 512 and 512 > 495
You're proving my point. Yes, 495 possibilities CAN be stored in 9 bits. But the article shows STRING '00000034' (64 bits) as an example, not the actual 9-bit binary encoding. That's exactly the problem - claiming bit-level compression while showing byte-level examples.
And if you look at article, nothing is binary encoded, they are all integer representations all the way down.
Please someone show me a BIT implementation of this - THESE ARE BITS 0 1 0 1 1 0 - It's called BINARY. There are no 9, or 5, or 3 or 4.....That isn't how logic gates work.
A 3 / INT is 8 BITS...1 BYTE.
HINT: I'm right.
And you never answered my question:
"Has anyone implemented this with actual bitwise operations instead of integer packing?"
Still waiting to see these "9-bit" "bytes"."00000034".
Again, show me. There is no such thing as a 9-bit byte, that isn't how CPUs or computation work. ITS 8 BITS 1 BYTE, that is transistor / gate design architecture.
This is how computers work.
If you have 9 bits, you have 2 BYTES!!!!!
BYTE 1: 00100011 (8 bits) BYTE 2: 10000000 (9th - 7 wasted bits)
= 16 bits, 2 BYTES THANK YOU GOODBYEEEEEEEEE
Yes 9 bits is 2 bytes. The article confusingly says 18 bits = ~2 bytes. It is the "about 2 bytes" that is confusing. They probably mean that an extra bit won't matter too much since we are bit packing the games in a contiguous stream.
BUT
In the article they don't mean that 00000034 is a bit or a byte. It is one of the possibilities and there are 495 of them and if you index each possibly in a 2 byte integer, you can decode it back to that string and get a representation of the promotions that happened in any game.
You understand me, this is most important. And thank you for explaining this exercise - but to be honest, if the article says "How to store a chess position in 26 bytes"
And you actually cannot store this in 26 bytes based on your implementation, and then you show integer bits and bytes that aren't even binary...eh.
And to be honest, like how about we store the chess position in 1 bit.
I will execute some chess position program in 1 bit, ON / 1. How about that for ultra compression? Lets just pretend those other random bits and bytes don't exist I mean (...but they do...) - it's stored somewhere else, but "HOW TO STORE A CHESS POSITION IN 1 BIT" - but ok, fine I will play "pretend" |How to store a chess position in 26 bytes (2022)|
You know what I mean? lol
Yes I do know what you mean, don't worry. (I'm also an IRC dinosaur)
Very clever, but that's the problem, clever is never the correct solution.
With a few bytes more more you can create an implementation that is a lot easier to understand. Bytes are cheap, developer time isn't.
"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something."
https://news.ycombinator.com/newsguidelines.html
I'd especially hammer the point in this case, because clever hacks are very much on topic for Hacker News. They are, in fact, what gave birth to the word hacker and the idea of hacking in the first place. Not only that but it was precisely the clever hacks with no particular utility that were prized most highly!
If you are writing a chess engine you'll want to store hundreds of millions of positions while you search for the best move and at that scale a byte is important because it gets multiplied by an enormous factor.
But that is a totally different problem which requires far fewer bytes to represent. For that problem you are just considering of the valid pieces which made a move and what board that came from. Storing a single move is far cheaper than an entire board state.
Not when you include transpositions, where you arrive at the same position from a different move order, in which case saving board states instead of moves could be very valuable.
There are transposition tables for that though. They don't store the board state actually. For Stockfish, transposition table entries are 10 bytes each, 16 bits of which are the low bits(or high? Can't remember) of a zobrist hash of the board state. The other 48 bits of the hash are used for addressing into the hash table, but aren't stored in it. The rest of the entry will be stuff like the best move found during the previous search(16 bits), the depth of that search(8 bits), evaluation(2 different ones at 16 bits each), and various bits of data like node type and age of the entry(for deciding which entry to replace, because this table is always full). Collisions can occasionally happen, but saving a full board state to eliminate them would cost far too much, since no matter how big you make the table, it'll never be big enough to cache all the board states a search visits.
In Stockfish, there will only be one full-fledged board state in memory per search thread. So the size of the board state is pretty much irrelevant to performance. What's important is reducing the overhead of generating possible moves, applying those moves to the board state, and hashing the board state, which is what magic bitboards are for.
That's interesting, I didn't know about transposition tables, thanks for the explanation!
If they cared about that, then it wouldn't have been written in python. This is an exercise of the author showing how clever they are.
This is pretty standard ( or at least used to be 20 years ago ) in high performance chess programming, see
https://www.chessprogramming.org/Bitboards
https://healeycodes.com/visualizing-chess-bitboards