hashtables

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Daniel Shawul
Posts: 3868
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: hashtables

Post by Daniel Shawul » Wed Oct 16, 2013 1:58 am

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
Posts: 33
Joined: Wed Aug 14, 2013 5:23 pm

Re: hashtables

Post by rtitle » Wed Oct 16, 2013 2:59 pm

> 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
Posts: 136
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: hashtables

Post by Pio » Wed Oct 16, 2013 4:34 pm

rtitle wrote:> 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
Posts: 33
Joined: Wed Aug 14, 2013 5:23 pm

Re: hashtables

Post by rtitle » Wed Oct 16, 2013 10:12 pm

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

Post Reply