On-the fly hash key generation?

[hgm]

A suitable quantitative measure of the quality of a set of keys could be the number of 6-key dependencies you could detect on several (randomly picked, but then kept fixed) subsets of the bits, chosen to have sufficiently few bits that you actually expect a fair number of such dependencies.

The 6-key dependencies are efficiently detected by storing all combinations of 3 different keys in a hash table. If two combinations map to the same entry, you found a 6-key dependency. For a set of 800 keys there are 800^3/6! = 21M 3-key combinations (170MB). According to the birthday paradox that makes 220e12 collision attempts. So you should start to see collisions when you consider 48-bit sub-sets of the key, and get a fair number when you consider 44-bit subsets.

[mar]

n << sq | n >> (64-sq);

That's an awesome idea!
Rotations will be folded into just one instruction on x64, cutting down memory requirement to practically a negligible amount (nearly by a factor of 64).
Does it work well in your engine compared to traditional full tables?
I can imagine it might work very well.

[Aleks Peshkov]

n << sq | n >> (64-sq);

That's an awesome idea!
Rotations will be folded into just one instruction on x64, cutting down memory requirement to practically a negligible amount (nearly by a factor of 64).
Does it work well in your engine compared to traditional full tables?
I can imagine it might work very well.

We are talking about micro-optimizations. I could not measure the speed difference between rotation and full table version.

I wanted to skip random factor from Zobrist keys and hoped to find better keys. The set of just 7 numbers is much easier to optimize.

[Aleks Peshkov]

A suitable quantitative measure of the quality of a set of keys could be the number of 6-key dependencies you could detect on several (randomly picked, but then kept fixed) subsets of the bits, chosen to have sufficiently few bits that you actually expect a fair number of such dependencies.

The 6-key dependencies are efficiently detected by storing all combinations of 3 different keys in a hash table. If two combinations map to the same entry, you found a 6-key dependency. For a set of 800 keys there are 800^3/6! = 21M 3-key combinations (170MB). According to the birthday paradox that makes 220e12 collision attempts. So you should start to see collisions when you consider 48-bit sub-sets of the key, and get a fair number when you consider 44-bit subsets.

I do not understand what should I do and what to do with the result.

I am optimizing chess space, so some key combinations are impossible or very rare in practice. For example, there only 2 kings in the chess game, on most of time the are always on home ranks. Collisions with castling keys are less important because they can happen only between positions before and after castling move and so on.

For example I have read here that 5 average 4-key 32-bit dependencies is normal for random set. My way of generation keys would mean either none or millions of such collisions would happen for such condition. So I should create a set without 32-bit collisions, but what to do after that? I can try to test 5-key sets, but I am not sure that 0 collisions is theoretically possible for 32-bit subkey. And if it is not possible for full space, probably it is possible to do in chess subspace...

[AlvaroBegue]

For example I have read here that 5 average 4-key 32-bit dependencies is normal for random set. My way of generation keys would mean either none or millions of such collisions would happen for such condition. So I should create a set without 32-bit collisions, but what to do after that? I can try to test 5-key sets, but I am not sure that 0 collisions is theoretically possible for 32-bit subkey. And if it is not possible for full space, probably it is possible to do in chess subspace...

To be clear, I only looked at this 4-key collision number as simple detector of glaring defects in a hashing scheme.

I wanted to skip random factor from Zobrist keys and hoped to find better keys. The set of just 7 numbers is much easier to optimize.

You can use full-size tables and initialize them with this procedure:

Code: Select all

  u64 h = 1;
  for &#40;int i = 0; i < 64*12; ++i&#41; &#123;
    zobrist_table&#91;i&#93; = h;
    h <<= 1;
    if &#40;h >> 63&#41;
      h ^= 0x42F0E1EBA9EA3693ull;
  &#125;

The resulting Zobrist key is actually a 64-bit CRC (the constant came from https://en.wikipedia.org/wiki/Cyclic_redundancy_check) of the bitboard representation of the position. Positions that are nearby in the tree would differ in few bits, and that's precisely what CRC is good at detecting. I expect this is about the best you can do. If you have a framework to compare hash functions in a chess engine, I would love to hear how well it fares.

NOTE: I would probably use a random constant as initial value for h instead of 1, to avoid some unfortunate properties of taking a subset of the bits (for instance to compute an entry in the hash table).