xoring "BlackToMove" in Hashkey

Discussion of chess software programming and technical issues.

Moderator: Ras

EricLang

xoring "BlackToMove" in Hashkey

Post by EricLang »

Do you, beloved chessprogrammers, change the board-hashkey when changing the color-to-move? And how?
I'm sorry if I ask stupid beginner-questions, but this will change in the future, I hope :)

I use zobristkeys to xor pieces in and out, but have some problems with xor-ing the colortomove into the hashkey.
User avatar
hgm
Posts: 28359
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: xoring "BlackToMove" in Hashkey

Post by hgm »

Most people have also two Zobrist randoms for stm, one for wtm, one for btm. In principle you could set one to zero (i.e. use only one, for btm, say), as either one or the other is to move, never both or none.

In micro-Max I simply add epSquare*sideToMove to the hash key, to account for both the e.p. rights and side to move.
EricLang

Re: xoring "BlackToMove" in Hashkey

Post by EricLang »

Ok thanks. I solved my problem btw.
I use only one key now for btm.
Now I can go back to evaluation, move ordering and openingsbook :)
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: xoring "BlackToMove" in Hashkey

Post by bob »

EricLang wrote:Do you, beloved chessprogrammers, change the board-hashkey when changing the color-to-move? And how?
I'm sorry if I ask stupid beginner-questions, but this will change in the future, I hope :)

I use zobristkeys to xor pieces in and out, but have some problems with xor-ing the colortomove into the hashkey.
I simply complement the hash key so that the hash signature is X for wtm, ~X for btm. Simple and effective.
EricLang

Re: xoring "BlackToMove" in Hashkey

Post by EricLang »

Ok, I do this too now. I could not find it in your crafty source code, because I can hardly read C-code.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: xoring "BlackToMove" in Hashkey

Post by bob »

EricLang wrote:Ok, I do this too now. I could not find it in your crafty source code, because I can hardly read C-code.
It is done like this in HashProbe():

temp_hashkey = (wtm) ? HashKey : ~HashKey;

I then use temp_hashkey for the actual probe and key match.
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: xoring "BlackToMove" in Hashkey

Post by Sven »

hgm wrote:In micro-Max I simply add epSquare*sideToMove to the hash key, to account for both the e.p. rights and side to move.
One should probably add a note that this is only possible if sideToMove is always nonzero, which may be the case in your engine but not in many others that use a White=0/Black=1 scheme.

EDIT: same applies for epSquare, I guess you ensure that epSquare != 0 always holds.

EDIT2: what did you really mean: "add epSquare*sideToMove", or "add ZobristKey[epSquare]*ZobristKey[sideToMove]"?

Sven
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: xoring "BlackToMove" in Hashkey

Post by sje »

Symbolic uses separate tables for white and black. Simple and fast.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: xoring "BlackToMove" in Hashkey

Post by bob »

sje wrote:Symbolic uses separate tables for white and black. Simple and fast.
I've never liked the separate table approach. In the typical tree, one side has way more entries than the other, thanks to the odd/even approach and one table can be overloaded, while the other is sparsely populated...

This can be caused by odd/even search depths as iterations progress, but also because of how the alpha/beta tree is searched, where the root is an ALL node, and for the cases where you don't change your mind, you end up with a huge number of ODD numbered ALL nodes, and very few even-numbered ALL nodes which really loads the table with the odd-numbered depth TIP branches...
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: xoring "BlackToMove" in Hashkey

Post by sje »

bob wrote:
sje wrote:Symbolic uses separate tables for white and black. Simple and fast.
I've never liked the separate table approach. In the typical tree, one side has way more entries than the other, thanks to the odd/even approach and one table can be overloaded, while the other is sparsely populated...

This can be caused by odd/even search depths as iterations progress, but also because of how the alpha/beta tree is searched, where the root is an ALL node, and for the cases where you don't change your mind, you end up with a huge number of ODD numbered ALL nodes, and very few even-numbered ALL nodes which really loads the table with the odd-numbered depth TIP branches...
Symbolic, like many programs, has much code dedicated to extensions and reductions. The effect of variable depth search is that both tables are roughly equally utilized. Also, the tables are persistent from move to move and this further reduces any color bias.