Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

ezzeriesa.notion.site

Post reply on HN
Print view View original

61–70 of 108 posts

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

#61

Post by Someone »

jmward01 wrote: post #5

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…

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

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

#62

Post by bonzini »

toast0 wrote: post #21
bonzini wrote: post #11

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.

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

#63

Post by pklausler »

mlyle wrote: post #47
wongarsu wrote: post #17

Earlier quoted context omitted.

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.

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

#64

Post by KK7NIL »

mtlmtlmtlmtl wrote: post #40
KK7NIL wrote: post #27

Earlier quoted context omitted.

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 th…

That's interesting, I didn't know about transposition tables, thanks for the explanation!

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

#65

Post by bombcar »

mlyle wrote: post #53
bombcar wrote: post #32

Earlier quoted context omitted.

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.

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

#66

Post by bonzini »

arnsholt wrote: post #34

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

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

#68

Post by fallingfrog »

Dylan16807 wrote: post #55
fallingfrog wrote: post #41

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!

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

#69

Post by dang »

not_the_fda wrote: post #4

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!

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

#70

Post by Dylan16807 »

fallingfrog wrote: post #68
Dylan16807 wrote: post #55

Earlier quoted context omitted.

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…

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

Post reply on HN