0

I'm writing a chess engine in Java, and I'm having difficulty understanding how to calculate the hash address/index, based on the zobrist key.

According to the Chess Programming Wiki, since the 64-bit zobrist is too large to use as the index itself, "to calculate the address or index requires signature modulo number of entries, for power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly."

My current implementation looks like this:

private int getIndex(long zobristKey) {
    return (int) Math.abs(zobristKey % TABLE_SIZE);
}

I need to use Math.abs, because otherwise half of the resulting numbers are negative, and therefore not suitable as an index.

The problem I have is that this current implementation generates thousands of collisions per search, and I can't work out why. It might be because the value is not 'masked by an and-instruction' as the CPW says, but I'm not sure what value I am supposed to be and-ing my key with.

Does anyone spot an error in my implementation, or else can fill the gap in my understanding?

Improve this question
2
  • You probably add some information on your expectations. All hashes (or practically all of them) produce collisions. The programmer has to cope with that. So: how many collisions did you expect to see, and what secondary access scheme (if any) are you using for that (such as bucket searching. And just what is your TABLE_SIZE? Your question is a question of hashing, not chess, so you may get better replies in other forums more targeted to searching algorithms. (Unless zobristkey is well-behaved, retaining just the lower bits is a common error in other situations. What are your unit tests? )
    – user30536
    Nov 15 at 17:26
  • The index calculation itself looks fine to me. But indeed, more information is needed. What is the table size, how many entries do you put in the table? How exactly do you calculate your Zobrist keys?
    – koedem
    Nov 16 at 12:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.