Hashing based on move lists

[ZirconiumX]

Fine, whatever. I though Dmitri's idea was clever, but I guess I know nothing. I mean, it's not like it's theoretically impossible to have a collision or anything.

This is not Zobrist hashing. OR works just fine here, and you don't have to worry about randomness or anything.

Matthew:out

[lucasart]

The main point of this is that it has a much lower collision rate than Zobrist keys, even 128-bit ones, but 128 bits is impractical for anything other than Perft, IMO.

On what do you base that conclusion

I can already see a lot of trivial ways to make your keys collide...

[ZirconiumX]

The main point of this is that it has a much lower collision rate than Zobrist keys, even 128-bit ones, but 128 bits is impractical for anything other than Perft, IMO.

On what do you base that conclusion

I can already see a lot of trivial ways to make your keys collide...

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

Matthew:out

[Henk]

The main point of this is that it has a much lower collision rate than Zobrist keys, even 128-bit ones, but 128 bits is impractical for anything other than Perft, IMO.

On what do you base that conclusion

I can already see a lot of trivial ways to make your keys collide...

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

Matthew:out

I do not understand what these chess programs do when zobrist key collides.

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.

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

[mcostalba]

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.

[syzygy]

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.

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

OK, talking to Dmitri confirms it was XOR, so my mistake.

With XOR, not OR, this doesn't collide.

Matthew:out

[Gusev]

1) XOR not OR

2) Zobrist are defined as zob[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB], so when building up a position's key you not only xor together the zobrits keys of the squares occupied by piece, but also they depend on the piece type and color. In your idea instead of just the squares you compose together also a signature of the piece by means of it's more or less unique attacks, but this is already done also by standard ones.

3) Standard one is stronger because takes in consideration also color, instead in your case attacks signatures (except for the pawns) are color independent

1) In my implementation, it was XOR all along (for reason obvious to you and everyone who knows Zobrist hashing: X xor Y xor Y = X).
2) My idea is to use the bits (a) for the piece's position itself (except for bishops, for which I take only their attacks) AND (b) the piece's attacks and squares it could move to (for pawns). I will post my presentation and the code, now that the word is out.
3) For the opposite color, I invert the bits of the piece's signature.
NOTE: The reason for not taking positions of bishops is to avoid mutual cancellation of same color bishops located in the opposite corners of the board, even though such a situation is extremely unlikely (a pawn has to be promoted to a bishop for that to happen).

[Gusev]

Dmitri's method is basically a Zobrist key replacement, that instead of using random numbers, relies on the uniqueness of how chess pieces move.
Matthew:out

Matthew describes my idea correctly in one sentence here. My approach is easier to modify if collisions are detected, because there is no reliance upon a pseudo-random number generator. Instead, we maintain direct control over our actions. (Rather than, say, vary the generator's seed.)

An example of such modification is my decision to exclude positions of bishops and keep their attacks only, once I realized that two bishops in the opposite corners of the board would have cancelled each other's contributions otherwise.

[Gusev]

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.