Hashing a quadboard from scratch

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Fabio Gobbato
Posts: 132
Joined: Fri Apr 11, 2014 8:45 am
Contact:

Re: Hashing a quadboard from scratch

Post by Fabio Gobbato » Thu Nov 24, 2016 9:22 am

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
Posts: 353
Joined: Sat May 05, 2012 12:48 pm
Location: Bergheim

Re: Hashing a quadboard from scratch

Post by BeyondCritics » Thu Nov 24, 2016 2:22 pm

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.

User avatar
Kotlov
Posts: 209
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Hashing a quadboard from scratch

Post by Kotlov » Thu Nov 24, 2016 9:06 pm

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 ))

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Hashing a quadboard from scratch

Post by stegemma » Fri Nov 25, 2016 6:25 am

Edoardo Manino wrote: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.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

BeyondCritics
Posts: 353
Joined: Sat May 05, 2012 12:48 pm
Location: Bergheim

Re: Hashing a quadboard from scratch

Post by BeyondCritics » Fri Nov 25, 2016 2:39 pm

Kotlov wrote: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
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Hashing a quadboard from scratch

Post by Henk » Fri Nov 25, 2016 3:33 pm

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.

User avatar
Kotlov
Posts: 209
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Hashing a quadboard from scratch

Post by Kotlov » Fri Nov 25, 2016 7:41 pm

BeyondCritics wrote: 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
Posts: 353
Joined: Sat May 05, 2012 12:48 pm
Location: Bergheim

Re: Hashing a quadboard from scratch

Post by BeyondCritics » Fri Nov 25, 2016 9:44 pm

Kotlov wrote:
BeyondCritics wrote: 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.

User avatar
Kotlov
Posts: 209
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Hashing a quadboard from scratch

Post by Kotlov » Sat Nov 26, 2016 8:04 am

BeyondCritics wrote:Zobrist hashing hashes the position on the board (plus some extra bits for current state). Why don't you do that?
much faster ))

Post Reply