How to store a chess position in 26 bytes (2022)

https://ezzeriesa.notion.site/How-to-store-a-chess-position-in-26-bytes-using-bit-level-magic-df1fdb5364eb42fdac11eb23b25e9605

by kurinikku • 6 months ago

138 101 6 months ago

ezzeriesa.notion.site

pklausler3• 6 months ago

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.

tromp5• 6 months ago

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• 6 months ago

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

pklausler3• 6 months ago

Yes, that number just can't be right; thank you for the check.

eulgro• 6 months ago

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• 6 months ago

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

bombcar2• 6 months ago

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.

herodoturtle• 6 months ago

Previously discussed (2022):

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

not_the_fda2• 6 months ago

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• 6 months ago

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.

jmward013• 6 months ago

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_the_fda2• 6 months ago

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• 6 months ago

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

dang• 6 months ago

"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!

jmward013• 6 months ago

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

klaff• 6 months ago

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.

jmward013• 6 months ago

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• 6 months ago

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.

bonzini4• 6 months ago

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.

toast02• 6 months ago

Should be able to shave 4 bits, cause there's four bishops?

bonzini4• 6 months ago

Doh of course. But the 26 bytes + 2 bits irritated me so I didn't think about it.

btilly• 6 months ago

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• 6 months ago

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• 6 months ago

You may even need envelope encryption for the currently unrevealed post-adjournment move.

bobmcnamara2• 6 months ago

Problem need to include the year in the encoding then

tromp5• 6 months ago

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• 6 months ago

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.

nurettin4• 6 months ago

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!

kibwen• 6 months ago

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

4rt2• 6 months ago

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?

vntok4• 6 months ago

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.

4rt2• 6 months ago

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.

efitz2• 6 months ago

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

vntok4• 6 months ago

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.

tromp5• 6 months ago

To make this work, the rook can only have the king's position, if neither the king nor that rook have moved.

cestith• 6 months ago

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.

bobmcnamara2• 6 months ago

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)

nvader• 6 months ago

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.

jcalvinowens• 6 months ago

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.

mrweasel• 6 months ago

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.

arnsholt• 6 months ago

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

bonzini4• 6 months ago

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.

datsci_est_2015• 6 months ago

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.

Smalltalker-802• 6 months ago

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• 6 months ago

+ 3 bits for piece type?

addaon• 6 months ago

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.

Scarblac4• 6 months ago

Each side has 16 pieces, so you need 32 elements.

Smalltalker-802• 6 months ago

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

fallingfrog4• 6 months ago

In my head I count 30 bytes, since all 16 pawns can be underpromoted to a bishop rook or knight.

Dylan168074• 6 months ago

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.

fallingfrog4• 6 months ago

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!

Scarblac4• 6 months ago

I think didn't mention the bit for whose move it is? Luckily, he has a few spare bits.

010920263• 6 months ago

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

vntok4• 6 months ago

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

010920263• 6 months ago

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

billforsternz• 6 months ago

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• 6 months ago

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• 6 months ago

The king can't be captured, so the capture bit for the kings can be used for something else.

kazinator3• 6 months ago

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.

kazinator3• 6 months ago

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.

kazinator3• 6 months ago

* en passant

jfaat• 6 months ago

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

jstanley2• 6 months ago

Since each position takes up 6 bits ($2^6 = 64$), multiplying 6 bits by 32 pieces gives us 192 bits / 24 bytes (1 byte = 8 bits).

But each position can only be used once, so you really only have 64*63*62*61*...*33 possibilities = 64!/32! = ~2^53, so you could encode this with less than 7 bytes, and then use the basic 12-byte encoding for captures, castling, en-passant, and promotions, and you are below 19 bytes in total. (Did I miscalculate this?)

Also pawns can never be on the 1st or 8th rank so you can subtract those possibilities from each of the numbers that represents a pawn.

You also don't care about the order of bishops, rooks, knights, and especially pawns - so you should be able to do even better.

tromp5• 6 months ago

Multiplying 32 numbers each over 5 bits long obviously results in more than 160 bits. 64!/32! > 2^178.3

jstanley2• 6 months ago

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

bonzini4• 6 months ago

(Former) pawns can be on the 1st or 8th rank if they've been promoted. You can place an unpromoted pawn on the 1st or 8th rank to encode en passant, too.

Also castling can be encoded as extra squares available to the rooks only ("queen side never moved" and "king side never moved"), and that is almost free.

But without a good encoding for promotions, I doubt you can beat the encoding of the article.

leothetechguy• 6 months ago

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

mrpopo• 6 months ago

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

jonsoft4• 6 months ago

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!

gus_massa2• 6 months ago

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.

jonsoft4• 6 months ago

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?

tromp5• 6 months ago

Among 4 pawns like white and black a&b pawns, you only need 1 pawn capture to allow the other 3 pawns to promote.

NooneAtAll32• 6 months ago

what's wrong with scrolling on that blog? arrow keys don't work

undeveloper• 6 months ago

notion

NooneAtAll32• 6 months ago

How to store a chess position in 26 bytes (2022)

Related Stories