Page 2 of 3

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 2:02 pm
by cdani
I use this to generate random numbers:
http://www.math.sci.hiroshima-u.ac.jp/~ ... T/emt.html

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 2:04 pm
by Daniel Anulliero
Hi all
Excuse me , if I ask a question (a little bit of topic..) to the experts here?
I quote that from Zobrist hashing wiki :
At program initialization, we generate an array of pseudorandom numbers [7] [8]:
One number for each piece at each square
One number to indicate the side to move is black
Four numbers to indicate the castling rights, though usually 16 (2^4) are used for speedEight numbers to indicate the file of a valid En passant square, if any
Why only one number for black ? Why not for white too?
I have two numbers for white and black in my engine...
It seems There is something I misunderstood ...
Bests
Dany
[/quote]

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 2:27 pm
by mar
Daniel Anulliero wrote:Hi all
Excuse me , if I ask a question (a little bit of topic..) to the experts here?
I quote that from Zobrist hashing wiki :
At program initialization, we generate an array of pseudorandom numbers [7] [8]:
One number for each piece at each square
One number to indicate the side to move is black
Four numbers to indicate the castling rights, though usually 16 (2^4) are used for speedEight numbers to indicate the file of a valid En passant square, if any
Why only one number for black ? Why not for white too?
I have two numbers for white and black in my engine...
It seems There is something I misunderstood ...
Bests
Dany
You only need one value to encode STM, so say if black's to move, you include the STM key (in fact, each time you make a move you simply xor with STM key unless it's a nullmove) - so if you build key from scratch,
if it's white to move you xor with 0 and if black then you xor with the STM key (you could also use one key for WTM and xor with 0 if its' BTM - this really doesn't matter).
If you use two, it will still work of course but it's not necessary.
The same holds for en passant square - you could use 64 values just like for any other square but that would be a waste since knowing only the file is enough, you can get along with just 8 values to encode the ep square.
Actually I made the same mistake and use too many keys to encode castling rights.
Even for chess960, only 3 states per side will do (can castle short, can castle long and can castle both long and short), no castling thus requires no extra key.
This is because rook/king positions are already "encoded" using piece keys.

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 2:31 pm
by Daniel Anulliero
Thanks for the very quick answer :wink:
Bests
Dany

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 2:33 pm
by mar
cdani wrote:I use this to generate random numbers:
http://www.math.sci.hiroshima-u.ac.jp/~ ... T/emt.html
Yes Mersenne Twister is pretty good, also has insane period. However each 624-th pseudo-random number takes much longer than the rest (this is no problem for offline processing),
but I prefer KISS-style PRNGs that are both simpler and faster and most importantly have stable running time.

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 2:38 pm
by AlvaroBegue
Daniel Anulliero wrote:Hi all
Excuse me , if I ask a question (a little bit of topic..) to the experts here?
I quote that from Zobrist hashing wiki :
At program initialization, we generate an array of pseudorandom numbers [7] [8]:
One number for each piece at each square
One number to indicate the side to move is black
Four numbers to indicate the castling rights, though usually 16 (2^4) are used for speedEight numbers to indicate the file of a valid En passant square, if any
Why only one number for black ? Why not for white too?
I have two numbers for white and black in my engine...
It seems There is something I misunderstood ...
Bests
Dany
Every position will have either white to move or black to move. You can use a Zobrist number for each, but the only thing that really matters is the XOR of those two numbers, because that's what's going to be different between black to move and white to move on the same position. So making one of them 0 doesn't change anything.

Actually I use 0 for white and 0x8000000000000001 for black. The idea is that I will use something like (hash_key & 0xffffff) to determine where in the transpositions table I will store a position, so with these codes I ensure the white-to-move and the black-to-move entries for the same position are contiguous. Since my engine uses the null-move heuristic, I will often look up both of those positions in succession, so some of the time I save a cache miss. The highest bit is set because I do multiple consecutive probes in the hash tables and I use the high-order bits for verification.

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 4:24 pm
by hgm
In fact you can do away completely with an explicit stm key, as you know it will be applied every turn. All you have to do is assign it to all empty squares on the board (i.e. fill PST[EMPTY][] with it). Then when empty squares are 'captured' (i.e. a non-capture is played) the key is applied automatically. For capture of a real piece you can imagine that the stm key is already XORed into the piece keys. Only for null move you would have to explicitly apply the empty-square key then.

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 4:35 pm
by SMIRF
In my achromatic approach there is not something like a color. The position is always stored for the active side. But surrounding to an executed move both 4-byte double words of the 64 bit key will be swapped.

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 8:00 pm
by cdani
mar wrote:
cdani wrote:I use this to generate random numbers:
http://www.math.sci.hiroshima-u.ac.jp/~ ... T/emt.html
Yes Mersenne Twister is pretty good, also has insane period. However each 624-th pseudo-random number takes much longer than the rest (this is no problem for offline processing),
but I prefer KISS-style PRNGs that are both simpler and faster and most importantly have stable running time.
Thanks.
As I only generate the random numbers at the start of the engine, I understand that there is no problem.

Re: Zobrist keys - measure of quality?

Posted: Tue Feb 24, 2015 9:43 pm
by Sven
mar wrote:(in fact, each time you make a move you simply xor with STM key unless it's a nullmove)
Null move changes STM as well, so why "unless"?