Beginning hashtable question.

[Fguy64]

OK, my positional representation is a string, 76 characters long. 0-63 is the position, and the rest is game state variables.

My program is written in Sun java. Java has a built in HashTable class, which would require that I use the built in HashCode function of the String class. This hash code function is defined as follows...

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

I was wondering if someonce could speak to the suitabilty of using this function for a chess Hash Table. It's not a show stopper, I can easily adapt, but a built in function would be nice, as long as there is problems with clustering and collisions.

Thanks.

[Fguy64]

OK, never mind that question, I'll stick with the recommended zobrist key.

At this point I'm a little unclear on capacity, but I'll give myself some time to figure that one out.

[bob]

OK, my positional representation is a string, 76 characters long. 0-63 is the position, and the rest is game state variables.

My program is written in Sun java. Java has a built in HashTable class, which would require that I use the built in HashCode function of the String class. This hash code function is defined as follows...

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

I was wondering if someonce could speak to the suitabilty of using this function for a chess Hash Table. It's not a show stopper, I can easily adapt, but a built in function would be nice, as long as there is problems with clustering and collisions.

Thanks.

Terrible idea. First the function is not very good for chess, since empty squares are 3x more common than occupied squares. Second, this is hugely expensive compared to an incremental Zobrist hash signature. But the main problem is the hashing algorithm that weights empty squares 3x (or more) over occupied squares.

[Fguy64]

OK, my positional representation is a string, 76 characters long. 0-63 is the position, and the rest is game state variables.

My program is written in Sun java. Java has a built in HashTable class, which would require that I use the built in HashCode function of the String class. This hash code function is defined as follows...

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

I was wondering if someonce could speak to the suitabilty of using this function for a chess Hash Table. It's not a show stopper, I can easily adapt, but a built in function would be nice, as long as there is problems with clustering and collisions.

Thanks.

Terrible idea. First the function is not very good for chess, since empty squares are 3x more common than occupied squares. Second, this is hugely expensive compared to an incremental Zobrist hash signature. But the main problem is the hashing algorithm that weights empty squares 3x (or more) over occupied squares.

OK thanks, I figured there had to be a reason. Now if I can only manage to write my hashing code without being tempted to change to a bitboard implementation

[Fguy64]

OK I just wanted to bounce my zobrist stratgey off the board. I think I have it covered.

my position reprentation, for better or worse, is the following string. I don't wanna mess with it right now if I can help it. Although I am certainly beginning to see that there may some serious room for improvement here.

Code: Select all

field	description
0-63	Board position. Upper case white, lower case black. Empty square is '1'.
64	 	Side to move. 'w' or 'b'.
65-68	Castling rights - '1' or '0'
69-70	en passant target square, in integer notation
71-72	half move clock maximum value "99".
73-75	move number, maximum value "999", so keep your games short.

My hash entry will be based on piece position, side to move, castling, eptarget.
I'm not gonna concern myself with 50 move or threefold repetition or anything else right now

so I need the following 64 bit random constants...

A constant to seed my Random number generator.

a 12x64 array of constants to represent all possible piece positions
one constant for side to move.
one contstant for each of the 4 castling rights
16 constants for each of the enPassant Target Squares

so my hash key will be built as follows...

set zKey to 0L

loop through the first 64 characters, XOR zKey with the appropriate piece/square entry from my array
if white to play, XOR with side to move constant, if black to move do nothing
for each of four castling fields, XOR with zkey if value is 1 (can castle)
if ep target is non-zero XOR with one of 14 epTarget constants.

How my actual Transposition table is gonna be laid out I have yet to decide.

[Greg Strong]

This works but it's expensive to loop through the 64 squares xor-ing in appropriate hashes. The beauty of the zobrist hash scheme is that you can maintain it incrementally (at least the piece-on-square portion.) When you move a piece off a square, xor that piece-square-key to remove it. When you place a piece on a square, xor that new piece-square-key. Then, when you need your actual position hashcode, just take the incrementally-maintained key and xor in the appropriate side-to-move, castling rights, and ep square keys.

You can also test this scheme by performing your original loop-through-squares approach and compare that result to make sure that your incrementially maintained key approach is correct.

[Fguy64]

Thanks Gregory, your answer is pretty much what I expected. As long as it works. I'm kind of reaching the end of the first real chess program I've written, it started a couple years ago based on fen strings. Once the hash table is working I'll have alphabeta and Q and iterative deepening and hashing and some piece square tables. Then I start the rewrite beginning probably with bitboards. And I'll be paying close attention to the business of maintaining the hashcode incrementally, like you have mentioned.

[Fguy64]

This works but it's expensive to loop through the 64 squares xor-ing in appropriate hashes. The beauty of the zobrist hash scheme is that you can maintain it incrementally (at least the piece-on-square portion.) When you move a piece off a square, xor that piece-square-key to remove it. When you place a piece on a square, xor that new piece-square-key. Then, when you need your actual position hashcode, just take the incrementally-maintained key and xor in the appropriate side-to-move, castling rights, and ep square keys.

You can also test this scheme by performing your original loop-through-squares approach and compare that result to make sure that your incrementially maintained key approach is correct.

You know, this observation is probably either obviously right or obviously wrong, but..., I haven't seen it answered clearly in the literature. I can more or less understand how zobrist keys can be used to represent a position for the purposes of comparison, but as far as I can see, it is not used for purposes of move generation, or positional representation for the purposes of keeping track of the actual game, or for displaying the position graphically. That is the role of the board representation, and there really is no direct connection with a bitboard representation and a zobrist key, any more than there is a link with any other kind of board representation.

[tvrzsky]

You know, this observation is probably either obviously right or obviously wrong, but..., I haven't seen it answered clearly in the literature. I can more or less understand how zobrist keys can be used to represent a position for the purposes of comparison, but as far as I can see, it is not used for purposes of move generation, or positional representation for the purposes of keeping track of the actual game, or for displaying the position graphically. That is the role of the board representation, and there really is no direct connection with a bitboard representation and a zobrist key, any more than there is a link with any other kind of board representation.

Of course, this is the very nature of hashing: once you hash your position to the zobrist number then there is no way to get the position back. The zobrist number does not contain any information about the position, so it can not be used any other way than as an index to a hashtable or for the purposes of comparison.

[Fguy64]

You know, this observation is probably either obviously right or obviously wrong, but..., I haven't seen it answered clearly in the literature. I can more or less understand how zobrist keys can be used to represent a position for the purposes of comparison, but as far as I can see, it is not used for purposes of move generation, or positional representation for the purposes of keeping track of the actual game, or for displaying the position graphically. That is the role of the board representation, and there really is no direct connection with a bitboard representation and a zobrist key, any more than there is a link with any other kind of board representation.

Of course, this is the very nature of hashing: once you hash your position to the zobrist number then there is no way to get the position back. The zobrist number does not contain any information about the position, so it can not be used any other way than as an index to a hashtable or for the purposes of comparison.

That's exactly what I was wondering. You'd think the authors would put that in bold print, but I guess not. I figured it was a simple matter of... ah never mind

Thanks, much appreciated, that clears up a big question mark for me.