Hi, I posted a while ago about my plan to incorporate TTs into my engine and I was requested to make sure I have castling and en-passant complete, which I have now done.
During the MAKE_MOVE process I will be creating the key for the position.
How should I include in the key:
a) Side to move
b) Castling Rights (2 different positions could look same, but have different castling rights)
c) En-passent capturable pawns
Only the XORPart is updated differentially. The stm and the epSquare are instantaneous contributions, incorporated at the moment the key is used. In principle, the CastlingRights could be handled differentially, each time a right changes. But as the rights d not only change by castling, but also by moving kings or rooks, this was too much of a hassle.
By the way... You might want to use 64 bits for Zobrist keys.
I think conventional wisdom is that 32 bits is not enough to avoid collisions (where two different chess positions end up producing the same Zobrist key).
However with 64 bits and sufficiently random numbers in your tables, the chance of a collision like that is so incredibly small that you can pretty much ignore the possibility. (You might prefer to make sure your engine won't actually crash if it happens, but producing a wrong result would be fine because it will probably never happen).
If you index into your TT using N bits from the Zobrist key, the chance of two arbitrary positions wanting to fit into the same table entry is 1 / 2^N. This is kind of large. So you would want to store at least (64-N) bits from the Zobrist key in your TT entry -- for maximum safety, all of the bits not used to index into the TT should be stored in there. (The simplest thing to do is store the whole Zobrist key, though that wastes some bits). Then you only have the (extremely small) 1 in 2^64 chance of confusing the two positions.
Well, in practice storing 32 bits in the hash entry as signature, in stead of 64-N, is also sufficient (provided a collission can't crash your engine).
With current TT sizes N is easily 22-24, so you would only lose 8-10 bits. And 54 bits is still large enough to make the probability for a key collission negligible. (If you generate 16M keys per second, you would have a collission every 4 billion seconds. And a collission is almost always without effect on the root move / score.)
hgm wrote:Well, in practice storing 32 bits in the hash entry as signature, in stead of 64-N, is also sufficient (provided a collission can't crash your engine).
With current TT sizes N is easily 22-24, so you would only lose 8-10 bits. And 54 bits is still large enough to make the probability for a key collission negligible. (If you generate 16M keys per second, you would have a collission every 4 billion seconds. And a collission is almost always without effect on the root move / score.)
The probability you give is that of a collision with one particular key. The probability of any two keys matching is much higher. (If you generate 16M keys per second, you would have a collision about every 10 seconds. See http://en.wikipedia.org/wiki/Birthday_paradox for details)
hgm wrote:Well, in practice storing 32 bits in the hash entry as signature, in stead of 64-N, is also sufficient (provided a collission can't crash your engine).
With current TT sizes N is easily 22-24, so you would only lose 8-10 bits. And 54 bits is still large enough to make the probability for a key collission negligible. (If you generate 16M keys per second, you would have a collission every 4 billion seconds. And a collission is almost always without effect on the root move / score.)
The probability you give is that of a collision with one particular key. The probability of any two keys matching is much higher. (If you generate 16M keys per second, you would have a collision about every 10 seconds. See http://en.wikipedia.org/wiki/Birthday_paradox for details)
It is not a practical problem based on the assumption that
"a collission is almost always without effect on the root move / score"
Wesley is right, though: the 1 in 4 billion (2^32) is the error rate per access, not per second.
The maximum rate at which I could do (randomly distributed) memory reads is more like 4M per second, though. So you would expect a key collission every 1000 seconds.
But if it does not happen on a node of the PV, or very close to it, the seach will simply steer away from it. In practice you benifit much more from the larger number of entries you can afford in the same amount of memory by shrinking the signature, than that the occasional error would harm you. Even if you would lose 1 in a 1000 games because of a collission, that would only amount to 0.35 Elo points (assuming that otherwise you woul have scored on the average a draw).
In my measurements a speed doubling (supposed to gain ~50-70 Elo)resulted from expanding the hash by a factor 2^12, so that is about 5 Elo points per doubling. So saving 5% on the size of an entry would gain you 0.35 Elo (1.05^14 = 2). And saving 4 byte on a 20-byte entry is 20%...