[HN Gopher] How to store a chess position in 26 bytes (2022)
___________________________________________________________________
How to store a chess position in 26 bytes (2022)
Author : kurinikku
Score : 71 points
Date : 2026-01-09 15:07 UTC (7 hours ago)
(HTM) web link (ezzeriesa.notion.site)
(TXT) w3m dump (ezzeriesa.notion.site)
| pklausler wrote:
| 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.
| tromp wrote:
| 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
| gowld wrote:
| "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.
| pklausler wrote:
| Yes, that number just can't be right; thank you for the
| check.
| eulgro wrote:
| 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.
| wongarsu wrote:
| 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
| mlyle wrote:
| 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.
| pklausler wrote:
| The duplication is the problem if you want to use
| positions as DB keys.
| bombcar wrote:
| 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.
| NitpickLawyer wrote:
| Not what you asked for, sorry, but it reminded me of this
| gem - https://www.youtube.com/watch?v=C5JVFCouXIU
| mlyle wrote:
| Obviously not possible -- how would pawns pass each other
| without captures?
| bombcar wrote:
| Ah! True, I worked out how you could have OTHER pieces
| get around a pawn, but pawns themselves can't get past
| each other.
| herodoturtle wrote:
| Previously discussed (2022):
|
| https://news.ycombinator.com/item?id=37525348
| not_the_fda wrote:
| 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.
| SkiFire13 wrote:
| 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.
| jmward01 wrote:
| 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.
| KK7NIL wrote:
| 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.
| mtlmtlmtlmtl wrote:
| 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.
| KK7NIL wrote:
| That's interesting, I didn't know about transposition
| tables, thanks for the explanation!
| not_the_fda wrote:
| 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.
| Agingcoder wrote:
| 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
| jmward01 wrote:
| 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.113761393x1062 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...
| klaff wrote:
| 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.
| jmward01 wrote:
| 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'.
| Someone wrote:
| > 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.
| bonzini wrote:
| 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.
| toast0 wrote:
| Should be able to shave 4 bits, cause there's four bishops?
| bonzini wrote:
| Doh of course. But the 26 bytes + 2 bits irritated me so I
| didn't think about it.
| btilly wrote:
| 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.
| jmole wrote:
| 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.
| inopinatus wrote:
| You may even need envelope encryption for the currently
| unrevealed post-adjournment move.
| bobmcnamara wrote:
| Problem need to include the year in the encoding then
| tromp wrote:
| > 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...
| tucnak wrote:
| 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.
| kibwen wrote:
| 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...
| 4rt wrote:
| 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?
| vntok wrote:
| 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.
| 4rt wrote:
| 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.
| Scarblac wrote:
| 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.
| Dylan16807 wrote:
| 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).
| efitz wrote:
| 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".
| vntok wrote:
| 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.
| tromp wrote:
| To make this work, the rook can only have the king's
| position, if neither the king nor that rook have moved.
| efitz wrote:
| How do you differentiate between "never moved" and "moved
| but moved back"?
| vntok wrote:
| 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).
| cestith wrote:
| 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.
| bobmcnamara wrote:
| 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)
| jcalvinowens wrote:
| 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.
| arnsholt wrote:
| 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...
| bonzini wrote:
| 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.
| Smalltalker-80 wrote:
| 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)
| veidelis wrote:
| + 3 bits for piece type?
| addaon wrote:
| 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.
| Scarblac wrote:
| Two bits on the king for castling, queenside and kingside.
| Scarblac wrote:
| Each side has 16 pieces, so you need 32 elements.
| Smalltalker-80 wrote:
| 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...
| fallingfrog wrote:
| In my head I count 30 bytes, since all 16 pawns can be
| underpromoted to a bishop rook or knight.
| Dylan16807 wrote:
| 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.
| Scarblac wrote:
| I think didn't mention the bit for whose move it is? Luckily, he
| has a few spare bits.
| 01092026 wrote:
| "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.
| vntok wrote:
| 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
| billforsternz wrote:
| 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.
| untech wrote:
| 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.
| RiverCrochet wrote:
| The king can't be captured, so the capture bit for the kings can
| be used for something else.
___________________________________________________________________
(page generated 2026-01-09 23:01 UTC)