Hash Collision?

[Fguy64]

I have encountered something unusual, I think. First of all, I have isolated the problem to the following conditions...

as I tinker with my program, one of the things I do for testing is run a set of 200 tactical poaitions, and check to make sure that the engine returns the same best move and evaluation as always, with the following parameters...

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

ok so with hash table disabled, I get the usual result, all positions are evaluated as always.

when hashing is turned on, for transposition checking only, I get maybe a 50% reduction in nodes, but anomalies are observed in three positions, in that the engine returns the same best move, but with a different evaluation.

The remaining 197 positions produce identical eval, with our without hashing.

So before I spend a lot of time investigating this, I thought I'd run it by the board, to see if this sort of thing is normal, or not.

regards.

[hgm]

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.

[Fguy64]

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?

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?

[jwes]

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.

[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.

[Fguy64]

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.

indeed! I tried it using only exact hash matches. The four original anomalous positions were resolved, to be replaced by one I hadn't seen before. Interestingly enough, the position was...

8/8/2Kp4/3P1B2/2P2k2/5p2/8/8 w - - 0 1 bm Bc8 Bd3 Bh3; id WAC.146;

[D]8/8/2Kp4/3P1B2/2P2k2/5p2/8/8 w - - 0 1

as an aside, switching to exact hash matches came at a cost of a 3.7% increase in processing time to run through the set.

[jwes]

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

[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...

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.

[jwes]

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?"

[hgm]

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.