If you don't implement virtual loss, all threads will follow the same path in the UCT part of the playout, which is a huge departure from what the sequential algorithm would have done. Adding one loss temporarily when a thread picks the move discourages other threads from picking it, but it can be argued that this already results in too much exploration when compared with the sequential algorithm, since the sequential algorithm would sometimes be just as discouraged (when the previous playout resulted in a loss) and sometimes *less* discouraged (when the previous playout resulted in a win).
So if I were to tune this parameter, I would try with numbers smaller than 1, not larger. Álvaro. On Tue, Nov 30, 2010 at 12:13 PM, Richard B Segal <rse...@us.ibm.com> wrote: > Yes, there are many possible variations / enhancements to virtual loss. I > have found > experimentally that the +1 variety is sufficient for near perfect scaling to > hundreds of > threads so it is not clear that any additional improvement is needed. > > - Rich > > > computer-go-boun...@dvandva.org wrote on 11/30/2010 12:48:54 AM: > >> [image removed] >> >> Re: [Computer-go] Fuego in Kanazawa and UEC Cup >> >> Michael Williams >> >> to: >> >> computer-go >> >> 11/30/2010 12:49 AM >> >> Sent by: >> >> computer-go-boun...@dvandva.org >> >> Please respond to computer-go >> >> Since you brought up virtual losses, I wanted to point-out something >> that occurred to me recently: you don't have to use just one virtual >> loss. You can add N visits to a node when you visit it and then >> remove N-1 visits when you update the node with the playout result. >> The larger N is, the less different threads will step on each other. >> Of course increasing N also means an increased likelyhood of exploring >> irrelevant paths. >> >> >> >> On Mon, Nov 29, 2010 at 4:33 PM, Richard B Segal <rse...@us.ibm.com> >> wrote: >> > Hi Everyone, >> > >> > Aja's description of Fuego in the UEC cup is pretty accurate. The main >> > changes to Fuego for both events were to improve scaling on the 112 core >> > system. The move generation algorithm was mostly identical to the SVN >> > source >> > for both Kanazawa and the first day of the UEC cup. >> > >> > We did make a possibly significant change for the last two matches of >> > the >> > UEC cup. Once in Kanazawa and once on the first day of the UEC cup Fuego >> > lost by attacking with a ladder that would ultimately fail. Fuego has a >> > root >> > filter that prevents extending a group that will be captured in a >> > ladder, >> > but it does not filter failed attacks. I modified Fuego's root filter >> > for >> > the last two matches to remove failed attacks as well. I also modified >> > the >> > code to apply the root filter (minus its safety check) at all levels of >> > the >> > search. While the new code did not show any improvement in self play, it >> > did >> > improve its handling of the position that led to the failed ladderattack >> > in >> > the UEC match against Erica. >> > >> > The other change between Kanazawa and the UEC cup was regarding some >> > experimental code to improve exploration. The experimental code appears >> > to >> > be effective for 9x9 play, but its value for 19x19 play was >> > questionable. I >> > had weak experimental data (50 games) in Kanazawa suggesting it may be >> > useful so I enabled it for 19x19 as well. A similar weak experiment just >> > before the UEC cup showed a 50 ELO loss so it was disabled for the UEC >> > cup. >> > >> > Probably the most important change for running on the 56 core system was >> > switching from floats to doubles to score move evaluations. After about >> > one >> > million trials, the limited precision of floats becomes a bottleneck to >> > improved play. I made a few small modifications to the virtual loss code >> > to >> > ensure that virtual losses were added as early as possible, and removed >> > as >> > late as possible to maximize their effect. I also separated out the >> > counting >> > of virtual losses from the UCT statistics to reduce the chances of >> > simultaneous updates as simultaneous updates can introduce counting >> > errors. >> > >> > The final addition was a new parallel tree copy algorithm that was >> > needed >> > due to the large 200Gb RAM available on the 56 core system. When Fuego >> > runs >> > out of memory, it copies its current tree to a new tree while removing >> > nodes >> > with a small number of trials. The single threaded copy algorithm took >> > up to >> > 20 seconds on a 200Gb tree. The parallel tree copy algorithm reduces the >> > same copy to about 4 seconds. >> > >> > We plan to eventually move most if not all of these updates into the >> > public >> > Fuego source tree. For completeness, the configuration script used for >> > UEC >> > was as follows: >> > >> > go_rules japanese >> > time_settings 1800 0 0 >> > komi 6.5 >> > >> > uct_max_memory 175000000000 >> > >> > uct_param_player ponder 1 >> > uct_param_player reuse_subtree 1 >> > >> > uct_param_search lock_free 1 >> > uct_param_search number_threads 112 >> > uct_param_search number_playouts 2 >> > >> > # Enable new parallel tree copy >> > uct_param_search max_copy_threads 8 >> > >> > # New features added on second day of UEC cup >> > uct_param_globalsearch use_filter 1 >> > uct_param_rootfilter check_offensive_ladders 1 >> > >> > - Rich >> > >> > _______________________________________________ >> > Computer-go mailing list >> > Computer-go@dvandva.org >> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > >> _______________________________________________ >> Computer-go mailing list >> Computer-go@dvandva.org >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > _______________________________________________ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > _______________________________________________ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
