No Zobrist key

[Daniel Anulliero]

Looks like my engine is twice as slow as before. Don't know yet why. Perhaps creating 64 bit hash key costs too much. In previous key implementation I only had to copy 8 x 64 bits (these bit boards).

You are doing something badly wrong.

To make a move you simply need to do TWO XOR operations, one to remove the from square, one to add the to square. A capture adds a third XOR to remove the captured piece.

To unmake, you simply restore the original hash signature that you should have saved before updating it...

I can't even measure the cost of this in my engine it is so small.

There is also an XOR for side to move.

I don't do that in Make/Unmake. I do that at the time I use the signature to probe or store. You don't want to xor in side to move at ply=1, then xor it in again at ply=3, as you just undid the xor.

I don't understand why you don't do that in make/unmake
Because in my logic, I do (for exemple white have to play) :

Code: Select all

Make move
Hash ^= stm (white) remove white stm from hashcode
Change the color to black (now stm = black)
Hash ^= stm ( black)

And I do that for ep and castle rights too.
Some lights by Bob are welcome

[Evert]

I don't do that in Make/Unmake. I do that at the time I use the signature to probe or store. You don't want to xor in side to move at ply=1, then xor it in again at ply=3, as you just undid the xor.

I don't follow.
After making a move I always xor in the STM key, which makes BTM and WTM positions differ by exactly this key. Why would one not do that?

[Evert]

Because in my logic, I do (for exemple white have to play) :

Code: Select all

Make move
Hash ^= stm (white) remove white stm from hashcode
Change the color to black (now stm = black)
Hash ^= stm ( black)

You can pick one those to be 0 without loss of generality.

[hgm]

The point is that you have to do it once per node anyway, whether you do it incrementally or not. So you might as well do

totalKey = incrementalKey ^ stmKey[stm] ^ epKey[epFile] ^ castlingKey[rights];

at the top of every node. In KingSlayer I use

totalKey = incrementalKey ^ (1+stm)*(32+epSquare);

(where stm = 0 or 8, and epSquare a 0x88 square number).

[Sven]

The point is that you have to do it once per node anyway, whether you do it incrementally or not. So you might as well do

totalKey = incrementalKey ^ stmKey[stm] ^ epKey[epFile] ^ castlingKey[rights];

at the top of every node. In KingSlayer I use

totalKey = incrementalKey ^ (1+stm)*(32+epSquare);

(where stm = 0 or 8, and epSquare a 0x88 square number).

With that method, how do you solve checking for 3-fold repetition? Do you recalculate the non-incremental key components for previous game positions from stored information (epSquare, castling rights)?

[hgm]

totalKey can be a local variable in the Search() routine, also used for repetition checking. It is compared with versions of this totalKey that were stored in a table (stack or small hash table) by the nodes that calculated them. But in fact I just store a draw score in the hash entry for the node (exact and infinite depth) immediately after probing. That will produce a draw score for any move leading back to it, without ever having to do specific testing for it. The high depth protects the entry from overwrite.

The latest Fairy-Max uses a similar method, except that it sets a flag in the hash entry to indicate the node is in the current search path. Storing of draw scores in entries that occurred in the game history was already done in micro-Max, but through that flag they are now also caught in search (so that it can sacrifice to create a perpetual check).

This method for repetition checking doesn't work very well in Shogi, though (and Crazyhouse, I suppose). Because you want to detect repetitions of the board position, even when the pieces in hand are different. But you don't want positions with different hands to map into the same hash entry.

[Daniel Anulliero]

I wonder if I can do

Code: Select all

..make move ..
Hash ^= new ep 
Hash ^= new castling right
Hash ^= new stm

Instead of

Code: Select all

Hash ^= old ep (remove old code from hashcode);make(or not) ep
Hash ^= new ep
Hash ^= old castling right; make castling (or not)
Hash ^= new castling right
Hash ^= old stm; change stm
Hash ^= new stm

I do that in Isa , but if we can do the same with only 3 ^ opérations it'll be better

[Sven]

I wonder if I can do

Code: Select all

..make move ..
Hash ^= new ep 
Hash ^= new castling right
Hash ^= new stm

Instead of

Code: Select all

Hash ^= old ep (remove old code from hashcode);make(or not) ep
Hash ^= new ep
Hash ^= old castling right; make castling (or not)
Hash ^= new castling right
Hash ^= old stm; change stm
Hash ^= new stm

I do that in Isa , but if we can do the same with only 3 ^ opérations it'll be better

Instead of

Code: Select all

Hash ^= old stm; change stm
Hash ^= new stm

you can certainly always use:

Code: Select all

change stm; Hash ^= stmKey

since you do not need two different stm keys. In WTM positions stmKey is out and in BTM positions it has been XORed into the hash key.

The first of the two methods above is the one explained by HGM. I'm starting to like it since it has potential to both simplify and (slightly) speed up the makeMove code. It requires some other changes but I think I'll give it a try.

[hgm]

You can get rid of explicit handling of the stm key altogether (except with null move) if you initialize the Zobrist table for empty squares with it. Normally this would contain all zeros. But if you XOR all piece keys with the stm key, and those zeros as well, the expression

key ^= Zobrist[piece][from] ^ Zobrist[piece][to] ^ Zobrist[victim][to]

will then incrementally XOR with the stm key, as it has an odd number of factors. (This would not work for an additive key, though.) Of course XOR'ing all piece keys with the stm key is pointless, as they were random anyway, so you can just imagine it has already been done to random values that originally were different.

[bob]

Because in my logic, I do (for exemple white have to play) :

Code: Select all

Make move
Hash ^= stm (white) remove white stm from hashcode
Change the color to black (now stm = black)
Hash ^= stm ( black)

You can pick one those to be 0 without loss of generality.

In my case, if it is wtm I use the basic hash key. If it is btm, I simply complement the key.