Zobrist keys - measure of quality?

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
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Zobrist keys - measure of quality?

Post by cdani » Tue Feb 24, 2015 2:02 pm

I use this to generate random numbers:
http://www.math.sci.hiroshima-u.ac.jp/~ ... T/emt.html

Daniel Anulliero
Posts: 686
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: Zobrist keys - measure of quality?

Post by Daniel Anulliero » Tue Feb 24, 2015 2:04 pm

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]

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Zobrist keys - measure of quality?

Post by mar » Tue Feb 24, 2015 2:27 pm

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.

Daniel Anulliero
Posts: 686
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: Zobrist keys - measure of quality?

Post by Daniel Anulliero » Tue Feb 24, 2015 2:31 pm

Thanks for the very quick answer :wink:
Bests
Dany

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Zobrist keys - measure of quality?

Post by mar » Tue Feb 24, 2015 2:33 pm

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.

AlvaroBegue
Posts: 919
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Zobrist keys - measure of quality?

Post by AlvaroBegue » Tue Feb 24, 2015 2:38 pm

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.

User avatar
hgm
Posts: 23613
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Zobrist keys - measure of quality?

Post by hgm » Tue Feb 24, 2015 4:24 pm

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.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: Zobrist keys - measure of quality?

Post by SMIRF » Tue Feb 24, 2015 4:35 pm

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.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Zobrist keys - measure of quality?

Post by cdani » Tue Feb 24, 2015 8:00 pm

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.

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Zobrist keys - measure of quality?

Post by Sven » Tue Feb 24, 2015 9:43 pm

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"?

Post Reply