Hash idea

[jwes]

If you change the hashing for side to move to ensure that positions that differ only in side to move are hashed to the same bucket, it should make your program somewhat faster. The idea behind this is that when searching, you check the hash table, and then try null move, which then checks the hash table for the same position with the other side to move. This change will avoid many cache misses. It helps 1-2% with crafty though I would guess it will help much more with programs that check hash in qsearch.

[bob]

If you change the hashing for side to move to ensure that positions that differ only in side to move are hashed to the same bucket, it should make your program somewhat faster. The idea behind this is that when searching, you check the hash table, and then try null move, which then checks the hash table for the same position with the other side to move. This change will avoid many cache misses. It helps 1-2% with crafty though I would guess it will help much more with programs that check hash in qsearch.

I assume you are just hashing on original hash signature, but then key-matching using the signature after complementing based on wtm???

[jwes]

If you change the hashing for side to move to ensure that positions that differ only in side to move are hashed to the same bucket, it should make your program somewhat faster. The idea behind this is that when searching, you check the hash table, and then try null move, which then checks the hash table for the same position with the other side to move. This change will avoid many cache misses. It helps 1-2% with crafty though I would guess it will help much more with programs that check hash in qsearch.

I assume you are just hashing on original hash signature, but then key-matching using the signature after complementing based on wtm???

What I did was change from

Code: Select all

temp_hashkey = (wtm) ? HashKey : ~HashKey;

to

Code: Select all

temp_hashkey = (wtm) ? HashKey : HashKey ^ ~hash_mask;

or the equivalent everywhere the hash table is accessed.

[hgm]

I thought everyone did this. Just make sure all the bits from which you derive the index in the stm Zobrist key are zero. This is how I have always done it in Joker.

[bob]

If you change the hashing for side to move to ensure that positions that differ only in side to move are hashed to the same bucket, it should make your program somewhat faster. The idea behind this is that when searching, you check the hash table, and then try null move, which then checks the hash table for the same position with the other side to move. This change will avoid many cache misses. It helps 1-2% with crafty though I would guess it will help much more with programs that check hash in qsearch.

I assume you are just hashing on original hash signature, but then key-matching using the signature after complementing based on wtm???

What I did was change from

Code: Select all

temp_hashkey = (wtm) ? HashKey : ~HashKey;

to

Code: Select all

temp_hashkey = (wtm) ? HashKey : HashKey ^ ~hash_mask;

or the equivalent everywhere the hash table is accessed.

I tested this. I didn't particularly like the idea because one wants to avoid "clustering" in a hash algorithm, yet this is intended to do exactly that. Crafty-23.4R01 uses the change you suggested:

Code: Select all

   Crafty-23.4-2        2674    3    3 30000   66%  2552   22%
   Crafty-23.4-1        2671    3    3 30000   65%  2552   22%
   Crafty-23.4R01-1     2670    3    3 30000   65%  2552   22%
   Crafty-23.4R01-2     2669    3    3 30000   65%  2552   23%
   Crafty-23.3-1        2668    3    3 30000   65%  2552   22%
   Crafty-23.3-2        2666    3    3 30000   65%  2552   22%
   Crafty-23.2-1        2614    3    3 30000   58%  2552   22%
   Crafty-23.2-2        2613    3    3 30000   58%  2552   22%
   Crafty-23.1-2        2594    3    3 30000   55%  2552   23%
   Crafty-23.1-1        2592    3    3 30000   55%  2552   22%
   Crafty-23.0-2        2504    3    3 30000   44%  2552   20%
   Crafty-23.0-1        2503    3    3 30000   44%  2552   20%

More games are needed to absolutely state this is worse, but looking at the results above, there is a hint that it hurts a bit.

I am not sure how this is supposed to help, other than to (as one example) make the position before a null-move hash to the same "bucket" as the position after a null-move. For other examples, I see no reason to want wtm/btm positions to hash to the same bucket as that just forces crowding even in a sparsely filled table.

Why would it be useful to have both positions (wtm and btm) close together? If the null-move search gets a hit, we won't need the other side-to-move position. If the null-move search gets a hit, but the bound doesn't let us stop the search, why would the position at the next node be any different? Yes, you would get that second hit one cache miss faster, but I am not convinced it helps anything overall, based on the above test... Comparing NPS is not helpful here, as it does change the node counts as well due to different overwrite patterns.

[jwes]

If you change the hashing for side to move to ensure that positions that differ only in side to move are hashed to the same bucket, it should make your program somewhat faster. The idea behind this is that when searching, you check the hash table, and then try null move, which then checks the hash table for the same position with the other side to move. This change will avoid many cache misses. It helps 1-2% with crafty though I would guess it will help much more with programs that check hash in qsearch.

I assume you are just hashing on original hash signature, but then key-matching using the signature after complementing based on wtm???

What I did was change from

Code: Select all

temp_hashkey = (wtm) ? HashKey : ~HashKey;

to

Code: Select all

temp_hashkey = (wtm) ? HashKey : HashKey ^ ~hash_mask;

or the equivalent everywhere the hash table is accessed.

I tested this. I didn't particularly like the idea because one wants to avoid "clustering" in a hash algorithm, yet this is intended to do exactly that. Crafty-23.4R01 uses the change you suggested:

Code: Select all

   Crafty-23.4-2        2674    3    3 30000   66%  2552   22%
   Crafty-23.4-1        2671    3    3 30000   65%  2552   22%
   Crafty-23.4R01-1     2670    3    3 30000   65%  2552   22%
   Crafty-23.4R01-2     2669    3    3 30000   65%  2552   23%
   Crafty-23.3-1        2668    3    3 30000   65%  2552   22%
   Crafty-23.3-2        2666    3    3 30000   65%  2552   22%
   Crafty-23.2-1        2614    3    3 30000   58%  2552   22%
   Crafty-23.2-2        2613    3    3 30000   58%  2552   22%
   Crafty-23.1-2        2594    3    3 30000   55%  2552   23%
   Crafty-23.1-1        2592    3    3 30000   55%  2552   22%
   Crafty-23.0-2        2504    3    3 30000   44%  2552   20%
   Crafty-23.0-1        2503    3    3 30000   44%  2552   20%

More games are needed to absolutely state this is worse, but looking at the results above, there is a hint that it hurts a bit.

I am not sure how this is supposed to help, other than to (as one example) make the position before a null-move hash to the same "bucket" as the position after a null-move. For other examples, I see no reason to want wtm/btm positions to hash to the same bucket as that just forces crowding even in a sparsely filled table.

Why would it be useful to have both positions (wtm and btm) close together? If the null-move search gets a hit, we won't need the other side-to-move position. If the null-move search gets a hit, but the bound doesn't let us stop the search, why would the position at the next node be any different? Yes, you would get that second hit one cache miss faster, but I am not convinced it helps anything overall, based on the above test... Comparing NPS is not helpful here, as it does change the node counts as well due to different overwrite patterns.

The entire point is to avoid that 1 cache miss. On my old, slow machine, Crafty appears to spend almost 5% of its time on hash table cache misses, so avoiding cache misses seems worthwhile. Programs that use hash in qsearch could gain much more as >80% of null move searches go directly to qsearch.

[Chan Rasjid]

The entire point is to avoid that 1 cache miss. On my old, slow machine, Crafty appears to spend almost 5% of its time on hash table cache misses, so avoiding cache misses seems worthwhile. Programs that use hash in qsearch could gain much more as >80% of null move searches go directly to qsearch.

But is it recommended to have null move going directly (and blindly) to qsearch. Seems bad.

Rasjid.

[bob]

The entire point is to avoid that 1 cache miss. On my old, slow machine, Crafty appears to spend almost 5% of its time on hash table cache misses, so avoiding cache misses seems worthwhile. Programs that use hash in qsearch could gain much more as >80% of null move searches go directly to qsearch.

But is it recommended to have null move going directly (and blindly) to qsearch. Seems bad.

Rasjid.

It works OK if you have a layer of checks to help avoid the mate threats. Null-move has two issues. One is well known (zugzwang). The other is taking the search directly to q-search where mates are missed. Back when we first stated doing null-move search in the late 80's, the null-move killer was positions such as where black has played g6, and white has a pawn at f6 and queen at h6, with the black king on h/g8. The obvious threat is Qg7#. But if you (the losing side) can try a null-move and end up in the q-search, you miss Qg7# and the search can fail high and cause you to believe that your opponent will not come down this path. Wrong. A layer of checks in the q-search solves this easily.

[Chan Rasjid]

Thanks for the clarification.

I will think about it.

Rasjid.