Hashing based on move lists

[hgm]

Got any better ideas?t

Well, using keys generated by a pseudo-number generator, for instance, would reduce the collision rate by some 10 orders of magnitude...

Some might consider that better.

[sje]

This is true, but Zobrist keys have one problem. They are based on random numbers, and if the random numbers aren't very random at all, then you might have a problem.

Gusev hashing works by removing the randomness element, but is slightly harder to compute.

Why would the Zobrist keys be non-random? Keys produced by any modern pseudorandom source will be sufficiently random; these sources have been very well tested by some very competent people.

The burden of proof is upon the newcomer, as it should be. We would have to see some rather extensive empirical evidence that any substitute for the Zobrist scheme has any benefits. Suggestion: use the alternative scheme to produce perft(n) for n <= 13. I've done these calculations with 128 bit Zobrist keys made from my own pseudorandom source, The results were produced without error and with no need for any sanity testing.

[ZirconiumX]

Indeed, this is what I also remarked above, except that it was not clear to me that they are just using Zobrist hashing with hand-made keys. (Or rather, I could not believe they would propose something so obviously flawed.)

What they propose is of course disastrous. It is hard to think of a scheme that would cause more collisions than this. Perhaps unless you would initialize all keys to zero from the start...

A bit of jiggery-pokery fixes it. You XOR all of the black pieces onto a separate bitboard, THEN complement it, rather than complementing, then XORing.

Matthew:out

[hgm]

Makes it even worse with an XOR key. What you propose just XORs the key with one extra -1 always. This is equivalent to using the same key for black and white pieces of the same type.

[Gerd Isenberg]

I assume you are referring to the XOR version.

Yes.

I used an example with pawns, because pawns are numerous. So how about this example with rooks: Compare the position with rooks on f3 and c6 against the position with rooks on f6 and c3.

You would be right with pure attack sets, but the inclusion of the origin square makes the difference as pointed out by Matthew

[rjgibert]

Using OR is terrible. With pawns on b3, e3 and h3, adding any number of additional pawns to the 3rd rank will leave the signature unchanged.

Using XOR is better, but still bad. Compare the position with pawns on a3, b3, g3 and h3 with the position with pawns on d3 and e3.

Yep, but that collision already requires a lot of plies to occur in a typical search with a common root ancestor. I somehow like the idea to use attack sets on the otherwise empty board as "Zobrist" keys. I guess along with checking stored move is legal, this is quite safe. I guess there are collisions with less pieces different, but I fail to find some on the fly.

I assume you are referring to the XOR version. I used an example with pawns, because pawns are numerous. So how about this example with rooks: Compare the position with rooks on f3 and c6 against the position with rooks on f6 and c3.

Rf3 and Rc6:

Code: Select all

- - X - - X - -
- - X - - X - -
X X X X X - X X
- - X - - X - -
- - X - - X - -
X X - X X X X X
- - X - - X - -
- - X - - X - -

Rc3 and Rf6:

Code: Select all

- - X - - X - -
- - X - - X - -
X X - X X X X X
- - X - - X - -
- - X - - X - -
X X X X X - X X
- - X - - X - -
- - X - - X - -

Still bulletproof.

Matthew:out

What you give applies to OR, I was talking about XOR with my example using rooks, so it will look like this for both positions:

Code: Select all

- - X - - X - -
- - X - - X - -
X X - X X - X X
- - X - - X - -
- - X - - X - -
X X - X X - X X
- - X - - X - -
- - X - - X - -

A square attacked an even number of times cancels the X.

[Gerd Isenberg]

This is a chess-specific, very low collision (if not zero) hashing method.

This is basically a "do one thing and do it well" method.

Matthew:out

I don't know about zero, because it is impossible to describe a chess position uniquely using only 64 bits. The main idea is that we should be able to do better by controlling piece signatures directly, than by relying upon a pseudo-random number generator.

Sorry if I missed it, how do you distinguish same type white and black pieces (no pawns) which have same attack sets in the final 64-bit key?

He takes the complement (~attack_set) of the piece's attack set for black.

Matthew:out

Thanks, just found the init code in position.cpp, ahh yes, flip is complement and not byteswap. Complement is xor with -1, so each even number of black pieces xored, cancels the complement, hmm..., sounds dangerous.

Got any better ideas?

Matthew:out

maybe the color-flipper trick:

Code: Select all

zob (blackpiece, sq) := byteswap (zob (whitepiece, sq^56) );

[rjgibert]

I assume you are referring to the XOR version.

Yes.

I used an example with pawns, because pawns are numerous. So how about this example with rooks: Compare the position with rooks on f3 and c6 against the position with rooks on f6 and c3.

You would be right with pure attack sets, but the inclusion of the origin square makes the difference as pointed out by Matthew

If you are going to include the origin square, both OR and XOR still fail badly. Compare any position with a bishop on h1 against the otherwise same position with a bishop on a8 instead of h1. To see how this is true, consider the trivial example of just the 1 lone bishop:

Code: Select all

X - - - - - - -
- X - - - - - -
- - X - - - - -
- - - X - - - -
- - - - X - - -
- - - - - X - -
- - - - - - X -
- - - - - - - X

Then add any additional pieces as you wish.

[Gerd Isenberg]

I assume you are referring to the XOR version.

Yes.

I used an example with pawns, because pawns are numerous. So how about this example with rooks: Compare the position with rooks on f3 and c6 against the position with rooks on f6 and c3.

You would be right with pure attack sets, but the inclusion of the origin square makes the difference as pointed out by Matthew

If you are going to include the origin square, both OR and XOR still fail badly. Compare any position with a bishop on h1 against the otherwise same position with a bishop on a8 instead of h1. To see how this is true, consider the trivial example of just the 1 lone bishop:

Code: Select all

X - - - - - - -
- X - - - - - -
- - X - - - - -
- - - X - - - -
- - - - X - - -
- - - - - X - -
- - - - - - X -
- - - - - - - X

Then add any additional pieces as you wish.

Oups, sorry the bit inclusion is not for bishops, see comment in position.cpp 64:

Code: Select all

		  // Bishop doesn't leave footprint on its own square
		  // in order to reduce chances of canceling out of
		  // two bishops in opposing corners of the board:
		  if ((p!=NO_PIECE)&&(pt!=BISHOP)) 
			  zobrist[p][s]^=SquareBB[s];

I start to agree with you, but the more obvious problem seems related with same attacks of different colored pieces ...

[hgm]

maybe the color-flipper trick:

Code: Select all

zob (blackpiece, sq) := byteswap (zob (whitepiece, sq^56) );

Not sure what exactly byteswap does, but the chances that it transforms one valid attack set in another (causing two identical keys in the set) seems pretty large. Imagine for instance the attack set of a Rook. Swapping bytes in pairs, or swapping board halves would all give valid Rook attack sets.

Unlike randomly chosen numbers, non-random keys like attack sets are very likely to transform into each other by simple operations on them.

Seldomly I have seen an idea this flawed, to solve a non-existing problem. It actually creates the (imagined) problem it was supposed to solve, but more than a million times worse.