Hash Collision?

[bob]

will do thanks.

Before I start on that, consider this...

The only place where an actual move is written to the table is at the end of alphaBeta, this is an exact write with the best move for the node. All the other writes (beta cutoff, depth=0), there is no move, just 0.

If this is correct, then we look at what I am doing with my hash move. Hash move automatically becomes the first best move for that node. Then I do the same as all other moves, which means an alpha update makes the hash type exact, and if the hash move causes a beta cutoff (I'm not even sure it is possible) then the existing table entry is overwritten with a 0 entry and a lower depth, like I do with all the other beta updates. Could the way I am handling the possibility of a hashMove causing a beta cutoff be the cause of the problem?

That isn't correct. If you are about to return beta, you have reached a beta cutoff, and there _is_ a move that caused this cutoff. That should be stored in the best move part of the entry. Simple test is always store a best move if alpha (best score found in this node's search) is > the original alpha value passed in to this instance of search(). If this is the case, then you have two possibilities.

(1) alpha >= beta, which means the move just searched caused a cutoff and should be saved.

(2) alpha < beta, which means the move stored in the PV array for this ply is the best move and should be saved.

Not that this has any effect on missing a forced mate of course.

[hgm]

The only place where an actual move is written to the table is at the end of alphaBeta, this is an exact write with the best move for the node. All the other writes (beta cutoff, depth=0), there is no move, just 0.

If this is correct, then we look at what I am doing with my hash move. Hash move automatically becomes the first best move for that node. Then I do the same as all other moves, which means an alpha update makes the hash type exact, and if the hash move causes a beta cutoff (I'm not even sure it is possible) then the existing table entry is overwritten with a 0 (move) entry and a lower depth, like I do with all the other beta updates. Could the way I am handling the possibility of a hashMove causing a beta cutoff be the cause of the problem?

As Bob says: this is not the correct way to handle hash moves. But hash moves should not have any effect to find the mates in a search of a given depth, just on the time it takes to find them. Provided the hash moves are legal moves, and don't mess up your move sorting in a way that makes you lose moves. All permutations of the move order should in the end give you exactly the same root score, in your fixed-depth search.

[bob]

The only place where an actual move is written to the table is at the end of alphaBeta, this is an exact write with the best move for the node. All the other writes (beta cutoff, depth=0), there is no move, just 0.

If this is correct, then we look at what I am doing with my hash move. Hash move automatically becomes the first best move for that node. Then I do the same as all other moves, which means an alpha update makes the hash type exact, and if the hash move causes a beta cutoff (I'm not even sure it is possible) then the existing table entry is overwritten with a 0 (move) entry and a lower depth, like I do with all the other beta updates. Could the way I am handling the possibility of a hashMove causing a beta cutoff be the cause of the problem?

As Bob says: this is not the correct way to handle hash moves. But hash moves should not have any effect to find the mates in a search of a given depth, just on the time it takes to find them. Provided the hash moves are legal moves, and don't mess up your move sorting in a way that makes you lose moves. All permutations of the move order should in the end give you exactly the same root score, in your fixed-depth search.

so long as you add the "and you are doing no extensions/reductions that are based on anything other than static criteria". If you use history counters to make LMR decisions, move ordering can change the score or even best move as two different orders will produce two different sets of history counters, and lead to different pruning/extension decisions...

As the search gets better, it becomes more unpredictable and produces more results that can't be reproduced.

[hgm]

so long as you add the "and you are doing no extensions/reductions that are based on anything other than static criteria".

Isn't that exactly what 'fixed-depth search' means? No reductions or extensions?

[Fguy64]

well, by fixed depth I mean no qSearch, plain ABP. I've never had any extensions or reductions or null move pruning or nything like that

anyways, as soon as I started writing moves for beta cutoff, as opposed to just writing 0 for the move, then failures increased three fold. Which is probably why I figured it was wrong to do so in the first place. So I suppose that tells us something about the nature of the problem. I'll be looking into it.

[bob]

so long as you add the "and you are doing no extensions/reductions that are based on anything other than static criteria".

Isn't that exactly what 'fixed-depth search' means? No reductions or extensions?

Not sure. It can mean "sd=n" where N only means something to a specific program. But within those N plies, there is a lot of freedom as to what is searched and what is not. Even simple null-move search introduces some oddities in an otherwise plain fixed-depth search.

[bob]

well, by fixed depth I mean no qSearch, plain ABP. I've never had any extensions or reductions or null move pruning or nything like that

anyways, as soon as I started writing moves for beta cutoff, as opposed to just writing 0 for the move, then failures increased three fold. Which is probably why I figured it was wrong to do so in the first place. So I suppose that tells us something about the nature of the problem. I'll be looking into it.

One thing is for sure. As HGM pointed out, a mechanism to dump the entire tree as it is searched is critical. If you can restrict the dump to only happen after a specific sub-PV, that's even better. But this is the best debugging tool you can write. Half of what you find will be real bugs. The other half of what you find will be real understanding when you realize that what you were seeing was not a bug at all, but a product of hashing in general.

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

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.

I've been thinking about your remark about it not being a problem. In an attempt to get to the bottom of the situation, I re-assembled my engine to include perft and hash key verification, and tested both till the cows came home. The issues were exactly the same.

ok, in the situation of vanilla abp, no qSearch, no iterative deepening, no hash moves, just transposition matching, and depth <= stored depth for the hash match.

consider the following position. Which is a mate in three.

[d]1B3k2/P2Q4/7p/8/P1N1B1p1/7b/7b/7K w - -

when I set the depth to 6, which is required to find a mate in 3 because the 6th ply is used to determine there are no legal moves, then my engine plays 1.Bd6 and returns a score of 9997, which is the normal score for a mate in two. A garbage PV is also displayed using the triangular approach. But the move leads to a mate in three. Now if I reduce the depth by 1 and have the engine make a black move, it plays 1...Bxd6 and returns a score of -9996, which means we are back into the correct score, and White now has a mate in two.

So the point is that in a normal game, an incorrect score might get returned, but the correct move still gets played. Is this what you mean by not a problem?

It makes me thing that in my batch job, I should measure a success as score >= expected score, not score == expected score.

[Fguy64]

never mind, when using depth <= stored depth the above position gets reported as a mate in 2 even when the depth is set to 4 , which is insufficient for a mate in 3.

sigh

[hgm]

If it reports mate in 2 when a mate in 3 is within the horizon, you have a bug. You cannot predict how harmfull that bug will be. I just debugged my new engine last week, and I had a similar problem, that turned to be due to cut-moves being removed from the move list in internal iterative deepening. (Because I wrote moves that gave cutoffs into the killer slots already in earlier iterations, so that the final iteration thought they were duplicates of the original killer moves, and skipped them.) This led to in-check positions that had only one or two evasions being classified as check-mate in the final iteration. In other situations it would not be obvious that something was wrong, except that it played a few hundred Elo weaker.

So trace the bug, and repair it.

Start by printing all moves & scores at ply=3 after 1.Bd6 Bxd6, to see how it thinks you will be checkmated in one in that position.

My new engine says this about the position:

Code: Select all

  1	+21.39	5	0:00.00	a7a8
  2	+21.86	106	0:00.01	a7a8 h2b8 a8b8
  3	+21.86	108	0:00.01	a7a8 h2b8 a8b8
  4	+319.97	722	0:00.02	b8d6 h2d6 a7a8 d6b8
  5	+319.97	750	0:00.02	b8d6 h2d6 a7a8 d6b8

It sees mate-in-3 already at 4 ply, while it currently also still needs the 6th ply to establish there are no legal moves. (i.e. it can stand pat while in check.) The reason is that you get an inexact-depth hash hit after Bd6-d8 on the position that was already searched after 1.a8=Q Bxd8 2.Qxd8#, which was the PV at 3 ply, (although it could not see it ws a checkmate there), and was thus searched as the first branch at 4 ply. There it was discovered that black was in fact checkmated, so it started to look for black alternatives. It then found a better black defense (presumably 1.... Bb7+), which pushed the mate again over the horizon, and then it tried a white alternative 1.Bd6+, which ended up in the graft.

The fact that you don't see a 5-ply PV at 5 ply is further evidence of the hash hit; this position was searched at d=1 in the 4-ply search, so the hit would still be valid for the 5-ply search. The hash cutoffs then cuts the PV (obtained through the triangular method) short.