Zobrist free

[Ras]

I wanted to eliminate the risk of a hash collision.

There is a paper by Bob Hyatt that shows you don't have to worry about hash collisions if you store at least 48 bits of hash. On PCs, you usually store the full 64 bit value, and collisions become a non-issue in practice.

[Henk]

Yes but then if it plays a very bad move then you still may think it might be that very very seldom appearing hash collision.

[Ras]

That's a psychological issue rather than a technical one. People fear what they can't control, even if the probability is vanishingly small and the overall ELO loss due to less speed outweighs the risk of a hash collision.

If you care about bad moves, I'd tackle static eval first so that silly opening moves like h4 don't happen.

[Dann Corbit]

Yes but then if it plays a very bad move then you still may think it might be that very very seldom appearing hash collision.

See the paper:
"The effect of hash collisions in a Computer Chess program"
Robert M. Hyatt, PhD.
Anthony E. Cozzie

It explains all that.

The bottom line is that if you have a large enough hash signature, then the probability of collision becomes so low there is no discernible effect in game play.

From the Hyatt/Cozzie paper:
"The most unexpected result is that with an error rate of one error for every one thousand hash probes done, over one-half of the positions produce results identical to the no-error versions of the programs. However, this represents such a ridiculously bad hash collision rate, one would have to use a table with just a few entries and a hash signature of just a few bits, to even come close to producing such an error rate."

And further:
" The numbers are surprising, but they clearly show that errors do not influence the search nearly as much as has always been suspected. Even with programs searching at one million nodes per second and beyond, the errors do not wreck the search and cause substantial problems. For example, in the tactical positions, there are just a few key positions that influence the final result. In a tree search space of 120 million nodes, a signature collision on one of such a small set of critical nodes is very unlikely. One point this certainly underlines is that past claims that programs search a large number of useless chess positions is clearly right on target. One can almost change scores at will and still have little adverse effect on the quality of the moves produced.

With large hash tables, the first table suggests that an error rate of one in 1,000,000 probes would be safe for this test set, and that increasing the error rate to one in 100,000 would only change two of eighteen scores for Crafty. Going to one in 10,000 adds one more score change for Crafty, which would not change the outcome in a game nor (apparently) weaken its play at all. For smaller hash tables, both programs are far more sensitive to errors as figure 2 shows.

Obviously such high error rates are not going to be trusted, because this test is based on hashing that has a distinct randomness due to the Zobrist algorithm's use of random numbers. What it does suggest, quite clearly, is that expending effort to drive the error rate below the one in four billion probes sort of range that 64 bit hash signatures produce is effort that is going to produce little return in terms of accuracy for the search."

[jdart]

Just use a 128-bit hash function, or 256 if you are really paranoid. Odds of collison are going to be minuscule.

--Jon

[jdart]

This comes with a caveat, however. That caveat is that you do not rely on any hash data (such as move) that might cause a program crash if it is incorrect, or if you do you have to validate it. I used to store check status in the hash table and that is problematic. Occasional collisions are tolerable unless they are fatal. Then they aren't tolerable at all and with a 48-bit hash you will see some.

--Jon

[Henk]

Just use a 128-bit hash function, or 256 if you are really paranoid. Odds of collison are going to be minuscule.

--Jon

Current one has 512 bits.

I remember once I had a bug in my software which did not happen very often so I thought it was a hash collision but it wasn't. So I did not repair it.

[Ras]

Then they aren't tolerable at all and with a 48-bit hash you will see some.

I have added some additional checks when a lookup detects there is a move stored, no matter whether the move is actually used (because of alpha/beta/exact).

I'm checking that the from-square holds a piece of the right colour, that the to-square is empty or holds a piece of the opposite colour except the king, and that the from/to difference allows for the move mechanics of the moving piece (without checking free in-between squares for sliders).

I think it is highly improbable that these additional conditions would also match in case of a qualified hash collision. Although I'm only using 48 bits of total hash, implicit index hash bits included, I've never seen the debug output that would occur if the additional move checks failed. So that's a non-issue, just as Bob Hyatt concluded.

However, an illegal hash move would not get far anyway. In every node, the full move list is generated, and if the hash move is among them, this move gets spilled to the top of the list. If it isn't, nothing happens.

(This could be made a bit more efficient by doing an explicit full legality check for the hash move and deferring the full move generation if that doesn't give a cut-off. I don't care because the tables are so small that the additional code complexity is not worth the effort.)

[Henk]

Yes but a legal move can still be a bad move. Maybe it won't get noticed but it might have affected evaluation.

Also if it plays a great many games I don't believe hash collisions almost never happen. For how many millions of hash table lookups are there when playing 1000 games.

[Ras]

Yes but a legal move can still be a bad move.

The consequence would be that the move order in a node would be suboptimal, which would have that node take longer.

For how many millions of hash table lookups are there when playing 1000 games.

And yet, I did not see the debug output from my additional checks.