I've been using Leela 0.10.0 for analysis quite often, and I've noticed something that might lead to an improvement for the search, and maybe also for other MCTS programs.
Sometimes, after putting hundreds of thousands of simulations into a few possible moves, Leela will appear to favor one, disliking the others for having clearly worse reported winrates. But then every once in a while, the winrate for one of the other disliked moves will start rising gradually, but very consistently. When this happens, if I play down the variation for that move and look at the analysis window, I often find that Leela has discovered a new tactic. Specifically, I find a node in that subtree where one move has a greatly higher winrate than all the others, but does not have too many simulations yet, meaning Leela only just now found it. (Possibly it already has more simulations than any other single move, but the number of simulations of all of the other moves combined still significantly outweighs it). Going back to the root, it's clear that if the new tactic has a high enough winrate, then the previously disliked move will eventually overtake the favored move. But it takes a long time, since the disliked move has a lot of bad simulations to outweigh - it's painful to watch the winrate creep up slowly but with high upward consistency, until it finally beats out the previously favored move. I think there's a chance that the search could be improved by adding a small decay over time to the weight of old simulations. This would allow a move to be promoted a bit more rapidly with the discovery of a better tactic. You would probably want to set the decay over time so that the total weight over time still readily approaches infinity (e.g. a fixed exponential decay would probably be bad, that would bound the total weight by a constant), but perhaps a bit slower than linearly. Thinking about it from the multi-armed-bandit perspective, I think this also makes sense. The distribution of results from each child is nonstationary, because the subtree below the child is evolving over time. If they were stationary you would weight all historical simulations equally, but since they aren't, the more-recent results from a child should get a little bit more weight since they give you more information about the current performance of the child move. Has anyone tried this sort of idea before?
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
