Hash Lock

[aberent]

In a 64 bit Zobrist Hash is it necessary to also have another 64 bit value Hash Lock to detect collisions. I have read some articles that mention this Hash Lock and some that completely omit it. What is the general practice?

[Dann Corbit]

In a 64 bit Zobrist Hash is it necessary to also have another 64 bit value Hash Lock to detect collisions. I have read some articles that mention this Hash Lock and some that completely omit it. What is the general practice?

If the hash consists of 64 bits, and the address consists of k bits, then the lock is the 64-k other bits.

Usually, people just use the high end 4 bytes, since the low end is used for addressing and varies in length depending on the size of the hash table.

So, if the hash address has something stored in it, you examine the lock field. If the fields match, then it is a hash match, else not.

[aberent]

Oh thats not how I understood it. I thought you use the full 64 bits for the hash since your random numbers you generate to XOR various positions are also 64 bits.

I was under the impression the hash is 64 bits and the lock is another 64 bit seperate value.

[Greg Strong]

The only articles mentioning hash locks that I've seen are old articles where 64-bit numbers wern't feasable, in which case there was a 32-bit hash, some part of which was used for indexing into the table, and another 32-bit number was a hash lock, to ensure it really was the same position.

I've seen research (although I can't tell you where right off) that 64 bits is enough to make collisions incredibly unlikely...

[jwes]

The only articles mentioning hash locks that I've seen are old articles where 64-bit numbers wern't feasable, in which case there was a 32-bit hash, some part of which was used for indexing into the table, and another 32-bit number was a hash lock, to ensure it really was the same position.

I've seen research (although I can't tell you where right off) that 64 bits is enough to make collisions incredibly unlikely...

It is not that unlikely. If you have 2^24 or 16 million hash table entries, after your hash table is full, you will have a false hit every 2^40 or about every trillion probes. If you do one million probes per second, that will be roughly once every 12 days of playing time.

[aberent]

Ok that sounds fairly reasonable, thank you for your answers.

[MattieShoes]

The only articles mentioning hash locks that I've seen are old articles where 64-bit numbers wern't feasable, in which case there was a 32-bit hash, some part of which was used for indexing into the table, and another 32-bit number was a hash lock, to ensure it really was the same position.

I've seen research (although I can't tell you where right off) that 64 bits is enough to make collisions incredibly unlikely...

It is not that unlikely. If you have 2^24 or 16 million hash table entries, after your hash table is full, you will have a false hit every 2^40 or about every trillion probes. If you do one million probes per second, that will be roughly once every 12 days of playing time.

But what percentage of collisions would cause a change in the move played? I'm guessing an overwhelming percentage of those collisions that happen once every 12 days of playing time are one alpha node being confused with another alpha node, which does no harm. Even if it confuses alpha and beta, it'll probably just trigger a re-search and then be evaluated correctly.

Locking usually is in reference to multithreaded programs, so two threads aren't simultaneously trying to write to the same hashtable slot, which could potentially give very bad bugs. Dr. Hyatt had a scheme where the program would XOR one half of a hash entry against the other during storage to avoid collisions... Is that possibly what you're thinking of?

[hgm]

I think dr Hyatt tested this once, and that the conclusion was that you needed many thousands of collisions per second to have any measurable impact on engine performance, as long as false probes cannot crash your engine. So I guess one collission per 12 days is quite save.

In Joker I use 32-bit locks, and probe 3 entries per probe, so I would get 3 false matches per 4G probes. That is about 3 per hour. Initially false hits could crash Joker, if the hash move was a castling while the actual position had material on the square the Rook ended on. This material was then not put back on undoing the move, which led to an inconsistency between piece list and board, which later led to table corruption if other moves with the ghost of the piece were done, which finally led to illegal moves. So I fixed that by in the MakeMove() code for castling (which is executed only very in frequently, even when castling rights still exist) also keeping track of what the Rook captures, and restore that on UnMake(). That solved the problem.

[yoshiharu]

Locking usually is in reference to multithreaded programs, so two threads aren't simultaneously trying to write to the same hashtable slot, which could potentially give very bad bugs. Dr. Hyatt had a scheme where the program would XOR one half of a hash entry against the other during storage to avoid collisions... Is that possibly what you're thinking of?

Well, actually I think that in Bob Hyatt's paper the term "lockless" refers to the fact that you don't need any lock (lock as in pthreads_lock) to avoid corruption, because of the clever trick you have mentioned.
While the "lock" in the hash table sense is needed also in single threaded programs, to avoid that a collision (of II type, IIRC) could cause errors or even crashes of the engine.
As far as I can understand, Adam's original question had the term "lock" in the latter meaning.

Cheers, Mauro

[MattieShoes]

Sorry, I guess I misunderstood. I never used the best move directly from the hash table so I guess I never encountered the crashing bugs involved in a collision.