Page 1 of 2
Re: Hashing a quadboard from scratch
Posted: Thu Nov 24, 2016 10:22 am
by 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.
Re: Hashing a quadboard from scratch
Posted: Thu Nov 24, 2016 3:22 pm
by 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.
Re: Hashing a quadboard from scratch
Posted: Thu Nov 24, 2016 10:06 pm
by 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 ))
Re: Hashing a quadboard from scratch
Posted: Fri Nov 25, 2016 7:25 am
by stegemma
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(int i = 0; i < 4; ++i) {
key ^= (position.bb[i] & mask) * magic_A[i];
key ^= (position.bb[i] >> 32) * magic_B[i];
}
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.
Re: Hashing a quadboard from scratch
Posted: Fri Nov 25, 2016 3:39 pm
by BeyondCritics
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.
Re: Hashing a quadboard from scratch
Posted: Fri Nov 25, 2016 4:33 pm
by 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.
Re: Hashing a quadboard from scratch
Posted: Fri Nov 25, 2016 8:41 pm
by Kotlov
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
Re: Hashing a quadboard from scratch
Posted: Fri Nov 25, 2016 10:44 pm
by BeyondCritics
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.
Re: Hashing a quadboard from scratch
Posted: Sat Nov 26, 2016 9:04 am
by Kotlov
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 ))