No Zobrist key
Moderators: hgm, Rebel, chrisw
-
- Posts: 1756
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: No Zobrist key
I've just realised that I've over looked castle rights / so square for my hashes. What's the process to add them in? A 64 length array of zorbist keys for ep, and 16length array of zorbist keys for castle rights?
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 759
- Joined: Fri Jan 04, 2013 4:55 pm
- Location: Nice
Re: No Zobrist key
Yes Andrew (but in reality , 16 keys are sufficent for en passant moves) and 2 keys for the side to move too , but I think we are a little bit off topic of Mr Henk....AndrewGrant wrote:I've just realised that I've over looked castle rights / so square for my hashes. What's the process to add them in? A 64 length array of zorbist keys for ep, and 16length array of zorbist keys for castle rights?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: No Zobrist key
16 zobrist keys for castling rights is ok. For ep target square 8 zobrist keys for the different files would be sufficient since the moving side is already part of the hash key (or it should be) and file + moving side uniquely identifies the ep target square (always on 6th resp. 3rd rank). However, you also need a 9th state for "no ep target square".AndrewGrant wrote:I've just realised that I've over looked castle rights / so square for my hashes. What's the process to add them in? A 64 length array of zorbist keys for ep, and 16length array of zorbist keys for castle rights?
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: No Zobrist key
In fact, only 4 of those need to be linearly independent, of course (it is sufficient to xor in the applicable castling right key(s) if the move gives up castling rights).Sven Schüle wrote: 16 zobrist keys for castling rights is ok.
Yes, but that can be taken to be 0.For ep target square 8 zobrist keys for the different files would be sufficient since the moving side is already part of the hash key (or it should be) and file + moving side uniquely identifies the ep target square (always on 6th resp. 3rd rank). However, you also need a 9th state for "no ep target square".
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: No Zobrist key
Right, I just looked into my own code and saw that I use an array of 8 keysEvert wrote:Yes, but that can be taken to be 0.Sven Schüle wrote:For ep target square 8 zobrist keys for the different files would be sufficient since the moving side is already part of the hash key (or it should be) and file + moving side uniquely identifies the ep target square (always on 6th resp. 3rd rank). However, you also need a 9th state for "no ep target square".
Re: No Zobrist key
What about generating the zobrist keys?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: No Zobrist key
Why so complicated? Just pull the numbers you need from a pseudo-random number generator and call it a day.flok wrote:What about generating the zobrist keys?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?
Or even just use the fruit/polyglot ones if you're really lazy.
Re: No Zobrist key
Complicated? For me that's just the easiest way! I mean I don't have to make sure that the PRNG works ok and does what I expect. And regarding using other people's code: I try not to, then I won't have any licensing issues. So far I copied 1 line of code.Evert wrote:Why so complicated? Just pull the numbers you need from a pseudo-random number generator and call it a day.flok wrote:What about generating the zobrist keys?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?
Or even just use the fruit/polyglot ones if you're really lazy.
-
- Posts: 759
- Joined: Fri Jan 04, 2013 4:55 pm
- Location: Nice
Re: No Zobrist key
Mersenne twister is a good generator and they had 1000 64 bits numbers on the page (I can't find now)
I saved these numbers and put in my engine
Better to have the same code at each exécution
I saved these numbers and put in my engine
Better to have the same code at each exécution
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: No Zobrist key
Sven Schüle wrote:That's 32 memory accesses to rep (hopefully most from cache) plus 152 shifts (j * 8 is like j << 3), 80 "+=" and 40 "^=" operations, plus some loop control stuff. A lot of calculation, even if almost everything is done in registers, and it will certainly burn many CPU cycles. "Beware of nested loops" ...Henk wrote:I use this key for hash table.
And I wonder if it does make my engine slow and if Zobrist key would be much better. But hash table is not used in qSearch.Code: Select all
public Key(IChessBoardBits board) { rep = new ulong[SIZE]; rep[0] = board.Pawns; rep[1] = board.Kings; rep[2] = board.Knights; rep[3] = board.Bishops; rep[4] = board.Rooks; rep[5] = board.Queens; rep[6] = board.WhitePieces; rep[7] = board.Other; } public bool Equals(Key key) { for (int i = 0; i < SIZE; i++) { if (rep[i] != key[i]) return false; } return true; } public override int GetHashCode() { int hash, i; for (hash = i = 0; i < SIZE; ++i) { for (int j = 0; j < 4; j++) { hash += (int)(rep[i] >> (j * 8)); hash += (hash << 10); hash ^= (hash >> 6); } } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return hash; }
[Don't ask how GetHashCode works for it's abracadabra to me now]
Btw, where are the other properties of the position like side to move, castling rights, ep target square, that need to have an influence on the hash key?
I would ask some different questions first before asking about the performance: does this hash function distribute well over the whole index range (so your hash table will reach 100% "used" entries after some moves), and what is your collision rate?
Speed-wise it is clear that this way is slow since you always have to calculate the hash key from scratch while the Zobrist method allows to do that incrementally based on very few XORs. But if there are massive functional drawbacks then the speed argument would not matter any longer, of course ...
The distribution properties of the hash function could be analyzed by running a simulation where you allocate a table of N entries (N = your typical number of hash table entries) with 1 bit per entry (or, to save programming effort, one byte representing a bool), initialize the table to 0, generate many "realistic random positions" (more than N), calculate your hash function for each position, take its index bits as indicated by N, and set table[index] to 1. Then count how often you store a "1" where you already had a "1" before, and how many entries remain at "0" in the end.
Code: Select all
public override int GetHashCode()
{
int hash = 0;
for (int i = 0; i < SIZE-1; i++)
{
hash += (int)(rep[i] % 13);
hash = (hash << 4);
}
hash += (int)(rep[SIZE-1] % 13);
return hash;
}