{"action":"created","issue":{"url":"https://api.github.com/repos/LeelaChessZero/lc0/issues/211","repository_url":"https://api.github.com/repos/LeelaChessZero/lc0","labels_url":"https://api.github.com/repos/LeelaChessZero/lc0/issues/211/labels{/name}","comments_url":"https://api.github.com/repos/LeelaChessZero/lc0/issues/211/comments","events_url":"https://api.github.com/repos/LeelaChessZero/lc0/issues/211/events","html_url":"https://github.com/LeelaChessZero/lc0/pull/211","id":343465067,"node_id":"MDExOlB1bGxSZXF1ZXN0MjAzMDkzNDI4","number":211,"title":"After finding a checkmate, never bother searching for alternatives to mate","user":{"login":"dubslow","id":6127392,"node_id":"MDQ6VXNlcjYxMjczOTI=","avatar_url":"https://avatars0.githubusercontent.com/u/6127392?v=4","gravatar_id":"","url":"https://api.github.com/users/dubslow","html_url":"https://github.com/dubslow","followers_url":"https://api.github.com/users/dubslow/followers","following_url":"https://api.github.com/users/dubslow/following{/other_user}","gists_url":"https://api.github.com/users/dubslow/gists{/gist_id}","starred_url":"https://api.github.com/users/dubslow/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dubslow/subscriptions","organizations_url":"https://api.github.com/users/dubslow/orgs","repos_url":"https://api.github.com/users/dubslow/repos","events_url":"https://api.github.com/users/dubslow/events{/privacy}","received_events_url":"https://api.github.com/users/dubslow/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":55,"created_at":"2018-07-23T02:15:34Z","updated_at":"2018-07-29T07:01:38Z","closed_at":"2018-07-28T20:44:23Z","author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/LeelaChessZero/lc0/pulls/211","html_url":"https://github.com/LeelaChessZero/lc0/pull/211","diff_url":"https://github.com/LeelaChessZero/lc0/pull/211.diff","patch_url":"https://github.com/LeelaChessZero/lc0/pull/211.patch"},"body":"Was just wondering about this in relation to Leela not finding a mate in 5 posted on Discord.\r\n\r\nTurns out that after searching a checkmating move, all the other (non-mate) alternatives still get searched like normal, which in turn \"pollutes\" the Q value in the nodes above the tree. This is of course exactly what we want in most cases, PUCT is supposed to be least upper confidence bound after all, but when we find a checkmate, our confidence is infinite, the game result is without uncertainty -- so never bother with alternatives.\r\n\r\nThis will go a long way towards Leela giving quicker mates. When the game is already totally won, all Q values in the search tree will already be north of 0.9, so finding mates currently doesn't do much, because averaging in a 1.0 into a whole bunch of other 0.95 and 0.98 or whatever doesn't actually change much of anything higher up the search tree. This will guarantee that such higher-up values converge monotonically to 1, rather than asymptotically only over several tens or hundreds of thousands of nodes. (And to be clear, even without this patch, parents-to-mate will *eventually* converge to having Q=1.0, but only after literally thousands or millions of nodes as the sqrt(N) term in the normal U decreases. Instead with this patch, converge immediately.)\r\n\r\nDemonstrations of these qualitative descriptions incoming."},"comment":{"url":"https://api.github.com/repos/LeelaChessZero/lc0/issues/comments/408656677","html_url":"https://github.com/LeelaChessZero/lc0/pull/211#issuecomment-408656677","issue_url":"https://api.github.com/repos/LeelaChessZero/lc0/issues/211","id":408656677,"node_id":"MDEyOklzc3VlQ29tbWVudDQwODY1NjY3Nw==","user":{"login":"dubslow","id":6127392,"node_id":"MDQ6VXNlcjYxMjczOTI=","avatar_url":"https://avatars0.githubusercontent.com/u/6127392?v=4","gravatar_id":"","url":"https://api.github.com/users/dubslow","html_url":"https://github.com/dubslow","followers_url":"https://api.github.com/users/dubslow/followers","following_url":"https://api.github.com/users/dubslow/following{/other_user}","gists_url":"https://api.github.com/users/dubslow/gists{/gist_id}","starred_url":"https://api.github.com/users/dubslow/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dubslow/subscriptions","organizations_url":"https://api.github.com/users/dubslow/orgs","repos_url":"https://api.github.com/users/dubslow/repos","events_url":"https://api.github.com/users/dubslow/events{/privacy}","received_events_url":"https://api.github.com/users/dubslow/received_events","type":"User","site_admin":false},"created_at":"2018-07-29T07:01:38Z","updated_at":"2018-07-29T07:01:38Z","author_association":"MEMBER","body":"`your original argument was that this change corrects a bug in MCTS`\r\n\r\nI maintain this is true. MCTS converges in the infinite limit to perfect play -- and as I mentioned in my post, it is *currently* true that given sufficiently many visits, Q converges to 1 for all checkmate-producing moves, and in particular, the fraction of visits received by non-checkmate moves converges to 0. That is to say, MCTS converges to eliminating all information whatsoever from non-checkmate moves; in other words, these noncheckmate moves offer zero information. All this PR does is speed up the convergence.\r\n\r\nThat the data hints at a -5 elo loss is nothing more than noise so far. And, even if it is a true strength loss (which I still doubt, more data needed), that does *not* mean that the other nodes actually do generate information, for mathematically they do not (again, MCTS is proven to converge to perfect play, and alternatives to mate converge to 0% of the visit share). All it means is that we are using a search technique that the network wasn't trained for. (In other words, although all my statements about converged infinite-playout MCTS are true, in reality the Leela NN is only a finite approximation, and that approximation may or may not gain 3-5 elo by using mathematically irrelevant information as a heuristic, and using this technique where not so trained may mess up those approximation heuristics, which again, I'm still not convinced of that either. That still doesn't mean that this simplification is incorrect, it just means we haven't run the proper tests yet.)\r\n\r\nMy results will be ready once I've convinced someone on Discord to generate the data :) should be easier after next release, when option is available by default."}}
{"actor":{"display_login":"dubslow"}}