Hashing based on move lists

[ZirconiumX]

Please demonstrate this, since with my stupid eyes I cannot see anything.

For instance Ra1, Ba8 and Ra1, Bh1


To moderation: Please be so kind to consider taking action against the the troll: it is many days already that he is dirtying up the threads. Normally this kind of people disappears after few days, but this one seems persistent so please evaluate about blocking the account.

I don't see why you needed Ra1 here, but I exclude bishop's positions, so in my implementation there won't be a collision in this case. This is not to say that my implementation is "perfect". But if deficiencies are found, they will be easier to eliminate, because the pseudo-random number generator is no longer there to reduce our ability to control what's going on.

Because the rook covers the bishop's square. But it still doesn't collide because a8 is XORed out in the Bh1 variant, and vice versa.

Matthew:out

[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.

[Gusev]

I made my presentation on Gusev hashing available at http://firenzina.wikispaces.com/file/vi ... tation.zip. The code (LegalMoveAndFlagsGen) is available at http://firenzina.wikispaces.com/file/vi ... ngCode.zip. It should be straightforward to incorporate in Stockfish, because the code is based primarily on Stockfish 2.2.2 to begin with. The main chess engine functionality was removed.

[Henk]

In my chess program, which has a dreadful performance by the way, I use the hashcode to look up an entry. If there are more entries with the same hashcode an equality operation is applied on the board representation.

So you store the whole board representation in the hash entry. That is not very competitive.

I do not want a hash function that possibly may look up wrong positions through collisions. I'm not gona implement a fruit machine. (gambling machine).

If you prefer dreadful performance over a negligble amount of incorrect probes that have an even more negligble chance of affecting the move played, then this is certainly the way to go.

I do not know at this moment if this dreadful performance is caused by cloning a complete key or a partial key(zobrist key). Of course it's less efficient. Do you know what percentage of these zobrist probes collide ?

[Gusev]

In my chess program, which has a dreadful performance by the way, I use the hashcode to look up an entry. If there are more entries with the same hashcode an equality operation is applied on the board representation.

So you store the whole board representation in the hash entry. That is not very competitive.

I do not want a hash function that possibly may look up wrong positions through collisions. I'm not gona implement a fruit machine. (gambling machine).

If you prefer dreadful performance over a negligble amount of incorrect probes that have an even more negligble chance of affecting the move played, then this is certainly the way to go.

I do not know at this moment if this dreadful performance is caused by cloning a complete key or a partial key(zobrist key). Of course it's less efficient. Do you know what percentage of these zobrist probes collide ?

See http://www.cis.uab.edu/hyatt/collisions.html for info.

[Gusev]

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.

[Gusev]

To moderation: Please be so kind to consider taking action against the the troll: it is many days already that he is dirtying up the threads. Normally this kind of people disappears after few days, but this one seems persistent so please evaluate about blocking the account.

To moderators: Matthew is NOT a troll!

[mvk]

I do not want a hash function that possibly may look up wrong positions through collisions. I'm not gona implement a fruit machine. (gambling machine).

I'm interested in your evaluation function.

[Gusev]

I do not want a hash function that possibly may look up wrong positions through collisions. I'm not gona implement a fruit machine. (gambling machine).

I'm interested in your evaluation function.

Just to make sure everybody is on the same page. Hash function and evaluation function are two very different functions.

[Gerd Isenberg]

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.