Search inaccuracy, repetitions, and TT

[odomobo]

I wanted some feedback on some thoughts I had. This is all theoretical at this point. My premise is:

1. One form of search inaccuracy comes from a path-dependent score being used directly from the TT when the path-dependency cannot be proved. That is, we know we arrived via different paths when we find a transposition, so repetitions can happen in different ways.
2. Repetitions rarely significantly influence TT entries.
3. TT entries are already slightly invalid (due to path-dependency and repetitions), so if we make them consistently slightly invalid, it should not weaken search strength.

Proposal: never store a score in the TT when it contains path-dependent information. One way to do this is to split the search tree by depth - let's call positions close to the root "shallow positions" and positions close to leaves "deep positions". Deep positions would no longer check for repetitions*, and would store scores in the TT. Shallow positions would still check for repetitions, but would never store score in the TT, and those entries would only be used for move ordering.

My concern with the current approach is that it leaves engines unpredictably blind to search inaccuracy from path-dependency. My proposal would make it predictably blind, which could potentially be improved with heuristics.

* deep positions could check for repetitions in the real game history, just not within the search tree. The real game history is fixed, so there is no path-dependency for such checks.

[federico]

I wanted some feedback on some thoughts I had. This is all theoretical at this point. My premise is:

1. One form of search inaccuracy comes from a path-dependent score being used directly from the TT when the path-dependency cannot be proved. That is, we know we arrived via different paths when we find a transposition, so repetitions can happen in different ways.
2. Repetitions rarely significantly influence TT entries.
3. TT entries are already slightly invalid (due to path-dependency and repetitions), so if we make them consistently slightly invalid, it should not weaken search strength.

Proposal: never store a score in the TT when it contains path-dependent information. One way to do this is to split the search tree by depth - let's call positions close to the root "shallow positions" and positions close to leaves "deep positions". Deep positions would no longer check for repetitions*, and would store scores in the TT. Shallow positions would still check for repetitions, but would never store score in the TT, and those entries would only be used for move ordering.

My concern with the current approach is that it leaves engines unpredictably blind to search inaccuracy from path-dependency. My proposal would make it predictably blind, which could potentially be improved with heuristics.

* deep positions could check for repetitions in the real game history, just not within the search tree. The real game history is fixed, so there is no path-dependency for such checks.

Check for path dependent conditions such as repetitions or 50 move rule before probing the TT.
E.g, If a rep is found , then return a draw score before even probing the TT.

here's a not so long ago thread with a similar premise: forum3/viewtopic.php?f=7&t=77718&hilit= ... 10#p902812

[odomobo]

Check for path dependent conditions such as repetitions or 50 move rule before probing the TT.
E.g, If a rep is found , then return a draw score before even probing the TT.

here's a not so long ago thread with a similar premise: forum3/viewtopic.php?f=7&t=77718&hilit= ... 10#p902812

Checking the topic, I don't think Sven understood the situation that Henk was trying to explain.

Imagine the following: deep in the search tree, it's white to move in a hopelessly lost position. However, the first move in the movelist causes a draw by repetition, because that position was repeated internally in the search tree. That causes the current position to evaluate as a draw, which gets stored in the TT (the current position isn't itself a repetition). Later in the search tree, the position is found again, and its TT score (a draw) is returned. However, this position isn't really a draw, because the first move is no longer a draw. The position should actually be losing.

More generally, if any children of the current position have path-dependent information, then the current score is also potentially path-dependent.

[federico]

Check for path dependent conditions such as repetitions or 50 move rule before probing the TT.
E.g, If a rep is found , then return a draw score before even probing the TT.

here's a not so long ago thread with a similar premise: forum3/viewtopic.php?f=7&t=77718&hilit= ... 10#p902812

Checking the topic, I don't think Sven understood the situation that Henk was trying to explain.

Imagine the following: deep in the search tree, it's white to move in a hopelessly lost position. However, the first move in the movelist causes a draw by repetition, because that position was repeated internally in the search tree. That causes the current position to evaluate as a draw, which gets stored in the TT (the current position isn't itself a repetition). Later in the search tree, the position is found again, and its TT score (a draw) is returned. However, this position isn't really a draw, because the first move is no longer a draw. The position should actually be losing.

More generally, if any children of the current position have path-dependent information, then the current score is also potentially path-dependent.

I think Sven understood very well, and i believe he explained it much better than i could. but i 'll give it a shot!

On a losing game, if the score returned is a draw because the position was played before at least once, it is likely that the move would be the stored in tt as it would the new best move. Also, it is likely that the engine would play that move, trying to pull a draw out of a lost game. Playing this move, would mean the position is met twice in the real game. (You can set a threshold here to let the engine know when is it worth trying to get to a draw, maybe based on a min moves to avoid reps early in the game and/or score based. e.g if moves > 30 and score < -50cp)

Later in the search, if the above move was played and then again the same position is reached again, the same outcome is expected. A TT draw score is _Not_ returned becuase , again, the engine should check for reps _Before_ probing. And the rep check would again return a draw. if the draw score is returned from tt or rep makes no difference. in other words, it would be the exact same behaviour as the paragraph above, with a tt draw score stored in tt or not.

Given that it would already be the 3rd time the same position is met by now, it truly is a draw if the move is played. given that it is losing it is actually likely that it is the best move to play.

It is up to you if you want your engine to return a draw after the same position is found twice or thrice. the latter is perhaps more accurate from a chess rules perspective if you will, but practically , this is an Elo loss in Ceibo. Which makes sense IMHO based on what i explained above.

[koedem]

I wanted some feedback on some thoughts I had. This is all theoretical at this point. My premise is:

1. One form of search inaccuracy comes from a path-dependent score being used directly from the TT when the path-dependency cannot be proved. That is, we know we arrived via different paths when we find a transposition, so repetitions can happen in different ways.
2. Repetitions rarely significantly influence TT entries.
3. TT entries are already slightly invalid (due to path-dependency and repetitions), so if we make them consistently slightly invalid, it should not weaken search strength.

Proposal: never store a score in the TT when it contains path-dependent information. One way to do this is to split the search tree by depth - let's call positions close to the root "shallow positions" and positions close to leaves "deep positions". Deep positions would no longer check for repetitions*, and would store scores in the TT. Shallow positions would still check for repetitions, but would never store score in the TT, and those entries would only be used for move ordering.

My concern with the current approach is that it leaves engines unpredictably blind to search inaccuracy from path-dependency. My proposal would make it predictably blind, which could potentially be improved with heuristics.

* deep positions could check for repetitions in the real game history, just not within the search tree. The real game history is fixed, so there is no path-dependency for such checks.

I had a similar idea recently that I posted about elsewhere, sadly got no replies but let me try again and just copy paste it here.

So, what if we don't return after the first repetition but instead keep going, noting down this first repeated position. Eventually we may repeat the position again, in which case we evaluate it as draw_score due to 3fold-rep. Now, as we back that score up, it might of course be influenced by the upcoming repetition, so we can at most store an appropriate bound. (so if we are +1 despite a repetition, that +1 can only be a lower bound, not an upper bound) So we now lose out on some possible TT information, but we would not be sure of that information. As we keep backing up, it might happen that the repetition is no longer relevant. That is (at least?) when the weaker side deviates away from the repetition line. Or, we eventually reach the position where we repeated the first time. From this position, the "attacking" player had a playing field free of repetitions to consider, so from now on we can treat this as an exact score (or bound, depending on our window). We can now back up further as normally.

Now, if the position is actually a perpetual, then the exact backed up score would still be 0, since there is no good way to deviate. If it isn't, then there is a winning line that does not involve that repetition, so we would have found that one.
We might at the point of the first repetition back up some eval - epsilon so that a variation not involving that first repetition in the first place, would get a better evaluation comparatively.

Now, where I see this breaking is when we probe the TT after that first repetition and get an incorrect score, not achievable in that position in the tree. However, from the first repetition position whatever winning line it is could be played some way, so backing up that score is not necessarily incorrect, so long as we don't store anything in the TT incorrectly. (which I think we would not? If we do, we could change the scheme to never store anything after the first repetition; this reduces the effectiveness of the TT, but those repeated positions should be rare anyway) Now, we would have to be careful there to choose the correct move in that first repetition line, but that should be possible. (at the latest, when this position becomes root, and we notice our root position is one that happened before, we can check for this specifically; before then, just backing up a correct score would be good enough presumably)

There are some more details to be weary of, but could an approach with an idea like this work? (possibly at the cost of performance) (edited)

[Desperado]

...

My concern with the current approach is that it leaves engines unpredictably blind to search inaccuracy from path-dependency. My proposal would make it predictably blind, which could potentially be improved with heuristics.

...

You won't get a path independent search anyway. All the selectivity stuff and heuristics are influenced too.

And i don't mean the inaccuracy because of the nature of selectivity. I mean the attributes of the tree state like...

E.g.: the history heuristic will have a different state. The heuristic depends on the nodes it has already visited. (path dependency).
In genenral i would say you you won't get the same node with the same characteristics even when you change the order.

There are many more factors than the repetition status of a node which depend on the paths.

[odomobo]

In genenral i would say you you won't get the same node with the same characteristics even when you change the order.

This is a good argument. However, most heuristic algorithms try to protect against pathological cases. For example, disabling NMP in positions that might have zugzwang, or re-searching with full depth if LMR produces a cutoff. In my mind, it's prudent to try to prevent storing scores in the TT which have been influenced by path-dependent repetition.

Then again, my algo is kind of a nuclear approach, which I suspect causes more harm than good. Here diep posted an approach to solving the problem, but I wasn't initially on board with the idea: forum3/viewtopic.php?f=7&t=78505&sid=14 ... 03f202fd1c

After thinking about it, I think diep's approach is a good one.

Maybe pathological cases are rare enough to not matter, but I might try to hack diep's approach into stockfish and see if I find any benefit (or harm).