Hash Collision?

[Fguy64]

If you get different result (move or score) with exct-depth hits, I would suspect a bug. I don't see how exact-depth TT hits could change a search result from doing the search.

Best way to test is probably to add a flag argument to Search to suppress TT writing, passed on to the daughters. In the root you start with TT writing allowed. As soon as you get a TT hit that would normally make you take a cutoff, you set that flag, and do the search anyway. So you in fact always do the complete search as if you had no TT at all, but you let the TT evolve as if you were doing hash cutoffs.

Then, if the search returns a bound that violated what was in the TT, there must be an error in that node, either during the current search, or the search that filled that entry.

Thanks. You know, I can't replicate the "problem". Which was a single position where a fixed depth search produced a different bestmove when hashing was turned on and off. Everything appears in order. I guess my testing methodology was not as rigorous as one would like.

You will note that the position above has several good moves by the bishop, whereby the bishop ends up being sacrificed for the advanced pawn, and White wins the pawn endgame. Perhaps the fact that thee are several best moves played a role, but like I said, my testing was not rigorous enough to prove the point.

[bob]

If you get different result (move or score) with exct-depth hits, I would suspect a bug. I don't see how exact-depth TT hits could change a search result from doing the search.

Best way to test is probably to add a flag argument to Search to suppress TT writing, passed on to the daughters. In the root you start with TT writing allowed. As soon as you get a TT hit that would normally make you take a cutoff, you set that flag, and do the search anyway. So you in fact always do the complete search as if you had no TT at all, but you let the TT evolve as if you were doing hash cutoffs.

Then, if the search returns a bound that violated what was in the TT, there must be an error in that node, either during the current search, or the search that filled that entry.

I believe the original suggestion was to use only exact-depth on EXACT entries, but use any valid depth for cutoffs? That will break even a simple search in terms of consistency.

[bob]

Are you acceptng exact-depth hits only, or also when the stored depth (draft) >= thn the currently requested search depth? In the latter case you can hve score changes due to grafting.

I am counting a hit as stored depth >= current remaining depth. So it sounds like that sort of thing is to be expected?

Yes, particularly in engames where zugzwang is involved. Try changing your code to only cutoff on = depth and see if the anomaly goes away.

It appears that another aspect of this situation is as follows.

Normally, for a fixed depth search, if you have the engine play both sides one move at a time, reducing the requested search depth by one ply at each half move, and clearing the hash table at each such reduction, then you can step through the original PV move by move, and the eval will be negated each time. However, for the anomalous positions, the PV changes part way through, and the eval changes at the same time. Furthermore, it appears that the differences happen at the beginning of the process, and then disappear as I step through the PV. Am I clear in what I am describing?

This sounds like what would happen if tree grafting were occurring.

This still won't "fix" the problem. It will make it occur less frequently, but hashing can always change the score or PV.

I don't follow. When would searching a position to a given depth return a different result from the last time that position was searched to that depth, given the conditions of the first post?

fixed-depth, no iterative deepening, no special pruning, just alphaBeta
qSearch disabled
material evaluation only

Do you clear hash after _every_ move played? Do you do extensions that are limited based on remaining depth? Pruning decisions based on alpha/beta bounds. There are a ton of things that let the hash graft branches from one part of the tree to another. Even with equal depths you can produce different scores or sub-trees, and then grafting takes those differences and lets them influence other parts of the tree.

I can't count the number of times I have debugged this problem, only to realize that it not a problem at all. I would never do the draft==depth "fix". Makes no sense at all to throw away good information and replace it with a search that is not free...

It's not a "fix", it is a test. If the problem goes away with this change, then it probably not worth debugging.

If you take only the simple search you described above, the problem may well not show up. But that's an unrealistic search. To expect things to remain the same is about as useful as expecting the Easter bunny. Just changing the hash size will quite frequently change the score, the time used, and even the best move for a given depth, because the replacement policy is another influence.

The question then becomes "How do you distinguish between a hash bug and ordinary hash weirdness?"

Don't have "hash bugs".

But this really is a fix for some. Several programs don't allow draft >= depth for exact entries, only draft == depth.

[Fguy64]

If you get different result (move or score) with exct-depth hits, I would suspect a bug. I don't see how exact-depth TT hits could change a search result from doing the search.

Best way to test is probably to add a flag argument to Search to suppress TT writing, passed on to the daughters. In the root you start with TT writing allowed. As soon as you get a TT hit that would normally make you take a cutoff, you set that flag, and do the search anyway. So you in fact always do the complete search as if you had no TT at all, but you let the TT evolve as if you were doing hash cutoffs.

Then, if the search returns a bound that violated what was in the TT, there must be an error in that node, either during the current search, or the search that filled that entry.

I believe the original suggestion was to use only exact-depth on EXACT entries, but use any valid depth for cutoffs? That will break even a simple search in terms of consistency.

for what itis worth, my understanding of the original suggestion was to use exact depth matches for all hits (alpha/beta/exact)

[Fguy64]

Well, I now have my iterative deepening running, and aside from a little grafting when using "inexact" depth matches, there is really only one weirdity that I can't explain, with the following position

[d]r4rk1/5ppp/p3q1n1/2p2NQ1/4n3/P3P3/1B3PPP/1R3RK1 w - -

now this position is mate in three, touch wood, starting with 1.Qh6

with my hash probes turned off, no problem. When hash probes are enabled, I have to set my fixed depth limit to the level required of a mate in four, then it proceeds to find the mate in three, without the running the remaining iterations. If I set the depth to the level normally required to find a mate in three, it doesn't get found.

All the other forced mate problems are found.

[Fguy64]

p.s. I'm running it through a file of 100,000 mate in three positions, and with iterative deepening with exact hash matches and fixing the number of iterations to that required to find a mate in three, my engine is failing on about one every 1000 positions. Failure meaning returning something other than a mate in three score.

[bob]

Well, I now have my iterative deepening running, and aside from a little grafting when using "inexact" depth matches, there is really only one weirdity that I can't explain, with the following position

[d]r4rk1/5ppp/p3q1n1/2p2NQ1/4n3/P3P3/1B3PPP/1R3RK1 w - -

now this position is mate in three, touch wood, starting with 1.Qh6

with my hash probes turned off, no problem. When hash probes are enabled, I have to set my fixed depth limit to the level required of a mate in four, then it proceeds to find the mate in three, without the running the remaining iterations. If I set the depth to the level normally required to find a mate in three, it doesn't get found.

All the other forced mate problems are found.

What search enhancements do you use, if any? Reductions? null-move? Any of those can hide a mate for a couple of iterations. What about extensions?

One thing is for sure, that tree should be small enough that you can print it out to see why the mating sequence is either not being searched, or is not detecting the mate.

[bob]

p.s. I'm running it through a file of 100,000 mate in three positions, and with iterative deepening with exact hash matches and fixing the number of iterations to that required to find a mate in three, my engine is failing on about one every 1000 positions. Failure meaning returning something other than a mate in three score.

If you can email me the positions, I'll run 'em thru Crafty, for some minimal fixed depth, to see if I see any issues. Crafty should be able to see any mate in 3 with a 4 ply search since it does q-search checks. If all 3 moves are checks, it would only need 2 plies I think. I can at least try 4 plies and see if any mates are missed.

[Fguy64]

Well, I now have my iterative deepening running, and aside from a little grafting when using "inexact" depth matches, there is really only one weirdity that I can't explain, with the following position

[d]r4rk1/5ppp/p3q1n1/2p2NQ1/4n3/P3P3/1B3PPP/1R3RK1 w - -

now this position is mate in three, touch wood, starting with 1.Qh6

with my hash probes turned off, no problem. When hash probes are enabled, I have to set my fixed depth limit to the level required of a mate in four, then it proceeds to find the mate in three, without the running the remaining iterations. If I set the depth to the level normally required to find a mate in three, it doesn't get found.

All the other forced mate problems are found.

What search enhancements do you use, if any? Reductions? null-move? Any of those can hide a mate for a couple of iterations. What about extensions?

One thing is for sure, that tree should be small enough that you can print it out to see why the mating sequence is either not being searched, or is not detecting the mate.

no special enhancements at all, just plain alphabeta. Anyways, It's gonna take me some time to write some proper diagnostics to deal with this. So it may be a little while before I have anything more to say on this topic, but I'll keep an eye on the thread.

[hgm]

p.s. I'm running it through a file of 100,000 mate in three positions, and with iterative deepening with exact hash matches and fixing the number of iterations to that required to find a mate in three, my engine is failing on about one every 1000 positions. Failure meaning returning something other than a mate in three score.

These could be genuine key collissions. You would not expect those that frequently, but there could be something wrorng with your keys (e.g. an accidental low-order dependency) that increases the probability above normal, or there could be a bug in your probing code.

If I were you, before trying any other thing, I would check for that. An efficient way to check it would be to calculate a completely independent hash key next to the one you are using now. (Speed is no issue, so calculate it from scratch in every node, e.g.

Code: Select all

u64 key2 = 0;
for(sqr=0; sqr<64; sqr++) key2 = 2*key2+board[sqr];

(assuming you have an array board that stores piece types), and store that key2 in an extra 64-bit field of you hash entry. (You could store the entire board, but that would probably bloat the table by more than you can afford).

On has hits according to your normal procedure, you then also compare if this key2 matches, and if it doesn't, you can print an error message with the number of the hash entry and the value of the keys. If this does not happen during the faulty search, you can be pretty sure that key collissions are not the problem.

If you do detect a collision, then in a second test you can have the program print out the full board and keys every time that hash entry is written or gets a probe hit. That should reveal which two different positions would give rise to the same hash key.

It should be possible to get this verdict in 5 min of work.