hashtables
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 Posts: 3868
 Joined: Tue Mar 14, 2006 10:34 am
 Location: Ethiopia
 Contact:
Re: hashtables
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.
Re: hashtables
> Another fun problem is what is the most compact representation for storing chess positions?
You can do it with four 64bit words (32 bytes). Choosing the Nth bit of each word gives you a 4bit 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 enpassant possibilities and castling rights.
Probably could be squeezed smaller, but I like nice round powerof2 numbers.
You can do it with four 64bit words (32 bytes). Choosing the Nth bit of each word gives you a 4bit 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 enpassant possibilities and castling rights.
Probably could be squeezed smaller, but I like nice round powerof2 numbers.
Re: hashtables
Hi Richard!rtitle wrote:> Another fun problem is what is the most compact representation for storing chess positions?
You can do it with four 64bit words (32 bytes). Choosing the Nth bit of each word gives you a 4bit 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 enpassant possibilities and castling rights.
Probably could be squeezed smaller, but I like nice round powerof2 numbers.
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 enpassant". By saving enpassant 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
Re: hashtables
Hi Pio,
That's quite clever and compact . So, the rooks that can castle get the artificial piece type for cancastle, 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 64bit 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 (64N) 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
That's quite clever and compact . So, the rooks that can castle get the artificial piece type for cancastle, 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 64bit 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 (64N) 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