hashtables

[Daniel Shawul]

Yes I think this topic has been brought up here before for a topic I can't recall now, may be egtb compression. As you said, saving the index of a sorted move list will increase redundancy that will be much better suited for huffman coding. The first and second move will take one bit to represent 0/1 in the cannonical huffman, so that should result in an order of magnitude compression.

[rtitle]

> Another fun problem is what is the most compact representation for storing chess positions?

You can do it with four 64-bit words (32 bytes). Choosing the Nth bit of each word gives you a 4-bit value that can be used to encode what (if any) piece is on the Nth square. There are 13 possibilities for that {WK, BK, WQ, BQ, ..., (empty)} so that leaves some spare room in the "illegal" bit combinations to encode extra information like en-passant possibilities and castling rights.

Probably could be squeezed smaller, but I like nice round power-of-2 numbers.

[Pio]

> Another fun problem is what is the most compact representation for storing chess positions?

You can do it with four 64-bit words (32 bytes). Choosing the Nth bit of each word gives you a 4-bit value that can be used to encode what (if any) piece is on the Nth square. There are 13 possibilities for that {WK, BK, WQ, BQ, ..., (empty)} so that leaves some spare room in the "illegal" bit combinations to encode extra information like en-passant possibilities and castling rights.

Probably could be squeezed smaller, but I like nice round power-of-2 numbers.

Hi Richard!

I store my chess positions in three 64 bit words. I manage to do that by saving all the piece occupied squares in 64 bits. In the next 32 bits I save which of the occupied squares that contain the side to move pieces by setting them to ones (and the other side pieces to zero) by going through the board in a predefined order. The next 3*32 bits are used to save the information about each piece and since I already know each piece's side to move I can use 3 bits to save the piece type information as pawns, knights, bishops, rooks, kings, queens, "artificial piece type rockad", "artificial piece type en-passant". By saving en-passant information and rockad information as piece types I do not waste any space in the three bits for each piece.

And as you wanted you get the representation in a nice round power of two

[rtitle]

Hi Pio,

That's quite clever and compact . So, the rooks that can castle get the artificial piece type for can-castle, right? And for en passant, which pawn gets the artificial piece type, the capturing pawn or the captured pawn (or both)?

While your compact position representation is nice, it's not really necessary in a chess engine, right? Anywhere you compute and store a compact position representation, you could equally well store the 64-bit Zobrist hash for the position (or any other "good" hash), assuming your Zobrist hash somehow takes into account e.p. possibilities and castling rights. In fact if you're using the first N bits of the Zobrist hash as the index into your TT table, you only need to store the remaining (64-N) bits inside the TT entries. Statistically, this is likely enough to detect collisions so that you don't need to also store a complete position representation.

Rich