shinbet
commented
5 years ago I don't think your analysis is correct... you say 'She finds so many of these incorrect continuations' - but those are correct continuations! there is a possibility she can escape the draw... at least that is her hope. The problem is that there are so many permutations and there is always another path that opens up another huge branch.
The reason SF find it is probably because it prunes traspositions better and it is so much faster. On my laptop it took it a few seconds to get to 0.00. meaning probably a few million nodes. This is a good test for my transposition pruning test... but it probably still has way too many permutations for it to help leela
TesseractA
Videodr0me
mooskagh
RedDenver
oscardssmith
EDIT: I have clarified this post so that others can see what I'm seeing in this post, particularly in the section with the visuals. EDIT2: I have made another discovery as of April 13th with the assistance of Faroe22 on the Leela discord. The problem is not a pure MCTS problem, but indeed it is also tied to the neural network's Q values. See my new comment down below. Hello, the following FEN is a 6-man position evaluated incorrectly by Lc0, no matter what neural network you use (really, all neural networks fail.). I had careless25 on the lczero discord test a 6-man position and another very similar 7-man position. Lc0 as an engine could not evaluate it as a draw. I finally have a concrete hypothesis as to what the problem is, and a guide for 2 proper solutions to fix it. (Certainty propagation does not fix this.)
7k/1RR4P/8/8/3K4/3r4/8/8 w - - 0 1
The perpetual stalemate threat is supposed to prevent white from ever accomplishing this mate in two (or one if the black rook moves to the a or b files without the white king to block it).
You can compare the PV in the searches below to what Leela comes up with in this Lichess study. The lichess study also includes a 7-man position that she horribly misevaluates. The 5-man she evaluates correctly because it is a five-man position, and she is given 5-man tablebases. https://lichess.org/study/pr2yCu1e 250k nodes info depth 8 seldepth 17 time 13814 nodes 254017 score cp 1411 hashfull 265 nps 18388 tbhits 0 pv d4e5 d3d8 e5f6 d8d6 f6e7 d6e6 e7d7 e6d6 d7c8 d6b6 b7a7 b6b7 c8b7 3M nodes info depth 10 seldepth 22 time 132587 nodes 3339570 score cp 1345 hashfull 1000 nps 25187 tbhits 0 pv d4e5 d3e3 e5d5 e3d3 d5e6 d3d6 e6e5 d6e6 e5d4 e6d6 d4e3 d6d4 e3f3 d4d3 f3f4 d3d8 b7a7 d8f8
You might want to note that at only very low nodes, leela evaluates this 6-man position properly. Here it is as demonstration to the issue, where leela's MCTS will initially give the correct evaluation, but will fail after 10-100 some nodes evaluating into the position.
NOTE: These PV's only are a representation of the search (which even still are telling), of course not the entire search tree itself.
You'll notice that it's closer to the front of her search that something goes wrong and she evaluates it incorrectly. She finds so many of these incorrect continuations at the front of her search that the MCTS will average the wins and the draws, correct drawn continuations becoming flooded out by incorrect evaluations at the forefront of her search. If you're careful enough you'll notice that her PV output is in odd numbers each time, (except when it gets to really high nodes like the 3 million node example where she goes deeper into some lines not yet noticing that there are mistakes made earlier) because her search is playing the wrong moves on black's behalf, while white can only take what black gives. Due to the observations I've made, my hypothesis is that leela's neural network is evaluating most of these individual positions that she searches correctly because tablebases have rescored her NN to understand them, but there is something deliberately wrong with the search itself. The outputs are wrong because she always finds a continuation--a deviation at the end of her search that indicates the position is not a draw. Because there are so many deviations, the ultimate output by the Lc0 engine is higher than it is supposed to be.
How do you fix this? We want to reduce the problem so that we aren't thinking of an infinite amount of fixes. There are zero and non-zero ways to fix this. Because it's an issue in MCTS, there should be something about MCTS we should add to and change. Therefore, we can look for a computationally inexpensive solution by changing the MCTS to recognizing that the search perpetually finds incorrect continuations by looking for a whole line of 'drawn-evaluated-positions' all the sudden changing to won positions at the end of the search.
You can go down the path of trying to write some complex evaluation function that evaluates the tree as a whole (even a NN). This is impractical and computationally expensive You could even 'simplify' the whole matter and look for repeating patterns in the search, like those demonstrated in the diagram. These are still impractical and will have far too many bugs, not only that, but are non-zero.
Instead in a far simpler course of action, you can assign a new value in the MCTS that represents stalemates, and create a value 'proven-stalemate frequency' which can be used to guide the MCTS itself. If a repeating pattern of stalemates are found earlier in the search, then you can tell the MCTS with a 'stalemate' value to continue searching for stalemate lines to make sure that it's not missing them. Otherwise, MCTS won't first try to prove that any proper continuation by black doesn't lead to something drawish.
Perhaps a more solidly 'zero' and general solution for any kind of perpetual would be to train the NN to recognize, predict, and output what kind of outcome will happen. A '50-move-rule%' outcome, a '3-fold-repitition%' outcome, a 'stalemate%' and a 'non-drawn%.' In a way, this is a new kind of 'policy' in a more general form that can guide how the MCTS itself searches based upon how many occurrences there are of those kinds of evaluations. These new evaluation values should further hint at what lines are 'incorrect' and negligible while MCTS can use that accordingly.
Some day I can start working on such code and work out technicalities, but as of now, I'm putting this problem, my thinking, and 2 thought-of solutions out there in hopes that someone can write the code to solve this long-standing problem since the beginning of the project before me to improve Leela even more.