bit hashing algorithms

[Don]

I'm looking for a good hashing algorithm for bit boards. I've read up on magic bitboards and such, but I'm looking for something more generally applicable.

Suppose you have up to N bitboards and want to very quickly compute a hash from it? Are there any methods in general usage?

I'm thinking in terms of evaluation features that require substantial calculation, but may be relatively common enough so that memoization could be used, similar to pawn structure hashing. An example might be a really sophisticated pawn shelter algorithm that is slow and expensive to compute and so you would not want to compute the same one over and over. I might have more of these than I am willing to build zobrist keys for. (For this particular example, it's probably good enough to use the zobrist pawn key for just this color, but it's just an example to illustrate why I might need to do this.)

What seems like a reasonable one is to add and multiply these boards together in some combination that doesn't hurt processor scheduling too much.

[Zach Wegner]

I'm looking for a good hashing algorithm for bit boards. I've read up on magic bitboards and such, but I'm looking for something more generally applicable.

Suppose you have up to N bitboards and want to very quickly compute a hash from it? Are there any methods in general usage?

I'm thinking in terms of evaluation features that require substantial calculation, but may be relatively common enough so that memoization could be used, similar to pawn structure hashing. An example might be a really sophisticated pawn shelter algorithm that is slow and expensive to compute and so you would not want to compute the same one over and over. I might have more of these than I am willing to build zobrist keys for. (For this particular example, it's probably good enough to use the zobrist pawn key for just this color, but it's just an example to illustrate why I might need to do this.)

What seems like a reasonable one is to add and multiply these boards together in some combination that doesn't hurt processor scheduling too much.

Very interesting question. I think hashing bit patterns in the eval has a lot of potential. Maybe small patterns independent of position, suitable for a pattern database?

It seems that this problem is best suited to something magic-like, more like a DeBruijn. You aren't going to get a perfect hash, but you need something like zobrist that gives a good distribution over the index bits, but is quick to compute. I'd say to try a basic DeBruijn, simply because the bit patterns are different for each bit position. You can then pull something like 10 bits off for the index. For multiple bitboards, use a different DeBruijn for each one and XOR the results.