Handling 3-rep/50-move in hash tables

[Pradu]

Although the same position cannot occur twice, the move history is different for each and therefore the drawing moves and the depths are different. Eg, you do a 7 ply search and it is not a draw, but under a differenet move history, it is a draw for 3 ply search depth. When you reach the node and tt_depth>=depth, it will be assumed as not draw because the hash entry of depth 7 says it is not a draw, which is incorrect. For some reason I have a hunch there is more to updating bounds than just path history because path history bugs remain whether you update bounds or not.

I am not sure we are communicating. Both in the 7 -ply search as in the 3-ply search, (and in fact in any search) the position will be a draw, because it already occured twice in the game.

Lets say our goal is to reach this:
[diag]8/8/8/2p5/2k5/8/3K4/8[/diag]
Black To Move

from this
[diag]8/8/8/2p5/2k5/8/2K5/8[/diag]
White To Move.

This can either be achieved by 1. Kd2 or by 1. Kc1 Kc3 2. Kd1 Kb3 3. Kc1 Kb4 4. Kd1 Kb5 5. Kc1 Kb6 6. Kd1 Kc6 7. Kc1 Kd6 8.
Kd1 Kd5 9. Kc1 Kd4 10. Kd1 Kc4 11. Kd2 . Lets say do the first path first and we search 2 ply and it gets a score of +1.59 for black. Lets say now we reach the second path, white can force a draw for any 2 ply search according to the move history. From earlier there is a hash table entry that had +1.59 for black and it will be mistakenly used if path history is not concidered....but any 2 ply search from the new move history of the second says it is a clear forced draw from white.

[H.G.Muller]

I still don't follow. Along the long path, the positio is won for black after the first two moves, but 3. ..., Kb4 draws it. Not along this path, though, as 4. Kd1 give away the game again.

The search will discover all that, as it will not only try this branch, but also those where white properly defends. The return of the black King to c4 while the white King is on d1 is still a draw. White has the choice between playing 11. Kc2, which draws, and the 11. Kd2 you show, which leads to a position that has a hashed score of +1.59 for black. The move that draws will probably also have score ~-1.5, as it is no repetition, and thus is not recognized as a draw.

So by fooling around like this, black will preserve its 159 cP advantage, but never get much more. While there are plenty of 21-ply branches after 1. Kc1 that would lead to a much much higher score for black (like +950) without white being able to prevent it.

I don't see what is the problem is.

[Pradu]

I still don't follow. Along the long path, the positio is won for black after the first two moves, but 3. ..., Kb4 draws it. Not along this path, though, as 4. Kd1 give away the game again.

The search will discover all that, as it will not only try this branch, but also those where white properly defends. The return of the black King to c4 while the white King is on d1 is still a draw. White has the choice between playing 11. Kc2, which draws, and the 11. Kd2 you show, which leads to a position that has a hashed score of +1.59 for black. The move that draws will probably also have score ~-1.5, as it is no repetition, and thus is not recognized as a draw.

So by fooling around like this, black will preserve its 159 cP advantage, but never get much more. While there are plenty of 21-ply branches after 1. Kc1 that would lead to a much much higher score for black (like +950) without white being able to prevent it.

I don't see what is the problem is.

I just used that fooling around as an example, I know it isn't rigorous to the actual game (assume that the moves played are the only legal moves posssible then it'll make sense I think). Formulating a rigorous short 3-rep path dependency example without game history will be very complicated (other than just printing out an entire search trace here). Anyways I've decided the gains in many positions are close to none and therefore will probably not bother updating bounds.

[H.G.Muller]

Well, as you already remarked, updating the bounds won't make the repetition problem go away. The latter is purely caused by storing scores in the hash that were contaminated by path-dependencies. The only way to get rid of it is (1) either not storing contaminated scores, or (2) not using a score found in the hash for any purpose whatsoever (which would raise the question why you store it in the first place...).

As I explained, method (1) is fairly easy to implement.

The problem I have with your examples is that I have not the slightest idea what they are supposed to be examples of. We are discussing 3-fold repetitions, and you give an example of a very long path that does not contain any repetition whatsoever, but simply ends on a position that was put in the hash table by the search of another branch, not on the current path. If this causes problems, they are general to hashing, and have nothing to do with handling repetitions...

[Pradu]

Well, as you already remarked, updating the bounds won't make the repetition problem go away. The latter is purely caused by storing scores in the hash that were contaminated by path-dependencies. The only way to get rid of it is (1) either not storing contaminated scores, or (2) not using a score found in the hash for any purpose whatsoever (which would raise the question why you store it in the first place...).

As I explained, method (1) is fairly easy to implement.

IMHO, every score in the hash table without path history information is contaminated . I've tried using exact draft and this doesn't work either. I think the effectiveness of the hash table in position with many repetitions goes down if one also takes into account path history.

The problem I have with your examples is that I have not the slightest idea what they are supposed to be examples of. We are discussing 3-fold repetitions, and you give an example of a very long path that does not contain any repetition whatsoever, but simply ends on a position that was put in the hash table by the search of another branch, not on the current path.

Discussion of 3-rep occurs after the same path has been reached again. Eg: in the second path any 2 ply search is a forced draw whereas in the first path this is not so.

If this causes problems, they are general to hashing, and have nothing to do with handling repetitions...

Yes I agree this is a general problem to hashing. Repetitions and fifty-move which are path dependent affect this. Perhaps a generic fifty-move example would be clearer. Take a position with the fifty counter at 90. You do a 6 ply search at that position and get a non-draw score. Then take the same position at fifty counter 98. The transposition table entry for the 6 ply search cannot be used here accurately.

[H.G.Muller]

Exact draft doesn't solve the path-dependence, although it might be good for removing most other search instability. Performs worse, though, as it avoids the instability by passing back results that are already known to be wrong, just to maintain the appearance of consistency.

Like you say, path-specific hashing nearly completely destroys the usefulness of hashing. So the next-best thing you can do is hash the score that is most generally useful. And that is the score the node would have with the path-history completely cleared, like the 3-fold repetition rule did not exist. Note that this is theoretically completely sound: draws would still be draws if the 3-fold repetition rule would be replaced by any N-fold repetition rule, which could be effectively removed by taking N towards infinity.

It is just that at finite search depth, pure minimax fails to recognize branchess that make no progress. (This holds as much for branchess where you are constantly checked, but have so much lattitude in manoeuvring that that you never get any repetitions within the horizon. They can't be reduced to a quiet position within a resonable number of moves.)

So you should forget about the 3-fold rep rule, and focus on the search recognizing nodes from which no progress is possible to a position where the static evaluation is meaningful. The PV returning to a position occurring earlier in the path is a strong hint that the eval, or any prior result from a less deep search (not enough to span the depth between the two occurrences) cannot be trusted at all, but should be in fact replaced by a draw score.

But it should not be replaced by a draw score because it happened to occur in the path before. It should only be scored a draw if a return to this position is forced, in the sense that attempts to break out of the repetition for either side leads to scores that are worse for them than the draw score. For such positions, you should substitute the draw score for the evaluation or for a finite-depth search score. And for such positions that is not contamination at all, so you can safely store that draw score in the hash.

This is why I trigger on the third tree repetition only: between the first and the second occurrence the search goes for the best eval. The fact that it hits a repetition gives it a hint that the eval might not be reliable. So it redoes the search (in practice starting from the second occurrence, but they are identical anyway), now based on the assumption that the score of this node will be a draw when it returns to it.

Now if that still makes it the best option for both sides, it really is a draw. But it is quite possible that the side that has the advantage can break out of the repetition by sacrificing some material, and still be better off as with a draw (but worse than with the eval of the repeating position). That would then become the new PV after re-evaluation of the third repetition node as a draw. And this would lead to a score of the second occurrence different from both a draw and the evaluation. That score goes in the hash table. This now should be the same score as the first occurrence will receive, but you return it at the level of the second to allow it to properly affect the scores of the intervening nodes.

This really keeps the hash completely free of path-dependence.

[Pradu]

It seems these bugs become easier to spot in an MTD(f) search. Try SOS v51:

8/8/8/8/2k5/1p6/8/1K6 b - - 0 1
99 +2.31 4.9M 0:03.50 Kb4 Kb2 Kc4 Kb1
98 +2.31 4.8M 0:03.44 Kb4 Kb2 Kc4 Kb1
97 +2.31 4.7M 0:03.38 Kb4 Kb2 Kc4 Kb1

I came about with some similar problems in Buzz even with regular old PVS without bounds updating (although I can't reproduce it here now because they occur in games with pondering on). So far I haven't had any problems with regular alphabeta but I'm not 100% sure if problems could occur with even regular alphabeta.