Move repetitions in tree search + transpositions

[koedem]

A few people are working on an improved version of Leela's search right now which allows better exploration and among other things transposition handling. In practice that would just be a search tree in memory as usual, however different positions' child node pointers might point to the same node if the moves transpose into each other. (and then pointers in the children back to the various parents for evaluation backup)
The tldr of why the eval is still accurate is that with increasing number of visits the evaluation of the best scoring child gets weighted much more strongly than of the alternatives. (this should seem logical, as this basically converges more quickly towards minimax than the plain PUCT of AlphaZero does) So if a child has "too many visits" because of a transposition elsewhere it still won't ruin the eval accuracy. (details can be found here https://github.com/LeelaChessZero/lc0/pull/963 )

However as always with transposition stuff this raises the question how to deal with repetitions which obviously depend on the path how you got to a node. Any thoughts on what should be done here?

[noobpwnftw]

Very simple:
1. Only the path of globally shortest occurrence of a node gets the right to explore its child.
2. On other occasions treat it as a terminal node and adjust the score locally if the path indicates a repetition.

Your search is breadth first, if you get to a node with a longer path, then you've got there wrong.

[koedem]

I don't quite understand...

Very simple:
1. Only the path of globally shortest occurrence of a node gets the right to explore its child.
2. On other occasions treat it as a terminal node and adjust the score locally if the path indicates a repetition.

But what if the shortest path doesn't want to expand it because the shortest path included an opposition mistake which gives us a much better option to focus on? But in the main line where this position shows up later this is the main move which we want to expand a lot?

Your search is breadth first, if you get to a node with a longer path, then you've got there wrong.

Here I once again don't understand. Why would the search be breadth first? For reference, when analyzing the starting position Leela looks at 1.e4 e5 2.Nf3 Nc6 3.Bb5 Nf6 4. 0-0 Nxe4 etc. first before spending a single node on e.g. 1.h3 .

[noobpwnftw]

But what if the shortest path doesn't want to expand it because the shortest path included an opposition mistake which gives us a much better option to focus on? But in the main line where this position shows up later this is the main move which we want to expand a lot?

Well that is contradicting:
How can the main line leads to a position that is worth exploring, while for the shortest line of reaching the same position, your opponent has to make a mistake? If that is the case then either the non-mistaken line refutes your main line or there wasn't a mistake after all.

Here I once again don't understand. Why would the search be breadth first? For reference, when analyzing the starting position Leela looks at 1.e4 e5 2.Nf3 Nc6 3.Bb5 Nf6 4. 0-0 Nxe4 etc. first before spending a single node on e.g. 1.h3 .

If you get to a position with a long line while the same position is known to be reachable(which is not necessarily the ground truth, but your search tree told you that) with a shorter line, by the same principle of only exploring "good moves", then you should probably explore it from the short one first because if it holds, then all the assumptions that the opponent will follow you with that long line would be false.

[koedem]

But what if the shortest path doesn't want to expand it because the shortest path included an opposition mistake which gives us a much better option to focus on? But in the main line where this position shows up later this is the main move which we want to expand a lot?

Well that is contradicting:
How can the main line leads to a position that is worth exploring, while for the shortest line of reaching the same position, your opponent has to make a mistake? If that is the case then either the non-mistaken line refutes your main line or there wasn't a mistake after all.

How is that contradicting? First they make a mistake then you make a mistake back to get to the position. Since your move was a mistake it will hardly be expanded since the better alternative for you would actually be winning.

Here I once again don't understand. Why would the search be breadth first? For reference, when analyzing the starting position Leela looks at 1.e4 e5 2.Nf3 Nc6 3.Bb5 Nf6 4. 0-0 Nxe4 etc. first before spending a single node on e.g. 1.h3 .

If you get to a position with a long line while the same position is known to be reachable(which is not necessarily the ground truth, but your search tree told you that) with a shorter line, by the same principle of only exploring "good moves", then you should probably explore it from the short one first because if it holds, then all the assumptions that the opponent will follow you with that long line would be false.

That's not what I meant, I questioned the breadth firstness here. What if I get to the position with a long line first and expand it a bunch, then hit it with a shorter line?

[noobpwnftw]

How is that contradicting? First they make a mistake then you make a mistake back to get to the position. Since your move was a mistake it will hardly be expanded since the better alternative for you would actually be winning.

If this ever occurred then apply rule #2 and move on?

That's not what I meant, I questioned the breadth firstness here. What if I get to the position with a long line first and expand it a bunch, then hit it with a shorter line?

Also apply rule #2 and for the longer lines, only when your shorter line hits the node for you to expand it.

This doesn't work with A/B but it is totally fine with MCTS.

[koedem]

How is that contradicting? First they make a mistake then you make a mistake back to get to the position. Since your move was a mistake it will hardly be expanded since the better alternative for you would actually be winning.

If this ever occurred then apply rule #2 and move on?

I still don't understand how that would help. In this exact scenario the position would get expanded way too little. Just to plug in some random numbers to make the point. Let's say you want to spend 10 million nodes on the equal root position. So you have the good root move and a bunch of bad ones. (among them the short path to position P) Then that bad move might get 10K of these nodes. Then the counter blunder which throws the advantage away again and leads to equal position P might get only some 100 nodes. So P would only get visited + expanded 100 times from there.
Now in the main line that might maybe hit the position P after 4 plies i.e. longer path to it. Then you'd want to spend millions of nodes on expanding the node however you treat it as terminal so you are stuck at only 100 nodes.

EDIT: Or do you mean we still expand it when the main line wants, but pretend the move history was from the shorter line so to speak?

[koedem]

That's not what I meant, I questioned the breadth firstness here. What if I get to the position with a long line first and expand it a bunch, then hit it with a shorter line?

Also apply rule #2 and for the longer lines, only when your shorter line hits the node for you to expand it.

This doesn't work with A/B but it is totally fine with MCTS.

So the shortest line should change in that case? Let's say we first look at the line 1.Nf3 Nf6 2.Nc3 Nc6 3.d4 Nb8 4.Nb1 and hit this position for the first time here. Currently this is the shortest path to the line we found so we can expand it. Now later we find the line 1.d4 Nf6 2.Nf3 and realize this line is shorter. Does this line then "take over" the right to expand this node? What happens to the expansions of the old line? The old line might have given the follow up 4...Nc6 5.Nc3 a repetition draw since that at the time was true but for the shorter line isn't anymore.

[noobpwnftw]

Or do you mean we still expand it when the main line wants, but pretend the move history was from the shorter line so to speak?

It is not a depth-first search, you do not need to always expand main line nodes to make progress, the search progresses by increasing overall expansion rate and that improves the quality of weighted average score, not just depth.

Does this line then "take over" the right to expand this node? What happens to the expansions of the old line? The old line might have given the follow up 4...Nc6 5.Nc3 a repetition draw since that at the time was true but for the shorter line isn't anymore.

The shortest known line takes over the right to expand, the old line then would not expand it anymore(even if it does, it pollutes the results with some non-existing repetitions given its longer move history).

What will happen with your given situation is that the saved score by the time you visit this node from the shorter path, you would get a wrong draw score from previous long line's history, which is no longer the case and should be expanded as your search sees fit.

The save is you now use the best-known judgement of repetitions(in your cached results), search still judges repetition on-the-fly, and not going for full history-based caching(which basically will have to re-evaluate every time you go to this node with a different path). The catch is you may find some nodes under-expanded when the main line is quite long, but then again the search is not depth-dependent, so it shouldn't affect your result quality(if not improving by not wasting time on chasing ghost).

[koedem]

Or do you mean we still expand it when the main line wants, but pretend the move history was from the shorter line so to speak?

It is not a depth-first search, you do not need to always expand main line nodes to make progress, the search progresses by increasing overall expansion rate and that improves the quality of weighted average score, not just depth.

There has to be a misunderstanding here, of course other lines will be explored too, I am worried that the main line can't be expanded anymore. To prevent misunderstandings let me give a concrete example:
[pgn] [FEN "3r2k1/5ppp/8/8/8/8/5PPP/2R3K1 w - - 0 1"] {[#]} 1. Rc7 $4 (1. Re1 Kf8 2. Kf1 Re8 3. Rc1 Rd8 4. Rc7) 1... Kf8 $4 (1... Rd1#) 2. Kf1 * [/pgn]
Let's say we start with the line here 1.Rc7 Kf8 2.Kf1 to get to position P. Then we realize 1...Rd1# actually wins for Black so we discard 1.Rc7 and never look at it again. Our new main line then may be the 1.Re1 line which after 4.Rc7 transposes to P. Now we can never ever expand P and are stuck with the main line ending there forever, since there can not be a shorter line to gain the right to expand from that original 1.Rc7 line.