Hashing a quadboard from scratch

[Edoardo Manino]

Hi all,
lately I have been thinking about the hashing function of a position and how to generate it from scratch (as opposed to updating it incrementally a la Zobrist). After reading the chessprogramming wiki and a couple of old TalkChess threads, an idea came up to my mind that may be interesting for the community.

Let's suppose we have a quadboard representation, and all the other relevant information (castling, ep, side to move) is squeezed in the lower bits of another word (five 64-bit words in total). We can compute a key with the following code:

Code: Select all

BITBOARD mask = 0x00000000FFFFFFFF;

HASHKEY key = (position.state * magic_C);

for&#40;int i = 0; i < 4; ++i&#41; &#123;
    key ^= &#40;position.bb&#91;i&#93; & mask&#41; * magic_A&#91;i&#93;;
    key ^= &#40;position.bb&#91;i&#93; >> 32&#41; * magic_B&#91;i&#93;;
&#125;

In total we need 9 constant random number ("magic" in the code) and the code executes 9 multiplies, 4 shifts, 4 logical AND, 8 logical XOR and 5+9 memory accesses. Not exactly competitive w.r.t. the incremental approach, but for now I will keep it as speed is not my main focus.

A quick note on this approach. Since I use multiplications to "spread out" the information, the upper bits of each word tend to contribute less to the final result. In order to compensate for that, I split each bitboard in two halves and perform the multiplication twice (with different magic numbers). Still, I expect the final result to be quite poor on the lower bytes, hence I am planning to use the upper part, and not the lower, as an index in the transposition table.

[kbhearn]

What you're doing is close to the murmur algorithms but with less mixing

https://github.com/aappleby/smhasher/wiki/MurmurHash3

Perhaps most importantly is the finalizing step where it mixes the compiled key together with 3 shift steps and 2 multiples (perhaps 2 shifts and 1 multiply would do - would have to test) and ensures all input bits are well distributed.

Seeing as you're doing your own makeshift hash you will have to test whether it's correctly identifying small differences and spreading throughout your hash table - since both aspects are important just using the stronger bits for distribution and the weaker bits to determine it's really the same position is probably not acceptable.

[Fabio Gobbato]

I think it's a good idea that can worth a try.

In my engine I use the zobrist hashing that is not really expensive because with the key I have also to incrementaly update the material+pst scores.

I use a struct that contains all like this:

Code: Select all

typedef struct
{
	uint64_t Hash;
	int16_t ScoreMg;
	int16_t ScoreEg;
} THashEval;

THashEval HashEval[1037]; //the array with all the zobrist keys and the scores

So when I have to update the position it brings me only a few memory accesses for the key and the scores.
Furthermore with copy-make I don't need to restore the previus key so in my engine zobrist hashing is very fast.

Having said that your solution seems good and could be successful used in engines.

[BeyondCritics]

If your magic multipliers are odd, you implement multiplicative hashing, which is known to be in the class of 2-universal hash functions. XOR-ing universal hash functions, yields you another universal hash function. This of course is known for ages, e.g. see K. Mehlhorn, "Data Structures and Algorithms".

I don't like the usage of arrays of here, i guess it would be faster to use constants and unroll by hand. The compiler can then embed your constants into the instruction stream, which alleviates memory pressure.

[Kotlov]

Hi all!

My hash-function in quadboard paradigm is:

(hi^(zk[m.t]+zk[m.f+64]+zk[m.s+(K&128)+128]))&hm

zk[0..383] - Zobrist keys
hi - previous hash
m.t - 0..63 move to
m.f - 0..63 move from
m.s - 0..128 move specifics (piece and flags)
K - 0..1 color
hm - hash size mask

I don't know if it's correct, but it works ))

[stegemma]

Hi all,
lately I have been thinking about the hashing function of a position and how to generate it from scratch (as opposed to updating it incrementally a la Zobrist). After reading the chessprogramming wiki and a couple of old TalkChess threads, an idea came up to my mind that may be interesting for the community.

Let's suppose we have a quadboard representation, and all the other relevant information (castling, ep, side to move) is squeezed in the lower bits of another word (five 64-bit words in total). We can compute a key with the following code:

Code: Select all

BITBOARD mask = 0x00000000FFFFFFFF;

HASHKEY key = (position.state * magic_C);

for&#40;int i = 0; i < 4; ++i&#41; &#123;
    key ^= &#40;position.bb&#91;i&#93; & mask&#41; * magic_A&#91;i&#93;;
    key ^= &#40;position.bb&#91;i&#93; >> 32&#41; * magic_B&#91;i&#93;;
&#125;

In total we need 9 constant random number ("magic" in the code) and the code executes 9 multiplies, 4 shifts, 4 logical AND, 8 logical XOR and 5+9 memory accesses. Not exactly competitive w.r.t. the incremental approach, but for now I will keep it as speed is not my main focus.

A quick note on this approach. Since I use multiplications to "spread out" the information, the upper bits of each word tend to contribute less to the final result. In order to compensate for that, I split each bitboard in two halves and perform the multiplication twice (with different magic numbers). Still, I expect the final result to be quite poor on the lower bytes, hence I am planning to use the upper part, and not the lower, as an index in the transposition table.

You can try my idea (and see other comments on it) in this thread:

http://www.talkchess.com/forum/viewtopic.php?t=60343

It works well in Satana book handling and/or in TT indexing.

[BeyondCritics]

Hi all!

My hash-function in quadboard paradigm is:

(hi^(zk[m.t]+zk[m.f+64]+zk[m.s+(K&128)+128]))&hm

zk[0..383] - Zobrist keys
hi - previous hash
m.t - 0..63 move to
m.f - 0..63 move from
m.s - 0..128 move specifics (piece and flags)
K - 0..1 color
hm - hash size mask

I don't know if it's correct, but it works ))

You are mixing additions with the xor-operator, this looks rather strange with all this mysterious constants. Normal zobrist hashing is much simpler.
Furthermore, if you have K = 0..1, then (K&128) is always zero, this should be some oversight. On the other hand, if K = 0,128 and m.s could really be 128 you could get an index of 384, off by one!

No matter what you do, if you do the same in the next iteration you get the same hash, so it could work most of the time, but i can't imagine that your hash is correct.

[Henk]

I implemented Zobrist key few months ago and I still think it was a waste of time for it gave not much speed improvement. Only gave some tough bugs and extra complexity. Maybe I have to put old source back.

[Kotlov]

You are mixing additions with the xor-operator, this looks rather strange with all this mysterious constants. Normal zobrist hashing is much simpler.
Furthermore, if you have K = 0..1, then (K&128) is always zero, this should be some oversight. On the other hand, if K = 0,128 and m.s could really be 128 you could get an index of 384, off by one!

No matter what you do, if you do the same in the next iteration you get the same hash, so it could work most of the time, but i can't imagine that your hash is correct.

1) of course K&128 is color (0 or 128)

2) m.s is: char

Code: Select all

N/A castle  promotion   e.p  captue  piece
  x    x        x        x     x      xxx    

3) zk[] is just 384 random int32 (like Zobrist keys)

4) hash (hi) is argument of search function

[BeyondCritics]

You are mixing additions with the xor-operator, this looks rather strange with all this mysterious constants. Normal zobrist hashing is much simpler.
Furthermore, if you have K = 0..1, then (K&128) is always zero, this should be some oversight. On the other hand, if K = 0,128 and m.s could really be 128 you could get an index of 384, off by one!

No matter what you do, if you do the same in the next iteration you get the same hash, so it could work most of the time, but i can't imagine that your hash is correct.

1) of course K&128 is color (0 or 128)

2) m.s is: char

Code: Select all

N/A castle  promotion   e.p  captue  piece
  x    x        x        x     x      xxx    

3) zk[] is just 384 random int32 (like Zobrist keys)

4) hash (hi) is argument of search function

I think i get it now: You do hash the complete string of moves to the position, in a way such that each permutation of this moves gets you the same key.
This is interesting, but not the way it is done normally. Zobrist hashing hashes the position on the board (plus some extra bits for current state). Why don't you do that?

As a side note: You should use "uint32" instead of "int32" as hash keys, otherwise you are running into integer overflow problems.