TT Key Collisions, Workarounds?

[Clemens Pruell]

Till now I've used the TT for move ordering purposes only (e.g. retrieve the PV-move from a previous iteration). Having read a very instructive paper by Prof. Hyatt about TT key collisons, when in a test a program would choose a different root move 50% of the time in case the TT is used for 'immediate' cutoffs (transpositions in a sense that the 'same' position 'most likely' occured before & was searched to the same depth, and hence instead of searching it again the score of the hash-move is returned) I'm somewhat afraid that using the TT in this way is a somewhat 'unsound' way of foreward pruning, because it seems to happen very often that two totally different positions get the same Zobrist Key. In extreme cases this could cause the program to blunder horribly.
However, in order to improve my program's overall search depth I'd still like to use the TT for its primary purpose, but I don't know what is a 'safe' workaround for the problem of possible Key Collisions. I've been thinking of using a second TT with completely different 64-bit Zobrist Keys, perhaps this could lower the chance of Key Collsions (must be really incredibly unlikely that two totally different positions get the same two 64-Zobrist Keys), however this certainly means there'll be a siginifant overhead with constantly updating the two different Zobrist Keys, plus of course the required memory would be doubled, too.
So my question: Do you think it's worth the effort to use two Zobrist Keys + twice as much memory for reducing the chances + potentially very negative consequences of TT key collisions, have you tried something similar?
Other than that as an additional layer of safety maybe it's sufficient to verify that the stored hash move is also at least legal in a current node, but of course when analyzing positions which result from the same root node I suppose that it's also very likely that the same move is legal in many different positions which have this same root-node,
so this - again - could be mere luck that not only the Zobrist Key is identical but also the Hashmove is also legal in both positions, but nevertheless the position in the TT could be very different from a current node, although it's got the same Zobrist Key.
Thanks for any good tips of how to reduce the negative effects of Key Collisions, I'm also wondering how much of a speedup I could expect from my program if it used the TT not only for move ordering, but also for (apparent) Transposition-Forward-Pruning? What is a typical number for your own programs? 10%? 90%?
best wishes

[tpetzke]

Hi,

you have to type of collissions.

Type A: 2 different positions calculate the same zobrist key. This is not impossible but very very unlikely when using a 64 bit zobrist key. I've not encountered it so far.

You can check whether the hash move is legal, this improves collision detection. You can also calculate a 2nd zobrist key using different random numbers, but this is expensive and I think not really needed.

Type B: 2 different zobrist keys map to the same slot in the transposition table. This is very very likely and you must take care of that.

Easiest way to to that is to store the zobrist key of the position as part of the hash entry and before you do anything with the information you find in the hash you compare the zobrist key from the hash entry with the zobrist key of the board, if they don't match you have a collision and can't use that hash entry, not even for move ordering as you do at the moment, it seems.

Thomas...

[Desperado]

Hello Clemens,

well, at first the chance that you get a _real_ collision for a 64 bit key
should be negligible (with correct implementation).

especially including the fact that if a real collision occurs, the chance is
shrinking further that it does influence the search result.

So the proposed workarounds are indeed _not_ worth to handle real
collisions.

Most of the time people who get a too high collision rate have a bug
of the following type:

index: key64 % slotNumber
store:
- key64 % slotNumber WRONG
- key64 (complete) OK
- key64>>32 OK (n-bit identification,this case 32)

The chance that 2 different positions address the same slot is relative
high and if the identification code doesnt differ for 2 different positions,
then there are of course bug-collisions (with all the side effects you are faced with)

Now checking the transMove against the position is a good idea (imo),
although it should match with the position, it may/will fail in a collision case.
The consequences _can_ be much more drastical, because the
iternal board will be corrupted, or your program may even crash.
(rarely case, but it will happen sooner or later).
So my suggestion is, that moves that arent produced by move-generation
process (transMove,killerMoves...) should always be checked if they are really playable for the current position.

Just a little sth. , because you expressed yourself with "the score of the hash-move ".
The score belongs to the position, but not necessarily to
a move. You may think of a failHi situation, store a score+move.
Again at this position you failLo and keep the move. Now there is a move
and a score, but they do not necessarily correspond. (as i said, just a little
sth.)

Michael

[Sven]

I'm also wondering how much of a speedup I could expect from my program if it used the TT not only for move ordering, but also for (apparent) Transposition-Forward-Pruning? What is a typical number for your own programs? 10%? 90%?

I can't give numbers but clearly the effect of using the TT also for transpositions will increase towards the endgame. As an extreme example, the famous "Fine#70" pawn endgame test position is practically unsolvable in reasonable time without transpositions, whereas in many opening or middlegame positions you will see only a minor speedup. But as a rule of thumb I would say, using the TT for transpositions never hurts (if applied correctly so that problems like collisions do practically "never" occur) and almost always helps.

Regarding the tradeoff, the point is that for move ordering purposes you already do the TT lookup at every node (in full-width search at least, depending on your implementation). So the additional effort that is wasted on one side is only the effort to decide about TT-based pruning using the stored entry type, bounds, and age etc., which you compare on the other side against the saved effort for a successful TT lookup that you can use for pruning. I have not done exact measurements for this but my feeling is that saving already few hundreds of nodes with full move generation, qsearch and evaluation should easily outweigh many thousands of wasted (unsuccessful) TT pruning decision calculations. To know more about it requires testing; I have never put this in question, though.

Sven

[Clemens Pruell]

Yes, of course I store the full Zobrist Key in order to detect Type B (Index-) Collisions. It's only the Type A - collisions which seem to happen more often than one would think. What is worse with Type A collisons (in case they occur) they could possibly cause search instability, too (which would render my narrow-window search techniques pointless, if I got a score > beta, then did a research with (beta, +INF), and suddenly get a score < beta.
In theory it should be possible to construct a 'perfect' Hashing Function (instead of Zobrist Hashing) for every Node which can possibly occur from a given root node, shouldn't it?
It's not like every-possible & legal chess position could occur within the next, say, 9-plies, only a small subset of all possible chess position can occur in a deterministic way and due to the chess rules of piece movement (pawns can't move back, a captured pawn can't suddenly occur again later, there sure are billions of positions which may be legal, but couldn't possibly occur after a -known- root node during the following e.g. 9- or 10-plies)
In any case a 64-bit key should (in theory) be large enough to store every single possible position which can occur (due to the chess rules of piece-movement) within the next 9-plies, and a perfect Hashing Functions (really the only reliable way to avoid Type A Key Collisions) should exist.
The problem with the Zobrist Hash Function is, it's not a perfect hashing and hence many different positions can be mapped to the same 64-bit key. With all those negative impacts on a programs consistent playing strength. It may win 90% of it's games vs. the strongest opponents, but due to Zobrist key collsions it's also capable of blundering in such a horrible manner that it can also lose to opponents which are thousands Elo weaker.

Well, what's worth more: Overall playing strength and little impact of key collisions most of the time and in most games, or 'not-so-strong' in the average case but - however - consistent and reliable. Especially for analyzing chess games I'd personally prefer the consistent (== free of TT key collisions) program over the strong program (which may overlook some cheap combinations because of it's TT key collisions).

Well, maybe there really is some way of hashing chess positions perfectly to a 64-bit key (hence key collisions would be impossible, not
only 'unlikely') - although I couldn't find something with google so far.
Because there are at most 40^9 possible positions which can occur in a 9-ply-search tree of a given root node, they all should fit into a 64-bit Key in some (till now - unknown ?) unique manner.

Well, best thanks for your tipps, so maybe it's best to use a Zobrist Hash Function and act 'as if' there won't occur any Type A collsions. At least until someday a wise guy invents a perfect hash function (it must exist for the limited number of possible nodes which can occur - in a deterministic manner - after a given root node, however complicated this 'perfect hashing' function should be ...)

regards

[hgm]

I have seen papers by Bob where it was claimed that a few hundred thousand key collissions per search (say about 0.1% of all TT probes returning the score of a randomly chosen other entry) had virtually zero impact on the strength of the engine. So why bother? And if you are the really worrying kind, when you use 64-bit keys, and there isn't anything seriously wrong with them (like only the 15 low-order bits being non-zero, f.i.), you can expect one collision per 30,000 years.

Now things starts to become interesting when you get down to 40-bit keys. (e.g. 24-bit used for addressing, and a 16-bit signature stored in the hash. This gives you a 1 in 16k error rate, which is of course not contributing any Elo. But the fact that you can cram significantly more entries in the same size table might more than offset that.

[Clemens Pruell]

you can expect one collision per 30,000 years.

Thanks a lot, now that seems to be a really low chance of key collisions, so I'll use the TT for its primary purpose from now on
Big thanks.

[Desperado]

So, now there is one point that makes me headache ?
In your first post you stated

...because it seems to happen very often that two totally different positions get the same Zobrist Key...

later

...It's only the Type A - collisions which seem to happen more often than one would think...

and HGM said

...you can expect one collision per 30,000 years..

So, how old are you

Michael

[Clemens Pruell]

Just a little sth. , because you expressed yourself with "the score of the hash-move ".
The score belongs to the position, but not necessarily to
a move. You may think of a failHi situation, store a score+move.
Again at this position you failLo and keep the move. Now there is a move
and a score, but they do not necessarily correspond. (as i said, just a little
sth.)

Michael

Well, I've treated the score as a property of the hash move, reasoning behind this is: If this move is played, and I follow this variation until I'm at the same depth of the hashmove, I'll reach a leaf node with the same score which was listed together with the hash move. The only exception when the score is really more a property of the position and not so much a property of the hashmove are the leaf nodes.
Thanks to H.G. Muller! Now that I know that key collisions happen so incredibly rarely I'll re-use the scores of the leaf nodes, too (I hope this will save me a lot of (time-) expensive eval() calls ...).
Big thanks all of you here, you really helped me A LOT.
best wishes

[Clemens Pruell]

Well, I've read this paper about key collisions in the chessprogramming wiki and it said that crafty and zappa played a different root move 50% of the time, and even worse in endgames. Most of the time the 'different' root move wasn't really significantly worse than the 'correct' minimax move, and hence the impact of the TT key collision didn't matter. But on some (rare!) occasions the 'different' root move caused their programs to play a weak move, too. So under this impression I thought that key collisions are a real problem.
But thanks to H.G. Muller I've learned that the TT collisions only happens once every 30.000 years. So here is my problem, both, Prof. Hyatt and H.G. Muller are WAY more experienced chess programmers than I am, so what is correct and what should I believe?
Will the TT key collisions cause my program to play a different root move 50% of the time, or will this only happen once every 30.000 years (like H.G. Muller said)?
Very confusing, isn't it?
Well, I'll just try different degrees of TT-'safety' and (hopefully!) find what works sufficiently reliable + also fast enough for my case.

thanks & best wishes