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?
Move repetitions in tree search + transpositions
Moderators: hgm, Rebel, chrisw
-
- Posts: 105
- Joined: Fri Mar 18, 2016 10:45 pm
-
- Posts: 560
- Joined: Sun Nov 08, 2015 11:10 pm
Re: Move repetitions in tree search + transpositions
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.
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.
-
- Posts: 105
- Joined: Fri Mar 18, 2016 10:45 pm
Re: Move repetitions in tree search + transpositions
I don't quite understand...
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?noobpwnftw wrote: ↑Tue Oct 22, 2019 2:20 am 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.
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 .Your search is breadth first, if you get to a node with a longer path, then you've got there wrong.
-
- Posts: 560
- Joined: Sun Nov 08, 2015 11:10 pm
Re: Move repetitions in tree search + transpositions
Well that is contradicting:koedem wrote: ↑Tue Oct 22, 2019 3:51 am 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?
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.
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.
-
- Posts: 105
- Joined: Fri Mar 18, 2016 10:45 pm
Re: Move repetitions in tree search + transpositions
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.noobpwnftw wrote: ↑Tue Oct 22, 2019 4:08 amWell that is contradicting:koedem wrote: ↑Tue Oct 22, 2019 3:51 am 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?
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.
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?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 wrote: 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 .
-
- Posts: 560
- Joined: Sun Nov 08, 2015 11:10 pm
Re: Move repetitions in tree search + transpositions
If this ever occurred then apply rule #2 and move on?
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.
-
- Posts: 105
- Joined: Fri Mar 18, 2016 10:45 pm
Re: Move repetitions in tree search + transpositions
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?
Last edited by koedem on Tue Oct 22, 2019 4:03 pm, edited 2 times in total.
-
- Posts: 105
- Joined: Fri Mar 18, 2016 10:45 pm
Re: Move repetitions in tree search + transpositions
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 wrote: ↑Tue Oct 22, 2019 4:58 amAlso 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.
-
- Posts: 560
- Joined: Sun Nov 08, 2015 11:10 pm
Re: Move repetitions in tree search + transpositions
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.
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).
-
- Posts: 105
- Joined: Fri Mar 18, 2016 10:45 pm
Re: Move repetitions in tree search + transpositions
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:noobpwnftw wrote: ↑Tue Oct 22, 2019 9:31 pmIt 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.
[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.